7.4. Doubly Linked Lists¶
7.4.1. Doubly Linked Lists¶
The singly linked list allows for direct access from a list node only to the next node in the list. A doubly linked list allows convenient access from a list node to the next node and also to the preceding node on the list. The doubly linked list node accomplishes this in the obvious way by storing two pointers: one to the node following it (as in the singly linked list), and a second pointer to the node preceding it.
Figure 7.4.1: A doubly linked list.
The most common reason to use a doubly linked 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.
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
implementation 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.
In our implementation, curr will point to the
current position (or to the trailer node if the
current position is at the end of the list).
Here is 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.
class Link<E> { // Doubly linked list node
private E e; // Value for this node
private Link<E> n; // Pointer to next node in list
private Link<E> p; // Pointer to previous node
// Constructors
Link(E it, Link<E> inp, Link<E> inn) { e = it; p = inp; n = inn; }
Link(Link<E> inp, Link<E> inn) { p = inp; n = inn; }
// Get and set methods for the data members
public E element() { return e; } // Return the value
public E setElement(E it) { return e = it; } // Set element value
public Link<E> next() { return n; } // Return next link
public Link<E> setNext(Link<E> nextval) { return n = nextval; } // Set next link
public Link<E> prev() { return p; } // Return prev link
public Link<E> setPrev(Link<E> prevval) { return p = prevval; } // Set prev link
}
class Link { // Doubly linked list node
private Object e; // Value for this node
private Link n; // Pointer to next node in list
private Link p; // Pointer to previous node
// Constructors
Link(Object it, Link inp, Link inn) { e = it; p = inp; n = inn; }
Link(Link inp, Link inn) { p = inp; n = inn; }
// Get and set methods for the data members
public Object element() { return e; } // Return the value
public Object setElement(Object it) { return e = it; } // Set element value
public Link next() { return n; } // Return next link
public Link setNext(Link nextval) { return n = nextval; } // Set next link
public Link prev() { return p; } // Return prev link
public Link setPrev(Link prevval) { return p = prevval; } // Set prev link
}
7.4.1.1. Insert¶
The following slideshows illustrate the insert and append
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.
While the code for these methods might be a little longer than their
singly linked list counterparts (since there is an extra pointer in
each node to deal with), they tend to be easier to understand.
7.4.1.4. Prev¶
The only disadvantage of the doubly linked list as compared to the singly linked list is the additional space used. The doubly linked list requires two pointers per node, and so in the implementation presented it requires twice as much overhead as the singly linked list.
7.4.1.5. Mangling Pointers¶
There is a space-saving technique that can be employed to eliminate
the additional space requirement, though it will complicate the
implementation and be somewhat slower.
Thus, this is an example of a
space/time tradeoff.
It is based on observing that, if we store the sum of two values,
then we can get either value back by subtracting the other.
That is, if we store \(a + b\) in variable \(c\), then
\(b = c - a\) and \(a = c - b\).
Of course, to recover one of the values out of the stored summation,
the other value must be supplied.
A pointer to the first node in the list, along with the value of one
of its two link fields, will allow access to all of the remaining
nodes of the list in order.
This is because the pointer to the node must be the same as the value
of the following node’s prev pointer, as well as the previous
node’s next pointer.
It is possible to move down the list breaking apart the
summed link fields as though you were opening a zipper.
The principle behind this technique is worth remembering, as it has many applications. The following code fragment will swap the contents of two variables without using a temporary variable (at the cost of three arithmetic operations).
a = a + b;
b = a - b; // Now b contains original value of a
a = a - b; // Now a contains original value of b
a = a + b;
b = a - b; // Now b contains original value of a
a = a - b; // Now a contains original value of b
A similar effect can be had by using the exclusive-or operator. This fact is widely used in computer graphics. A region of the computer screen can be highlighted by XORing the outline of a box around it. XORing the box outline a second time restores the original contents of the screen.
