Close
Register
Close Window

Data Structures & Algorithms

Chapter 3 Linked List and Stack

Show Source |    | About   «  3.5. Comparison of List Implementations   ::   Contents   ::   3.7. List Element Implementations  »

3.6. Doubly Linked Lists

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

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

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

3.6.1.2. Append

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

3.6.1.3. Remove

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

3.6.1.4. Prev

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

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.

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

   «  3.5. Comparison of List Implementations   ::   Contents   ::   3.7. List Element Implementations  »

Close Window