Make your own free website on Tripod.com

2.2. Doubly Linked Lists (Back Pointers)

It is often very convenient to provide the user with operations to move through a list in either direction. This is because you just as often want you want to do an operation just before a particular node as you want to do the operation at or just after the node (e.g. delete the node preceding this one, insert a new node before this one, split the list before this node). The normal way this is accomplished in a singly-linked list, such as ours, is for the user to create two windows, and have one go through the list one step behind the other.

For example, to write out the second last element of a list L (assuming L has at least 2 elements):

        current  = create_window(L); move_forward(current);
        previous = create_window(L);

        while (! is_last(current)) {
          move_forward(previous);
          move_forward(current); }

        print_element(get_value(previous),NULL);
Code like this is needed in our implementation of the DELETE operation. This is rather obscure, much simple and more self-evident is:
        current = create_window(L);
        while (! is_last(current)) move_forward(current);
        move_backward(current);
        print_element(get_value(current),NULL);
To make MOVE_BACKWARD a constant time operation, each node needs to store an additional pointer, called a back pointer, which points at the preceding node in the list. Such a list is called doubly-linked because there are 2 links per node. Operations on doubly-linked lists are more complex than on singly-linked lists, because both the forward and backward pointers need to be updated. However, there is a complete symmetry in the operations, so they are not really much more complicated. Let's use node-and-arc diagrams to look at how we would JOIN two doubly-linked lists.

Before

After

This is actually identical to the JOIN operation for singly-linked lists except that there is one extra pointer that needs to be updated - the back pointer of the node that was first is L2.