10.1.1. Motivating 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 by storing two pointers instead one: one to the “next” node following it (as in the singly linked list), and a second pointer to the “previous” node preceding it:

While the code for the doubly linked operations tend to be a little longer than for the singly linked version, because we now maintain a previous and next pointer our methods become more “symmetric,” which can make them easier to implement and debug. Whether a list implementation is doubly or singly linked should be hidden from the List class user.

10.1.2. Node class implementation¶

Here is the complete implementation for a Node 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:

// Node class implementation for doubly linked list
class Node<E> {
    private E data; // Value for this node
    private Node<E> next; // Pointer to next node in list
    private Node<E> prev; // Pointer to previous node in list

    // Constructors
    Node(E element, Node<E> prevNode, Node<E> nextNode) {
        data = element;
        prev = prevNode;
        next = nextNode;
    }

    Node(E element) {
        data = element;
        prev = null;
        next = null;
    }

    // return the value held in Node
    public E getValue() {
        return data;
    }

    // set value held in Node
    public void setValue(E newData) {
        data = newData;
    }

    // return the next node
    public Node<E> getNext() {
        return next;
    }

    // set next Node
    public void setNext(Node<E> nextNode) {
        next = nextNode;
    }

    // return the previous node
    public Node<E> getPrev() {
        return prev;
    }

    // set the previous node
    public void setPrev(Node<E> prevNode) {
        prev = prevNode;
    }
}

Note that the Node class is a generic class, so it can be used to store any type of data. Also notice that the Node class has a constructor that takes a single argument, which is the data to be stored in the node – with this constructor, the prev and next variables are set to null.

10.1.3. addLast() implementation¶

The class declaration and methods for the doubly linked list class are nearly identical to the singly linked list version.

Let’s walk through the addLast() method for a doubly linked list.

Settings

Saving...
Server Error
Resubmit

10.1.4. addAfter() implementation¶

The following illustrates the addAfter() method for a doubly linked list.

Settings

Saving...
Server Error
Resubmit

10.1.5. remove() a given node¶

Here, we look at a slightly different remove method, where we pass in the node to be removed as an argument. This method demonstrates the benefit of maintaining a prev pointer in the node structure.

Settings

Saving...
Server Error
Resubmit

In a singly linked list, removing a node is not straightforward because you need to somehow locate the node before the node to be removed. This is not necessary in a doubly linked list, as you can directly access the previous node using the prev pointer.

10.1.6. Summarizing list operation efficiency¶

Here’s a summary of the efficiency some operations for singly and doubly linked lists:

You’ll notice that the doubly linked list has the same efficiency or better for all of these operations. The primary 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.