Basic Structures:Linked Lists

Linked Lists

The linked list is an alternative to the array when a collection of objects is to be stored. The linked list is implemented using pointers. Thus, an element (or node) of a linked list contains the actual data to be stored and a pointer to the next node. Recall that a pointer is simply the address in memory of the next node. Thus, a key difference from arrays is that a linked list does not have to be stored contiguously in memory.

The code fragment below defines a linked list data structure, which is also illustrated in Figure 2.5:

A chain is a linked list where each node contains a pointer to the next node in the list. The last node in the list contains a null (or zero) pointer. A circular list is identical to a chain except that the last node contains a pointer to the first node. A doubly linked circular list differs from the chain and the circular list in that each node contains two pointers. One points to the next node (as before), while the other points to the previous node.

Chains

The following code searches for a key k in a chain and returns true if the key is found and false, otherwise.

In the worst case, Search takes Θ(n) time. In order to insert a node newnode in a chain immediately after node current, we simply set newnode’s pointer to the node following current (if any) and current’s pointer to newnode as shown in the Figure 2.6.

To delete a node current, it is necessary to have a pointer to the node preceding current. This node’s pointer is then set to current->next and node current is freed. Both insertion and deletion can be accomplished in O(1) time provided that the required pointers are initially available. Whether this is true or not depends on the context in which these operations are called. For example, if you are required to delete the node with key 50, if it exists, from a linked list, you would first have to search for 50. Your search algorithm would maintain a trailing pointer so that when 50 is found, a pointer to the previous node is available. Even though, deletion takes Θ(1) time, deletion in this context would require Θ(n) time in the worst case because of the search. In some cases, the context depends on how the list is organized. For example, if the list is to be sorted, then node insertions should be made so as to maintain the sorted property (which could take Θ(n) time). On the other hand, if the list is unsorted, then a node insertion can take place anywhere in the list. In particular, the node could be inserted at the front of the list in Θ(1) time. Interestingly, the author has often seen student code in which the insertion algorithm traverses the entire linked list and inserts the new element at the end of the list!

As with arrays, chains can be sorted or unsorted. Unfortunately, however, many of the benefits of a sorted array do not extend to sorted linked lists because arbitrary elements of a linked list cannot be accessed quickly. In particular, it is not possible to carry out binary search in O(log n) time. Nor is it possible to locate the ith smallest element in O(1) time. On the other hand, merging two sorted lists into one sorted list is more convenient than merging two sorted arrays into one sorted array because the traditional implementation requires space to be allocated for the target array. A code fragment illustrating the merging of two sorted lists is shown below. This is a key operation in mergesort:

The merge operation is not defined when lists are unsorted. However, one may need to combine two lists into one. This is the concatenation operation. With chains, the best approach is to attach the second list to the end of the first one. In our implementation of the linked list, this would require one to traverse the first list until the last node is encountered and then set its next pointer to point to the first element of the second list. This requires

time proportional to the size of the first linked list. This can be improved by maintaining a pointer to the last node in the linked list.

It is possible to traverse a singly linked list in both directions (i.e., left to right and a restricted right-to-left traversal) by reversing links during the left-to-right traversal. Fig- ure 2.7 shows a possible configuration for a list under this scheme.

As with the heterogeneous arrays described earlier, heterogeneous lists can be implemented in object-oriented languages by using inheritance.

Circular Lists

In the previous section, we saw that to concatenate two unsorted chains efficiently, one needs to maintain a rear pointer in addition to the first pointer. With circular lists, it is possible to accomplish this with a single pointer as follows: consider the circular list in Figure 2.8. The second node in the list can be accessed through the first in O(1) time.

Now, consider the list that begins at this second node and ends at the first node. This may be viewed as a chain with access pointers to the first and last nodes. Concatenation can now be achieved in O(1) time by linking the last node of one chain to the first node of the second chain and vice versa.

Doubly Linked Circular Lists

A node in a doubly linked list differs from that in a chain or a singly linked list in that it has two pointers. One points to the next node as before, while the other points to the previous node. This makes it possible to traverse the list in both directions. We observe that this is possible in a chain as we saw in Figure 2.7. The difference is that with a doubly linked list, one can initiate the traversal from any arbitrary node in the list. Consider the following problem: we are provided a pointer x to a node in a list and are required to delete it as shown in Figure 2.9. To accomplish this, one needs to have a pointer to the previous node. In a chain or a circular list, an expensive list traversal is required to gain access to this previous node. However, this can be done in O(1) time in a doubly linked circular list. The code fragment that accomplishes this is as below:

An application of doubly linked lists is to store a list of siblings in a Fibonacci heap (Chapter 7).

Generalized Lists

A generalized list A is a finite sequence of n ≥ 0 elements, e0, e1, ..., en−1, where ei is either an atom or a generalized list. The elements ei that are not atoms are said to be sublists of A. Consider the generalized list A = ((a, b, c), ((d, e),f ), g). This list contains three elements: the sublist (a, b, c), the sublist ((d, e),f ) and the atom g. The generalized list may be implemented by employing a GenListNode type as follows:

If tag is true, the element represented by the node is a sublist and down points to the first node in the sublist. If tag is false, the element is an atom whose value is contained in data. In both cases, next simply points to the next element in the list. Figure 2.10 illustrates the representation.