Doubly Linked List Implementation Guide | Data Structures

The doubly linked list data structure is a linked list made up of nodes with two pointers pointing to the next and previous element.

I will assume that readers are comfortable with the basic singly linked list. If not, I recommend reading about the singly linked list before proceeding.

Let’s get started shall we?

What is a Doubly Linked List?

As I described in the introduction, the doubly linked list is a linked list made up of nodes that have two pointers. These pointers point to the next and previous node.

The doubly linked list is like a

  • Old school disc-man.
  • Train.
  • Minimalist photo gallery slider.

What do all of these examples have in common?

You can only directly access the next or previous node from any given point/node.

Here is a visual representation of the doubly linked list.

doubly linked list illustration

Doubly Linked List Implementation

The only difference between a singly and doubly inked list is in our Node class or object. Instead of having just a single pointer, we have two pointers.

If you already know how to implement a singly linked list, implementing a doubly linked list is as simple as adding an extra pointer to your node.

Okay, this is the end of the tutorial. Kidding!

Before proceeding, I highly recommend, once again, to make sure that you  fully understand how a singly linked list works.

I will assume that you have a decent working knowledge of the singly linked list.

Doubly Linked List Node

Here is a graphic representation of what each doubly linked list node looks like.

doubly linked list node pointer diagram

In contrast to the singly linked list, our doubly linked list node will have two pointers LITERALLY pointing to the next and previous node.

For all linked list implementations, we must have either a head and/or a tail. I will mention this just in case. The head and tail node are the first and last node of a linked list respectively.

So our Node container (in whatever language you program in), will have the following attributes.

  • Data.
  • Next node.
  • Previous node.

Basic Operations

The basic operations that every linked list should support include the following.

  • insert(T data): Insert data to the front/back of the linked list.
  • insertAfter(T data, int index): Insert data after item at a particular index.
  • remove(T data): Search from the start of the list for the passed in data and remove it from the list, if found.
  • remove(int index): Remove data at a specific index.

The size() method is nice to have, but not an absolute must.

Insertion Operation

When inserting a node to the doubly linked list, we now have to worry about two pointers, instead of one. As long you understand the fundamentals of how nodes are linked together, this shouldn’t be too difficult.

If we have a linked list that has both a tail and a head, we gain the advantage of being able to insert to the front and back of the list in O(1) constant time!

For each insertion operation, we need to consider the three cases. These three cases also need to be considered when removing data from the doubly linked list.

  1. Front insertion (inserting a head node).
  2. Back insertion (inserting a tail node).
  3. Middle insertion (inserting a non head/tail node).

Front Insertion

This is almost as identical as what we did in the singly linked list implementation.

  1. Create new node (B).
  2. Check if list is empty (if head equals null, size equals 0, etc.).
    1. If list is empty, set B as the new head and end operation.
    2. Otherwise, perform the following operations.
      1. Set its next node of B to point at current head (A).
      2. Set the prev node pointer of A to point at B. This only needs to be done if elements already exist inside of the list.
      3. Assign the newly created node (B) as the new head.
      4. Set prev node of B to null.

The ultimately goal is to achieve the link shown in the diagram below. The steps described above are one way to ensure that this happens. If you figure out an alternative method to establishing the link, then by all means, feel free to implement it your way.

Note also that in some languages such as Java, by not assigning a value, the default value is null.

inserting data to front of doubly linked list

Front Insertion Pseudo Code

Here is the first pseudo code example. I have tried to write out all the logic inside of a single method so that we don’t have to jump back and forth from multiple method calls (at least until we understand the basics).

begin insertAtFront(data):
    if head is null:
        head = new Node(data);
        // Tail and head cannot point at the same node
        tail = null;
    else:
        if tail is null:
            tail = new Node(data);
            // Update references
            // Head --> Tail
            // Head <-- Tail
            head.setNext(tail)
            tail.setPrev(head)
        else:
            Node<T> prevHead = head;
            Node<T> newHead = new Node(data);

            // Update references
            // newHead.next --> prevHead
            // prevHead.prev <-- newHead
            newHead.setNext(prevHead)
            prevHead.setPrev(newHead)
            head = newHead
        end if else;
    end if else;
    increment size
end insertAtFront;

Back Insertion

