Doubly Linked Lists

Overview

There are a few flaws with linked lists the way we have it:

Adding to the end is not as efficient as adding to the front.
It's hard to know what node comes before another one, making the remove method awkward.
Looping backwards is awkward and slow.

Doubly Linked Lists

In order to solve these problems, we will introduce another type of linked list called a doubly linked list. A doubly linked list is a type of linked list, where, instead of having each node only know the location of the next node, it also knows the location of the previous one.

Below is a doubly linked list with three nodes:

Each node contains a data element, a reference to the previous node (which could be null),
and a reference to the next element (which could be null). This list has three nodes. — A doubly linked list

The above image depicts a doubly linked list. Now instead of each node containing two things, they each contain three things. Like before there is the data element and the next pointer which tells us where the next node in the list is.

Now there is also another pointer called "prev". This pointer stores the location of the previous node in the list. Now that we have a link to the previous node at each item in the list, we can easily go backwards through the list.

Normal linked lists (called "singly linked lists") only store the location of the first node in the list, the head. Doubly linked lists normally store the location of the first node and the last node, which is often called "tail". This allows us to go directly to the end of the linked list.

Changes to Make a List Doubly-Linked

To make a singly-linked list into a doubly linked list, there are a few changes we have to make. First we have to add the previous link into the Node declaration:


private class Node {
    Type data;
    Node next;
    Node prev;
}

We then have to add a reference to the end of the list to the List object's member variables:


    private Node head;
    private Node tail;

    // ...

This makes our list doubly linked, since now each node has two links, the next and the prev. Every function that deals with the linked list must now account for both links. So if we add a node, we have to setup both links appropriately.

Doubly linked lists solve the problem of adding nodes to the end, which we can now do directly, and the problem of looping through the list in reverse, which can now be done easily using the prev links.

Inserting Nodes at the Beginning

Inserting nodes at the beginning of a doubly linked list is much the same as with a singly linked list. The only difference is that now, we must account for the prev pointer as well as the tail of the list:

Make a new node.
Set the data field.
Set newNode.next to head.
Set newNode.prev to null.
If the list is empty, set tail to newNode.
Else set head.prev to newNode.
Set head to newNode.

Below is this algorithm implemented in Java:


// add a new value at the start
public void addStart(Type value) {
    Node newNode = new Node();
    newNode.data = value;
    newNode.next = head;
    newNode.prev = null;

    if (head == null) {
        tail = newNode;
    } else {
        head.prev = newNode;
    }

    head = newNode;
}

Inserting Nodes at the End

Now, to insert at the end of the list, we know longer have to go through the whole thing just to find the end. Now we can go directly to the end and add in nodes the same way we do at the start:

Make a new node.
Set the data field.
Set newNode.prev to tail.
Set newNode.next to null.
If the list is empty, set head to newNode.
Else set tail.next to newNode.
Set tail to newNode.

Notice that this is the same basic algorithm as adding at the front, except we flip next/prev and head/tail.

Below is this algorithm implemented in Java:


// add a new value to the end
public void addEnd(Type value) {
    Node newNode = new Node();
    newNode.data = value;
    newNode.prev = tail;
    newNode.next = null;

    // set node before to point to new node, or head
    if (tail == null) {
        head = newNode;
    } else {
        tail.next = newNode;
    }

    tail = newNode;
}