Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 113

HEAD CURR TAIL

20 23 12 15

Figure4.13 A doubly linked list.

list is because it is easier to implement than a singly linked list. While the code for
the doubly linked implementation is a little longer than for the singly linked version,
it tends to be a bit more “obvious” in its intention, and so easier to implement
and debug. Figure 4.13 illustrates the doubly linked list concept. Whether a list
implementation is doubly or singly linked should be hidden from the List class
user.
Like our singly linked list implementation, the doubly linked list implementa-
tion makes use of a header node. We also add a tailer node to the end of the list.
The tailer is similar to the header, in that it is a node that contains no value, and it
always exists. When the doubly linked list is initialized, the header and tailer nodes
are created. Data member head points to the header node, and tail points to
the tailer node. The purpose of these nodes is to simplify the insert , append ,
and remove methods by eliminating all need for special-case code when the list
is empty, or when we insert at the head or tail of the list.
For singly linked lists we set curr to point to the node preceding the node that
contained the actual current element, due to lack of access to the previous node
during insertion and deletion. Since we do have access to the previous node in a
doubly linked list, this is no longer necessary. We could set curr to point directly
to the node containing the current element. However, I have chosen to keep the
same convention for the curr pointer as we set up for singly linked lists, purely
for the sake of consistency.
Figure 4.14 shows the complete implementation for a Link class to be used
with doubly linked lists. This code is a little longer than that for the singly linked list
node implementation since the doubly linked list nodes have an extra data member.
Figure 4.15 shows the implementation for the insert , append , remove ,
and prev doubly linked list methods. The class declaration and the remaining
member functions for the doubly linked list class are nearly identical to the singly
linked list version.
The insert method is especially simple for our doubly linked list implemen-
tation, because most of the work is done by the node's constructor. Figure 4.16
shows the list before and after insertion of a node with value 10.
The three parameters to the new operator allow the list node class constructor
to set the element , prev , and next fields, respectively, for the new link node.
The new operator returns a pointer to the newly created node. The nodes to either
side have their pointers updated to point to the newly created node. The existence