Lists

From

Revision as of 23:41, 25 March 2009

Among the simplest data structures is the list. What is a list? A list is an unordered sequence of homogeneous data. The normal operations that are performed on lists are: insert(), remove(), and inList() (membership).

To move from an ADT to a data structure, we need to consider an implementation. First consider an array based implementation. Memory for an array is allocated sequentially. So consider two pointers, one to front of the list and one to the end of the list. Suppose I called them front and back. If I always add an item to the list at the slot that back points to, and remove an item from the slot that front points to, then my list is empty when front and back point to the same slot. To add an item to the list requires that I place the item in the slot where back points to and then increment back. To remove an item from the list means to remove an item from the slot that front points to and then increment front.

Each of these two operations require a certain amount of time, but that time does not depend on the size of the list. These two operations take constant time or O( 1 ).

Since an array implementation requires that I declare the size ahead of time, how would I know when my list is full? If the size of the list is N and the array takes slots 0 … N – 1, then when back is equal to N, the list is full. But notice what happens when I add some items and delete some items. After a while, my list might become full, because back is equal to N, but it is possible that most of the array is actually empty. What shall I do? I could periodically copy my list to a new list that always starts from the first empty position. How much time does this take? Copying depends on the size of the list, so it is O( N ). Another question is when should I perform the copy? Certainly every time I do an add is too often, because then adding is no longer a constant operation. Perhaps I can use a count operation that specifies a copy operation when there are a set number of empty spaces in the front of the array?

Circular Lists

Suppose I allocate 5 slots for a list and they are numbered 0 … 4. Now suppose I set up the following operations. A new list has front set to 0 and back set to 4. Adding an item to a list means to set back = (back + 1) mod 5 then add the item at that slot. Removing an item means to remove the item from the slot pointed to by front and then to set front = (front + 1) mod 5. When is a list full? When front == (back + 2 ) mod 5. When is a list empty? When front == (back + 1) mod 5. Note that this method wastes a slot, but for a large list, this is of little consequence.

What if I now want to be able to insert an item into the middle of my list? This will be O(N) because I need to move half the list to make room in the middle for the added item. A solution to this problem is to use linked representation.

Linked Representation

Linked representation means that we are using dynamic allocation. The elements of a list are usually called nodes, where a node has two parts. One part of the node contains the data, and the second part is called the pointer.

Linked list can be set up to have a special head node that contains a pointer to the first and to the last node or to simply use a list node to point to the head node. A linked list can also be singly linked or doubly linked.

A pointer that does not point to anything is said to be null (or in some languages, nil). Consider a list that has a head pointer containing two node pointers: one to the front of the list and one to the back of the list. Again, we will add items to the end of the list, and remove items from the front of the list.

We will use a list node that has two parts: the first part is called data and the second part is a pointer to a list node and is called next. We will also make use of a third type of node called temp that is just a pointer to a list node.

When a new list is created, both front and rear are null. To add a node means that there are two cases to consider: Adding a node to an empty list, and adding a node to a list that has one or more nodes that belong to it.

1. Temp points to the node to be added.
2. If Rear is null, the list is empty, so set Front and Rear to point to the node pointed to by Temp.
3. If Rear is not null, there is at least one node in the list. Set the next field of the node pointed to by Rear to the node pointed to by Temp. Now set Rear to point to the node pointed to by Temp.

When deleting a node, there are three cases to consider: the list is empty, the list has one item, and the list has two or more items.

1. First check to see if Front is null. If it is, then the list is empty and no node can be deleted.
2. If Front is not null, there is at least one node in the list. Check to see if Front and Rear point to the same node. If they do, there is only one node in the list. So, set Temp to point to the node that Front points to. Then set both Front and Rear to null.
3. If Front and Rear do not point to the same node, then there are at least two nodes in the list. Set Temp to point to the node pointed to by Front, then set Front to point to the node pointed to by Front.next.