The back insertion mirrors the front insertion.

  1. Create new node (C).
  2. Check if list is empty.
    • If head is empty
      1. set C as the new head. Existence of head node indicates that there are elements in the list (well, at least for this implementation).
    • Otherwise, check if tail is null.
      • If tail is null
        1. Set next node pointer of current head (B) to point to new node (C).
        2. Set prev node pointer of new node (C) to point at current head (B).
      • Otherwise,
        1. Set the prev node of C to point at current tail (B).
        2. Set the next node of B to point at new node (C).
    • Assign the newly created node (C) as the new tail.
    • Set next node of C to null.

Once again, this is one method of performing the back insertion operation. If you find another way that works for you, great! The whole point of this example is to get you thinking and to translate our linked list theory into actual code.

inserting data to back of doubly linked list

Back Insertion Pseudo Code

Let’s take a look at what all of this logic will look like in pseudo code. Note that the logic almost mirrors that of the front insertion. The only difference between the two is how we handle the reference updates when inserting a head and tail node.

Comparing the two examples will help you wrap your mind around the difference and solidify your working knowledge of the doubly linked list.

begin insertAtBack(T dataToInsert):
    // First element.     
    if head is null:
        nodeToInsert = new Node(dataToInsert)
        head = nodeToInsert
        // Tail and head cannot point at the same node
        tail = null
    else:
        // Second element to add to list
        if tail is null:
            tail = new Node(dataToInsert)
            // Update references
            // Head --> Tail
            // Head <-- Tail
            head.setNext(this.tail)
            tail.setPrev(this.head)
        else: 
            prevTail = tail
            newTail  = new Node(dataToInsert)

            // Update references
            // prevTail --> newTail
            // prevTail <-- newTail
            newTail.setPrev(prevTail)
            prevTail.setNext(newTail)
            tail = newTail
        end if else;
    end if else;
    increment size
end insertAtBack;

Middle Insertion

In the middle insertion, we need to perform the following operations. While walking through the middle insertion operation, please refer to the diagram below.

First of all, we need to create the new node (C).

Then, we need to iterate through the linked list and find the place where we need to insert our node. Be sure to handle possible errors such as user inserted index being out of range.

Afterwards, we need to update the pointers for the following nodes.

  1. Newly added node (C).
    • Set next node pointer of C to point at B.
    • Set prev node pointer of C to point at A.
  2. Previous Node (A).
    • Set next node pointer of A to point at C.
  3. Next Node (B).
    • Set prev node pointer of B to point at C.

adding data to doubly linked list

Middle Insertion Pseudo Code

Here is the pseudo code for the middle insertion, which is pretty much inserting data based on index. In this implementation, for the sake of simplicity, we will begin iterating from the start of the linked list (the head) until we reach the desired index at which to insert the data.

As a challenge, I recommend you to implement a version that inspects whether it is faster to iterate from the head or tail and choose the most optimal path. I have included this version in the source code, but try it on your own before looking at the solutions.

begin insertAfter(data, index):
    if index is less than size - 1:
        // Handle error here
    end if;
    // Get node at a specific index
    currentNode = head;
    counter = 0;

    // Iterate from the front of the list
    while currentNode is not null and counter != index:
        currentNode = currentNode.getNext()
    end while;
    // Add node
    call insertNode(data, currentNode, currentNode.getNext());
end insertAfter;

Below is the pseudo code for the insertNode method.

begin insertNode(dataToInsert, currentNode, nextNode):
    newNode = new Node(dataToInsert)
    // If next node is null, current node is the tail node
    if nextNode is null:
        tail = newNode
        tail.setPrev(currentNode)
        currentNode.setNext(newNode)
    else:
        // update references of existing node
        currentNode.setNext(newNode)
        nextNode.setPrev(newNode)
        // update references of new node
        newNode.setPrev(currentNode)
        newNode.setNext(nextNode)
    end if else;
    increment size
end insertNode;

Remove Operation

In contrast to the singly linked list, because our nodes have two pointers, we have slightly more work to do. If you fully understand the insertion operation in the doubly linked list, the remove operation is very similar.

Therefore, I am going to spend a little less time explaining the same concepts that we went through in the previous section. Try to figure it out on your own. If you ever get stuck, for each operation, I have included some pseudo code to get you back on track.

There are three main cases when removing a node to the doubly linked list. Cases where the node that we are deleting is the

  1. Head.
  2. Tail.
  3. Neither the head or tail. In another word, the node to remove is somewhere in the middle of the list.

Case One: Removing Head

How do we know if the node to remove is the head in a doubly linked list?

