Doubly Linked Lists

Convenient to be able to move both forward and backward.

For example, to print the 2nd last element of a list. Contrast:

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);

With the simpler:

current = create_window(L);
while (! is_last(current)) move_forward(current);
move_backward(current);
print_element(get_value(current),NULL);

To make MOVE_BACKWARD constant time, each node needs a backward pointer to the preceding node in the list.

Operations on doubly-linked lists must update both the forward and backward pointers.