7.2.5 Doubly Linked List

In this example, you are going to look at a variation of the linked list called a Doubly Linked List. This is essentially the same thing as a linked list with the exception that you now add a previous field to the node.

As you would expect, the previous tracks the previous node just like the next tracked the next node. This allows for lists to be easily traversed forwards and backward.

Source: By Lasindi - Own work, Public Domain, https://commons.wikimedia.org/w/index.php?curid=2245165

Doubly Linked List Implementation

The implementation is nearly identical to a standard linked list.

Head - Same as the standard linked list. It starts as NULL and gets updated along the way.

Tail (optional) - Since you will have the option to work backward through the linked list, you may want to track the tail so that you can start at the end and traverse forward.

Inserting into the list - To add nodes into the doubly linked list, you follow the same steps as before, with two extra steps:

• Create a new node element and add the data to that element

• Link the pointer in the new node element to point to the existing head

• New - Set the previous of the new node element to NULL

• New - Using a conditional statement, check to see if the head is NULL.

  • If it is not NULL, set the previous of the head to point to the new node element

  • If it is NULL this is the first element, so set the tail to point to this element.

• Update the head to point to the new node element.

Your loop to insert new elements will not look like this:

for (int i = 0; i < 3; i++) {
    int newData  = i;
    item *newItem = new item;
    newItem->data = newData;
    newItem->next = head;
    // New steps
    newItem->prev = NULL;
    if (head != NULL) {
        head->prev = newItem;
    }
    else {
      tail = newItem;  
    }

    head = newItem;   
}

Here is the example in motion. Notice how the tail remains static once set, and the new items get added to the front of the list.

Traversing the list is the same as a single linked list. You now have an option to start at the end and work forward. See the example below for this.

Try This Example