Lists

From

Revision as of 23:57, 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.

Temp points to the node to be added.

If Rear is null, the list is empty, so set Front and Rear to point to the node pointed to by Temp

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.

First check to see if Front is null. If it is, then the list is empty and no node can be deleted.

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.

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.

Now consider adding or removing a node from the middle of the list. First consider removing a node. The first problem is to find the node that we want to remove.

1. Let Temp point to the node pointed to by Front. If this node is not the one we want to delete, let Temp point to the node pointed to by Temp.next. Continue this process until we find the node to be removed. 2. Let P be a second pointer like Temp. Start P from Head and ask the question, does P.next point to the same node as Temp? If it does not, slide P down one node in the list. Continue this process until P.next points to the same node as Temp. 3. Set P.next to the value of Temp.next and then set Temp.next to null.

To add a node in the middle of the list, let Temp point to the node to be added. Now we have to find the spot where this node is to be added. Let P start from Head and travel down the list until we find the node which the new node will come after. Then:

1. Set Temp.next to point to the node that P.next points to. 2. Now set P.next to point to the node that Temp points to.

Note that insertion and deletion in this type of list is O( N ).

Unlike an array based implementation, a linked representation does not have random access to nodes, only sequential access. This means that to get to a node in the middle of the list, a pointer must always start from the head pointer and travel the list, node by node until it finds the node for which it is looking. Also, a singly linked list can only be traversed in a single direction. An alternative to a singly linked list is a doubly linked list.

In a doubly linked list, each node has a data field and two pointer fields: next and previous. Traversing a list is easier because we can move in both directions. Where might this be useful? If we have a long list, which is kept in some sorted order, and we do a great deal of searching of the list. However, inserting and deleting become more complex, and this is the trade-off for the ease of searching.

Consider removing and adding a node to a doubly linked list.

To add a node at the end of the list

Let Temp be a node pointer that points to the node being added.

If Rear is null, the list is empty. Set Front and Rear to Temp.

If Rear is not null do the following

    Set Temp.previous to Rear.

    Set Rear.next to Temp.

    Set Rear to Temp.