Doubly Linked List Using JavaScript

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 = data;
  3 = null;
  4   this.prev = null;
  5 }

The constructor function of the doubly linked list:

 1 function LinkedList () {
 2   this.head = null;
 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.
  2. If the head is already present,
    • Keep a reference for the existing head (X).
    • The new node becomes the new head.
    • The new node’s next becomes the old head (X).
    • The old head’s previous link becomes the new head.

Deleting a node at any position can be achieved using similar algorithms. All we need to do is to keep track of both the next and previous links while adding a new node otherwise the chain will break.

Link: Doubly linked list