Doubly Linked List Implementation Guide | Data Structures

July 21, 2017 0 Comments

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?

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

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.

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.

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.

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).

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

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;

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

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;

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

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;

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.

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

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;

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

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;

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.

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;

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.

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


Tag cloud