Shares

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

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.

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.

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.

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

### 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):
// Tail and head cannot point at the same node
tail = null;
else:
if tail is null:
tail = new Node(data);
// Update references
else:

// Update references
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.
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.

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

``````begin insertAtBack(T dataToInsert):
// First element.
nodeToInsert = new Node(dataToInsert)
// 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
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.

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

### 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
counter = 0;

// Iterate from the front of the list
while currentNode is not null and counter != index:
currentNode = currentNode.getNext()
end while;
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

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

``````begin removeFromFront():
if head is not null: {
// Set prev node of next to null if it exists
if nextNode is not null:
nextNode.setPrev(null)
end if;
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 Pseudo Code

``````begin removeFromBack():
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
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.

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