Understanding and implementing a doubly linked list will be much easier if one understands the concept of a single linked list. If you haven’t read my previous post on the single linked list, I recommend you to do that.

In this post, I will only highlight the difference between a single and doubly linked list, and at the end of the post, I will give the link of the complete code.

In a single linked list, we have uni-directional links, i.e. each node (containing data) has a link to the next node. But in a doubly linked list, a node has three parts.

1. Data
2. A link to the next node.
3. A link to the previous node.

A link to the previous node allows us to traverse the list in the backward direction. It should be clear by now that a doubly linked list is bi-directional and along with the head, we should also keep track of the tail. Since traversing in the backward direction is possible, we can go from the tail node to head using the previous links.

Let’s see some codes now.

The constructor function of the node:

``````  1 function Node (data) {
2   this.data = data;
3   this.next = null;
4   this.prev = null;
5 }``````

The constructor function of the doubly linked list:

`````` 1 function LinkedList () {
3   this.tail = null;
4   this.length = 0;
5 }``````

Things to remember:

While adding the node to the list we have to follow these steps, considering the following list:

A <=> B <=> D <=> E <=> F ->null

1. Create the node (C) and assign the data [we are adding it between B and D].
2. The next and previous links will be pointing to null initially.
3. Traverse to D (the given position), then look back (using the previous node) or,
• B -> C (C to next of B)
• C -> D (D to next of C)
• B <- C (B to previous of C)
• C <- D (C to previous of D)

Creating a Head (new node at position 0):

1. If the head does not exist,
• The new node becomes head.
• The new node becomes the tail as well.