The answer is simple: head nodes do not have a previous node pointer. In another word, prev node has a value of null.

If you find it difficult to visualize, try reviewing the previous section. Once you have conceptualized the doubly linked list, the diagram below will make a lot of sense. When we remove the head node, two things are happening.

  1. Set head to null.
  2. Set next node after the head (A) as the new head.
  3. Update A‘s prev pointer value to null.

removing head node in a doubly linked list

Removing Head Pseudo Code

begin removeFromFront():
    if head is not null: {
        nextNode = head.getNext()
        // Set prev node of next to null if it exists
        if nextNode is not null:
            nextNode.setPrev(null)
        end if;
        // Remove current head
        head = null;
        head = nextNode;
        decrement size
    end if;
end removeFromFront;

Case Two: Removing Tail

Removing a tail node mirrors the head removal operation.

  1. Set tail to null.
  2. Set previous node (B) as the new tail.
  3. Update B‘s next node pointer value to null.

In the case that we are removing the last element, we also need to make a check if this is the last element. In our implementation, the tail cannot equal the head. Therefore, if the head node does not equal null but the tail is null, then we are removing the last element.

In this case, all we need to to is remove the head node but setting its reference to null.

removing tail node in a doubly linked list

Removing Tail Pseudo Code

begin removeFromBack():
    if head is not null:
        if tail is not null:
            // Two or more elements exist
            newTail = tail.getPrev()
            tail = null
            newTail.setNext(null)
            tail = newTail
        else:
            // Tail is null but head is not null
            // means that this is the last element
            head = null
        end if else;

        decrement size

    end if;
end removeFromBack;

Case Three: Removing from the middle of the list.

This is probably the most complex case out of the three, because we now have to work with three nodes:

  1. Previous node.
  2. Next node.
  3. Node to remove.

Removing a node from the linked list is not as complicated as inserting an item into the middle of the list. If you got that, this should be a cakewalk.

remove from middle of a doubly linked list

We need to update the following pointers.

  • Next node pointer of A. This should be updated to point to C.
  • Prev node pointer of C. This should be updated to point to A.

Lastly, we destroy B by setting it to null.

Pseudo Code

Now that we have reviewed all the cases, let’s take a look at the pseudo code for the entire remove operation.

Remove operation

begin remove(T dataToRemove):
        currentNode = head
        while current node is not null: 
            currentData = currentNode.data
            if  currentData equals dataToRemove:
                call removeNode(currentNode)
            end if;
            currentNode = currentNode.next
        end while;
end remove;

removeNode operation

begin removeNode(nodeToRemove):
    prevNode = nodeToRemove.prev
    nextNode = nodeToRemove.next
    // Head node does not have a previous node
    if prevNode is null:
        head = null
        head = nextNode
        head.prev = null
    else if nextNode is null:
        // Tail does not have a next node
        tail = null
        tail = prevNode
        tail.next = null
    else:
        // Is somewhere in the middle of the linked list
        // Set current node to null
        nodeToRemove = null
        // connect the previous and next nodes together
        prevNode.next = nextNode
        nextNode.prev = prevNode
    end if else statement;
    decrement size
end removeNode;

Conclusion and Challenge

Now that you understand how the insertion and remove operation works in the doubly linked list, adding extra features such as  add/removing items by index, smart traversal, etc. should be easier.

It is important that you have a solid conceptual understand of these basic data structures before attempting to move onto some of the more complex data structures.

I recommend playing around with the doubly linked list by adding the aforementioned features such as insertion/removal by index. In the source code, I have added these features for your reference.

Here is a list of possible features that you can add to your doubly linked list to get more practice.

  • Batch inserting a list (adding a list to the linked list, as opposed to single elements).
  • An empty function that empties the entire list.
  • A copy constructor (or constructor that converts a different collection into a list).
  • Update your insertAfter(data, index) and removeAt(index) methods to calculate the fastest way of traversing to the node at that index. E.g. If we are removing the second last node in a list of five items, it will start looking from the tail.

Source Code

As always, here is the source code. I have added some of the implementations to the challenges provided above (not all). If you understand how the doubly linked list works, it should only be a matter of time until you get your implementation up and running.

If this post was useful, please share it. And if you have any constructive feedback or requests, please feel free to leave a comment. I will follow up on any comments as soon as possible.

Happy coding guys!

– Jay

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community.

I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.

follow me on:
9 Shares