Linked lists - Data Structures and Problem Solving Using Java - page 631

when designing a text editor, we can maintain the internal image of the file as
a linked list of lines. We want to be able to move up just as easily as down in
the list, to insert both before and after a line rather than just after, and to be
able to get to the last line quickly. A moment's thought suggests that to imple-
ment this procedure efficiently we should have each node maintain two links:
one to the next node in the list and one to the previous node. Then, to make
everything symmetric, we should have not only a header but also a tail. A
linked list that allows bidirectional traversal by storing two links per node is
called a doubly linked list. Figure 17.15 shows the doubly linked list repre-
senting a and b . Each node now has two links ( next and prev ), and searching
and moving can easily be performed in both directions. Obviously, there are
some important changes from the singly linked list.

First, an empty list now consists of a head and tail , connected as shown in
Figure 17.16. Note that head.prev and tail.next are not needed in the algo-
rithms and are not even initialized. The test for emptiness is now

Symmetry demands
that we use both a
head and a tail and
that we support
roughly twice as
many operations. head.next == tail

or

tail.prev == head

We no longer use null to decide whether an advance has taken us past the
end of the list. Instead, we have gone past the end if current is either head or
tail (recall that we can go in either direction). The retreat operation can be
implemented by

When we advance
past the end of the
list, we now hit the
tail node instead
of null .

current = current.prev;

figure 17.15
A doubly linked list

a b

head tail

figure 17.16
An empty doubly
linked list

head tail