Link List

A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets, supporting (though not necessarily efficiently) all the operations.

As shown in Figure 10.3, each element of a doubly linked list L is an object with an attribute key and two other pointer attributes: next and pre. The object may also contain other satellite data. Given an element x in the list, x.next points to its successor in the linked list, and x.pre points to its predecessor. If x.pre = NIL, the element x has no predecessor and is therefore the first element, or head, of the list. If x.next = NIL, the element x has no successor and is therefore the last element, or tail, of the list. An attribute L.head points to the first element of the list. If L.head = NIL, the list is empty.

A list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not. If a list is singly linked, we omit the pre pointer in each element. If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list; the minimum element is then the head of the list, and the maximum element is the tail. If the list is unsorted, the elements can appear in any order. In a circular list, the pre pointer of the head of the list points to the tail, and the next pointer of the tail of the list points to the head. We can think of a circular list as a ring of elements. In the remainder of this section, we assume that the lists with which we are working are unsorted and doubly linked.

Searching a linked list

The procedure LIST-SEARCH(L, k) finds the first element with key k in list L by a simple linear search, returning a pointer to this element. If no object with key k appears in the list, then the procedure returns NIL. For the linked list in Figure 10.3(a), the call LIST-SEARCH(L, 4) returns a pointer to the third element, and the call LIST-SEARCH(L, 7) returns NIL.

LIST-SEARCH(L, k)

1 x = L.head 

2 while x ≠ NIL and x.key ≠ k 

3     x = x.next 

4 return x

To search a list of n objects, the LIST-SEARCH procedure takes O(n) time in the worst case, since it may have to search the entire list.

Inserting into a linked list

Given an element x whose key attribute has already been set, the LIST-INSERT procedure “splices” x onto the front of the linked list, as shown in Figure 10.3(b)

LIST-INSERT(L, x) 

1 x.next = L.head 

2 if L.head ≠ NIL 

3     L.head.pre = x 

4 L.head = x 

5 x.pre = NIL

(Recall that our attribute notation can cascade, so that L.head.pre denotes the pre attribute of the object that L.head points to.) The running time for LISTINSERT on a list of n elements is O(1).

Deleting from a linked list

The procedure LIST-DELETE removes an element x from a linked list L. It must be given a pointer to x, and it then “splices” x out of the list by updating pointers. If we wish to delete an element with a given key, we must first call LIST-SEARCH to retrieve a pointer to the element.

LIST-DELETE(L, x)

1 if x.pre ≠ NIL 

2     x.pre.next = x.next 

3 else L.head = x.next 

4 if x.next ≠ NIL 

5     x.next.pre = x.pre

Figure 10.3(c) shows how an element is deleted from a linked list. LIST-DELETE runs in O(1) time, but if we wish to delete an element with a given key, O(n) time is required in the worst case because we must first call LIST-SEARCH to find the element.

Sentinels

The code for LIST-DELETE would be simpler if we could ignore the boundary conditions at the head and tail of the list:

LIST-DELETE0 (L, x)

1 x.pre.next = x.next 

2 x.next.pre = x.pre

A sentinel is a dummy object that allows us to simplify boundary conditions. For example, suppose that we provide with list L an object L:nil that represents NIL but has all the attributes of the other objects in the list. Wherever we have a reference to NIL in list code, we replace it by a reference to the sentinel L.nil. As shown in Figure 10.4, this change turns a regular doubly linked list into a circular, doubly linked list with a sentinel, in which the sentinel L.nil lies between the head and tail. The attribute L.nil.next points to the head of the list, and L.nil.pre points to the tail. Similarly, both the next attribute of the tail and the pre attribute of the head point to L.nil. Since L.nil.next points to the head, we can eliminate the attribute L.head altogether, replacing references to it by references to L.nil.next. Figure 10.4(a) shows that an empty list consists of just the sentinel, and both L.nil.next and L.nil.pre point to L.nil.

The code for LIST-SEARCH remains the same as before, but with the references to NIL and L.head changed as specified above

LIST-SEARCH' (,, k) 

1 x = L.nil.next 

2 while x ≠ L.nil and x.key ≠ k 

3     x = x.next 

4 return x

We use the two-line procedure LIST-DELETE' from before to delete an element from the list. The following procedure inserts an element into the list:

LIST-INSERT' (L, x) 

1 x.next = L.nil.next 

2 L.nil.next.pre = x 

3 L.nil.next = x 

4 x.pre = L.nil

Figure 10.4 shows the effects of LIST-INSERT' and LIST-DELETE' on a sample list.

Sentinels rarely reduce the asymptotic time bounds of data structure operations, but they can reduce constant factors. The gain from using sentinels within loops is usually a matter of clarity of code rather than speed; the linked list code, for example, becomes simpler when we use sentinels, but we save only O(1/)time in the LIST-INSERT' and LIST-DELETE' procedures. In other situations, however, the use of sentinels helps to tighten the code in a loop, thus reducing the coefficient of, say, n or n² in the running time.

We should use sentinels judiciously. When there are many small lists, the extra storage used by their sentinels can represent significant wasted memory. In this book, we use sentinels only when they truly simplify the code.