Home CPSC 340

Doubly Linked Lists

Accessing the End of a Linked List

With a normal linked list, we can only directly access the first element of the list.

This makes adding to the end of a list complicated and slow:

  1. Create the new node with the right data.
  2. Set the new node's next field to NULL.
  3. If the list is empty, set the head to the new node and return.
  4. Search through the list for the last node.
  5. Set the last node's next field to the new node.

As we can see, this is much slower than adding at the beginning of a list since we have to loop through every node in the list.

What if we want to loop through a linked list in reverse order? This is possible, but not simple with a regular linked list.


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:

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:


struct Node {
  int data;
  Node* next;
  Node* prev;
};

We then have to add a pointer to the end of the list to the List object's private section:


  ...

  private:
    Node* head;
    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:

  1. Make the new node with the given data.
  2. Set the node's prev to NULL.
  3. If the list is empty:
    1. Set the head to node.
    2. Set the tail to node.
    3. Set node's next to NULL.
  4. Otherwise:
    1. Set node's next to head.
    2. Set head's prev to node.
    3. Set head to node.

Below is this algorithm implemented in C++:


// add a new value at the start
void addStart(int value) {
    Node* newNode = new Node;
    newNode->next = head;
    newNode->prev = NULL;
    newNode->data = value;

    if (head != NULL) {
        head->prev = newNode;
    } else {
        tail = 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:

  1. Make the new node with the given data.
  2. Set the node's next to NULL.
  3. If the list is empty:
    1. Set the head to node.
    2. Set the tail to node.
    3. Set node's prev to NULL.
  4. Otherwise:
    1. Set node's prev to tail.
    2. Set tail's next to node.
    3. Set tail to node.
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 C++:


// add a new value to the end
void addEnd(int value) {
    Node* newNode = new Node;
    newNode->prev = tail;
    newNode->data = value;
    newNode->next = NULL;

    // set node before to point to new node, or head
    if (tail != NULL) {
        tail->next = newNode;
    } else {
        head = newNode;
    }

    tail = newNode;
}

Deleting Nodes

Deleting a node is also much the same as for a singly-linked list, but we have to make sure that we make, not only the next pointer route around the deleted node, but also the prev pointer. Another difference is that we do not need to keep two pointers as well search, but only one - since the previous is now easy to find:

  1. Keep a pointer to the current node.
  2. Loop through the list until we find one where current has the data we're looking for.
    1. If that's the first node:
      1. Set head to currents next.
      2. If there is now a head, set heads prev to NULL.
    2. Else:
      1. Set the current->prev->next to current->next.
      2. If current has a next, set it's prev to current->prev.
      3. Otherwise, set tail to current->prev.
    3. Delete the current node.
    4. Return.
  3. If we didn't find it, it wasn't there!

Below is this algorithm implemented in C++:


// remove an element
void remove(int value) {
    // find the node with our number
    Node* current = head;
    while(current != NULL) {
        // if the value was found
        if(current->data == value) {

            // if the previous is NULL, we are removing head!
            if(current->prev == NULL) {
                head = current->next;
                if(head != NULL) {
                    head->prev = NULL;
                } else {
                    tail = NULL;
                }
            } else {
                // point previous's next pointer at the one after current
                current->prev->next = current->next;

                // also point next's previous pointer to current's prev
                if(current->next != NULL) {
                    current->next->prev = current->prev;
                } else {
                    tail = current->prev;
                }
            }

            // delete node and leave
            delete current;
            return;
        }

        // move on to the next one
        current = current->next;
    }

    // if we got here we didn't find it!
    cout << value << " was not found in the list!" << endl;
}

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.