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.
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.
