Data Structure: Doubly Linked List

A Doubly linked list is similar to a Singly Linked List, but it holds reference to the previous node also. So we can traverse both forward and backward from any node.

NOTE

In this article, we are discussing in detail, the implementation of Doubly Linked List in JavaScript and TypeScript.

Check the link below to check the details of Linked List and doubly Linked List-

Linked List Details

Doubly Linked List Details

Implementation

Here is the detailed implementation of Doubly Linked List in JavaScript and TypeScript, step-by-step –

Step #1: Node Class

Let’s create a node class, to represent a single Node. This class has field for data and for the next, previous nodes.

Create a class named “Node”.

Define a constructor and accept “data”.

In the constructor set data.

Set “next” and “previous” field to null.

JavaScript
TypeScript

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.previous = null;
  }
}

Step #2: Doubly Linked List Class

Now let’s create a class for the Doubly Linked List. Initially it will be as below.

Create a class “DoublyLinkedList”.

In the constructor set field “head” to null, “tail” to null, and “length” to 0(zero).

JavaScript
TypeScript

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

NOTE

For TypeScript we are using a generic and passing the type as <T>. We need to pass this type <T> to the “Node” item.

Step #3: Push (Node to the end)

Check the step by step implementation of the Push method of a Dobuly Linked List.

Create method “push”.

Accept “data” as parameter.

Create a new Node from this “data“.

If head(or tail) is not present then make this new “Node” as head, and also tail. As this is the only one node present in the list.

If there is head and tail already present in the list, then we have to add this node to the end.

Set previous of the new node to the current tail.

Set “next” of the current tail to the new node.

And finally make this new node as tail.

JavaScript

TypeScript

class DoublyLinkedList {
  // ...
  
  // Push item to the end of Doubly Linked List
  push(data) {
    const node = new Node(data);

    // If the list is empty
    // then make this node as head and tail
    // Or you can check if the length==0 here
    if (!this.head) {
      this.head = node;
    } else {
      // set the current tail's next value to new node
      node.previous = this.tail;
      this.tail.next = node;
    }

    // Set the tail to this new node
    this.tail = node;

    // Increase the length by 1
    this.length++;

    // Return the DoublyLinkedList
    return this;
  }

  // ...
}

Step #4: Pop (Last Node)

Here are the steps to follow for popping a node from a Doubly Linked List.

If tail not present then return “undefined”.

The current tail is the item we want to pop.

If there is only one element then return that. and make the “head” and “tail” null. Also make sure to make the “length” as null.

Move the tail to the “previous” of the current tail, and make the “next” of this new tail as null.

Decrease the length by one.

JavaScript

TypeScript

class DoublyLinkedList {
  // ...
  
  // Pop item from the end of the list
  pop() {
    if (!this.tail) {
      return undefined;
    }

    // Get the list item as popped item
    let poppedItem = this.tail;

    // Check if list has only one item
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      // Set the second last item as tail
      this.tail = poppedItem.previous;
      this.tail.next = null;

      // Reset the previous point of the popped item
      // Then next point should already be null
      poppedItem.previous = null;
    }

    // Decrease the length
    this.length--;

    return poppedItem;
  }

  // ...
}

Step #5: Shift Head

In this method we want to shift an item from the left.

If there is no “head” (or “tail”) then return undefinded.

Current “head” is the item we want to return, so save it in a variable.

Make the “next” of the current “head” as new “head”.

Make the “previous” of the new “head” as null.

Finally decrease the length by one.

JavaScript

TypeScript

class DoublyLinkedList {
  // ...
  
  // Shift node form the begingin
  shift() {
    if (!this.head) {
      return undefined;
    }

    let shiftedItem = this.head;

    // Check if list has only one item
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      // Set the second last item as tail
      this.head = shiftedItem.next;
      this.head.previous = null;

      // Reset the previous point of the popped item
      // Then next point should already be null
      shiftedItem.next = null;
    }

    // Decrease the length
    this.length--;

    return shiftedItem;
  }

  // ...
}

Step #6: Unshift Head

For unshift our goal is to create a new node and make this new node as head.

Create function “unshift” and accept “data” as parameter.

Create a new Node from “data”.

Make the “next” of new node to the current “head”.

Point the “prevous” of current head to the new node.

Make this new node as head.

JavaScript

TypeScript

class DoublyLinkedList {
  // ...
  
  // Unshift item to the begining of Doubly Linked List
  unshift(data) {
    const node = new Node(data);

    // If the list is empty
    // then make this node as head and tail
    // Or you can check if the length==0 here
    if (!this.head) {
      this.tail = node;
    } else {
      // set the current tail's next value to new node
      node.next = this.head;
      this.head.previous = node;
    }

    // Set the tail to this new node
    this.head = node;

    // Increase the length by 1
    this.length++;

    // Return the DoublyLinkedList
    return this;
  }

  // ...
}

Step #7: Get by Index

If the index is in the first half then start from the “head” and move forward.

If the index is in last half then start from the “tail” and come backward.

Go through the nodes one by one.

Return the node when reach the node at specified index.

JavaScript
TypeScript

class DoublyLinkedList {
  // ...
  
  // Get item by index
  get(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    let currentNode, currentIndex;

    // Start from the head if index is in the first half
    if (index <= this.length / 2) {
      currentNode = this.head;
      currentIndex = 0;

      while (currentIndex < index) {
        currentNode = currentNode.next;
        currentIndex++;
      }
    } else {
      // Start from the tail if index is in the second half
      currentNode = this.tail;
      currentIndex = this.length - 1;

      while (currentIndex > index) {
        currentNode = currentNode.previous;
        currentIndex--;
      }
    }

    return currentNode;
  }

  // ...
}

Step #8: Set Data by Index

Get the node by index using the “get” method of this class.

Set the “data” field of this node.

JavaScript
TypeScript

class DoublyLinkedList {
  // ...
  
  // Set the value of a specific node by index
  set(index, data) {
    let node = this.get(index);

    if (node) {
      node.data = data;
    }

    return node;
  }

  // ...
}

Step #9: Insert New Node at Index

Create method named “insert”.

Accept an “index” and “data” as parameter.

Create a new node from “data”.

Get the item at the specified index and insert this newly created node, by changing the “next” and “previous” pointers.

JavaScript

TypeScript

class DoublyLinkedList {
  // ...
  
  // Insert the value at specivic index
  insert(index, data) {
    // Check if index is out of range
    if (index < 0 || index > this.length) {
      return false;
    }

    // If index==0 then unshift(add to the begining)
    if (index === 0) {
      return this.unshift(data);
    }

    // if index==length then push(to the end)
    if (index === this.length) {
      return this.push(data);
    }

    // Create a new node
    const node = new Node(data);
    let nodeAtIndex = this.get(index);

    node.next = nodeAtIndex;
    node.previous = nodeAtIndex.previous;

    node.previous.next = node;
    nodeAtIndex.previous = node;

    this.length++;

    return node;
  }

  // ...
}

Step #10: Remove Node from Index

Use the “get” method to get the item a specific index.

Link the nodes to it’s left and right.

Return the node that we got at the specific index.

JavaScript
TypeScript

class DoublyLinkedList {
  // ...
  
  // Remove node at an specific index
  remove(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    if (index === 0) {
      return this.shift();
    }

    if (index === this.length - 1) {
      return this.pop();
    }


    const node = this.get(index);

    node.next.previous = node.previous;
    node.previous.next = node.next;

    node.next = null;
    node.previous = null;
    this.length--;
    
    return node;
  }

  // ...
}

Full Implementation Code

Here is the full implementation of Doubly Linked List, with all the functionality.

JavaScript
TypeScript

// dll.js
// Doubly linked list in JavaScript

// Node class for storing data and reference to the next node
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.previous = null;
  }
}

// Doubly Linked List class
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Push item to the end of Doubly Linked List
  push(data) {
    const node = new Node(data);

    // If the list is empty
    // then make this node as head and tail
    // Or you can check if the length==0 here
    if (!this.head) {
      this.head = node;
    } else {
      // set the current tail's next value to new node
      node.previous = this.tail;
      this.tail.next = node;
    }

    // Set the tail to this new node
    this.tail = node;

    // Increase the length by 1
    this.length++;

    // Return the DoublyLinkedList
    return this;
  }

  // Pop item from the end of the list
  pop() {
    if (!this.tail) {
      return undefined;
    }

    // Get the list item as popped item
    let poppedItem = this.tail;

    // Check if list has only one item
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      // Set the second last item as tail
      this.tail = poppedItem.previous;
      this.tail.next = null;

      // Reset the previous point of the popped item
      // Then next point should already be null
      poppedItem.previous = null;
    }

    // Decrease the length
    this.length--;

    return poppedItem;
  }

  // Shift node form the begingin
  shift() {
    if (!this.head) {
      return undefined;
    }

    let shiftedItem = this.head;

    // Check if list has only one item
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      // Set the second last item as tail
      this.head = shiftedItem.next;
      this.head.previous = null;

      // Reset the previous point of the popped item
      // Then next point should already be null
      shiftedItem.next = null;
    }

    // Decrease the length
    this.length--;

    return shiftedItem;
  }

  // Unshift item to the begining of Doubly Linked List
  unshift(data) {
    const node = new Node(data);

    // If the list is empty
    // then make this node as head and tail
    // Or you can check if the length==0 here
    if (!this.head) {
      this.tail = node;
    } else {
      // set the current tail's next value to new node
      node.next = this.head;
      this.head.previous = node;
    }

    // Set the tail to this new node
    this.head = node;

    // Increase the length by 1
    this.length++;

    // Return the DoublyLinkedList
    return this;
  }

  // Get item by index
  get(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    let currentNode, currentIndex;

    // Start from the head if index is in the first half
    if (index <= this.length / 2) {
      currentNode = this.head;
      currentIndex = 0;

      while (currentIndex < index) {
        currentNode = currentNode.next;
        currentIndex++;
      }
    } else {
      // Start from the tail if index is in the second half
      currentNode = this.tail;
      currentIndex = this.length - 1;

      while (currentIndex > index) {
        currentNode = currentNode.previous;
        currentIndex--;
      }
    }

    return currentNode;
  }

  // Set the value of a specific node by index
  set(index, data) {
    let node = this.get(index);

    if (node) {
      node.data = data;
    }

    return node;
  }

  // Insert the value at specivic index
  insert(index, data) {
    // Check if index is out of range
    if (index < 0 || index > this.length) {
      return false;
    }

    // If index==0 then unshift(add to the begining)
    if (index === 0) {
      return this.unshift(data);
    }

    // if index==length then push(to the end)
    if (index === this.length) {
      return this.push(data);
    }

    // Create a new node
    const node = new Node(data);
    let nodeAtIndex = this.get(index);

    node.next = nodeAtIndex;
    node.previous = nodeAtIndex.previous;

    node.previous.next = node;
    nodeAtIndex.previous = node;

    this.length++;

    return node;
  }

  // Remove node at an specific index
  remove(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    if (index === 0) {
      return this.shift();
    }

    if (index === this.length - 1) {
      return this.pop();
    }


    const node = this.get(index);

    node.next.previous = node.previous;
    node.previous.next = node.next;

    node.next = null;
    node.previous = null;
    this.length--;
    
    return node;
  }
}

export default DoublyLinkedList;

Demo

Here is the demo code for using the implemented functionality of Doubly Linked List-

JavaScript
TypeScript

// linked-list/doubly-linked-list/demo.js
import DoublyLinkedList from "./dll.js";

// Create a Doubly Linked List
let bigboxList = new DoublyLinkedList();

console.log("\n\n----------- Doubly Linked List - Push example -----------\n");

console.log('Push - "Big" | Result: ', bigboxList.push("Big"));
console.log('Push - "Box" | Result: ', bigboxList.push("Box"));
console.log('Push - "Code" | Result: ', bigboxList.push("Code"));

console.log("\n\n----------- Doubly Linked List - Pop example -----------\n");

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log(
  "\n\n----------- Doubly Linked List - Shifted example -----------\n"
);

bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");

console.log("Shifted Item: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log("Shifted Item: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log("Shifted Item: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log("Shifted Item: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log(
  "\n\n----------- Doubly Linked List - Unshift example -----------\n"
);

console.log('Unshift - "Code" | Result: ', bigboxList.unshift("Code"));
console.log('Unshift - "Box" | Result: ', bigboxList.unshift("Box"));
console.log('Unshift - "Big" | Result: ', bigboxList.unshift("Big"));

console.log("\n\n----------- Doubly Linked List - Get example -----------\n");

console.log("Get index 0 | Result: ", bigboxList.get(0));
console.log("Get index 1 | Result: ", bigboxList.get(1));
console.log("Get index 2 | Result: ", bigboxList.get(2));


console.log("\n\n----------- Doubly Linked List - Set example -----------\n");

console.log("Set 'abc' index 0 | Result: ", bigboxList.set(0, 'abc'));
console.log("Set 'BB' index 10 | Result: ", bigboxList.set(10, 'BB'));

console.log("List after set: ", bigboxList);

console.log("\n\n----------- Doubly Linked List - Insert example -----------\n");

console.log("Insert 'New Insert 1' at index 1 | Result: ", bigboxList.insert(1, 'New Insert 1'));
console.log("Insert 'New Insert 99' at index 99 | Result: ", bigboxList.insert(99, 'New Insert 99'));


console.log("\n\n----------- Doubly Linked List - Remove example -----------\n");

console.log("Remove  at index 1 | Result: ", bigboxList.remove(1));
console.log("Remove at index 99 | Result: ", bigboxList.remove(99));

console.log("List after remove: ", bigboxList);

Output:

----------- Doubly Linked List - Push example -----------

Push - "Big" | Result:  DoublyLinkedList {
  head: Node { data: 'Big', next: null, previous: null },
  tail: Node { data: 'Big', next: null, previous: null },
  length: 1
}
Push - "Box" | Result:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'Big',
    next: Node { data: 'Box', next: null, previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Box',
    next: null,
    previous: <ref *1> Node {
      data: 'Big',
      next: [Circular *2],
      previous: null
    }
  },
  length: 2
}
Push - "Code" | Result:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'Big',
    next: Node { data: 'Box', next: [Node], previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Code',
    next: null,
    previous: Node { data: 'Box', next: [Circular *2], previous: [Node] }
  },
  length: 3
}


----------- Doubly Linked List - Pop example -----------

Popped Item:  Node { data: 'Code', next: null, previous: null }
List value:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'Big',
    next: Node { data: 'Box', next: null, previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Box',
    next: null,
    previous: <ref *1> Node {
      data: 'Big',
      next: [Circular *2],
      previous: null
    }
  },
  length: 2
}
Popped Item:  Node { data: 'Box', next: null, previous: null }
List value:  DoublyLinkedList {
  head: Node { data: 'Big', next: null, previous: null },
  tail: Node { data: 'Big', next: null, previous: null },
  length: 1
}
Popped Item:  Node { data: 'Big', next: null, previous: null }
List value:  DoublyLinkedList { head: null, tail: null, length: 0 }
Popped Item:  undefined
List value:  DoublyLinkedList { head: null, tail: null, length: 0 }


----------- Doubly Linked List - Shifted example -----------

Shifted Item:  Node { data: 'Big', next: null, previous: null }
List value:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'Box',
    next: Node { data: 'Code', next: null, previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Code',
    next: null,
    previous: <ref *1> Node {
      data: 'Box',
      next: [Circular *2],
      previous: null
    }
  },
  length: 2
}
Shifted Item:  Node { data: 'Box', next: null, previous: null }
List value:  DoublyLinkedList {
  head: Node { data: 'Code', next: null, previous: null },
  tail: Node { data: 'Code', next: null, previous: null },
  length: 1
}
Shifted Item:  Node { data: 'Code', next: null, previous: null }
List value:  DoublyLinkedList { head: null, tail: null, length: 0 }
Shifted Item:  undefined
List value:  DoublyLinkedList { head: null, tail: null, length: 0 }


----------- Doubly Linked List - Unshift example -----------

Unshift - "Code" | Result:  DoublyLinkedList {
  head: Node { data: 'Code', next: null, previous: null },
  tail: Node { data: 'Code', next: null, previous: null },
  length: 1
}
Unshift - "Box" | Result:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'Box',
    next: Node { data: 'Code', next: null, previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Code',
    next: null,
    previous: <ref *1> Node {
      data: 'Box',
      next: [Circular *2],
      previous: null
    }
  },
  length: 2
}
Unshift - "Big" | Result:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'Big',
    next: Node { data: 'Box', next: [Node], previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Code',
    next: null,
    previous: Node { data: 'Box', next: [Circular *2], previous: [Node] }
  },
  length: 3
}


----------- Doubly Linked List - Get example -----------

Get index 0 | Result:  <ref *2> Node {
  data: 'Big',
  next: <ref *1> Node {
    data: 'Box',
    next: Node { data: 'Code', next: null, previous: [Circular *1] },
    previous: [Circular *2]
  },
  previous: null
}
Get index 1 | Result:  <ref *1> Node {
  data: 'Box',
  next: Node { data: 'Code', next: null, previous: [Circular *1] },
  previous: Node { data: 'Big', next: [Circular *1], previous: null }
}
Get index 2 | Result:  <ref *1> Node {
  data: 'Code',
  next: null,
  previous: <ref *2> Node {
    data: 'Box',
    next: [Circular *1],
    previous: Node { data: 'Big', next: [Circular *2], previous: null }
  }
}


----------- Doubly Linked List - Set example -----------

Set 'abc' index 0 | Result:  <ref *2> Node {
  data: 'abc',
  next: <ref *1> Node {
    data: 'Box',
    next: Node { data: 'Code', next: null, previous: [Circular *1] },
    previous: [Circular *2]
  },
  previous: null
}
Set 'BB' index 10 | Result:  undefined
List after set:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'abc',
    next: Node { data: 'Box', next: [Node], previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Code',
    next: null,
    previous: Node { data: 'Box', next: [Circular *2], previous: [Node] }
  },
  length: 3
}


----------- Doubly Linked List - Insert example -----------

Insert 'New Insert 1' at index 1 | Result:  <ref *2> Node {
  data: 'New Insert 1',
  next: <ref *1> Node {
    data: 'Box',
    next: Node { data: 'Code', next: null, previous: [Circular *1] },
    previous: [Circular *2]
  },
  previous: Node { data: 'abc', next: [Circular *2], previous: null }
}
Insert 'New Insert 99' at index 99 | Result:  false


----------- Doubly Linked List - Remove example -----------

Remove  at index 1 | Result:  Node { data: 'New Insert 1', next: null, previous: null }       
Remove at index 99 | Result:  undefined
List after remove:  DoublyLinkedList {
  head: <ref *1> Node {
    data: 'abc',
    next: Node { data: 'Box', next: [Node], previous: [Circular *1] },
    previous: null
  },
  tail: <ref *2> Node {
    data: 'Code',
    next: null,
    previous: Node { data: 'Box', next: [Circular *2], previous: [Node] }
  },
  length: 3
}

Testing

Let’s test the functionality using automated testing. Use the following code for testing.

JavaScript

TypeScript

// dll.test.js
import { describe, it, beforeEach, expect } from "vitest";
import DoublyLinkedList from "./dll";

describe("DoublyLinkedList", () => {
  describe("Push item to DoublyLinkedList", () => {
    let doublyLinkedList;

    beforeEach(() => {
      doublyLinkedList = new DoublyLinkedList();
    });

    it("Should have correct head and tail", () => {
      // Initially head and tails should be null
      expect(doublyLinkedList.head).toBeNull();
      expect(doublyLinkedList.tail).toBeNull();

      doublyLinkedList.push("Big");

      expect(doublyLinkedList.head.data).toBe("Big");
      expect(doublyLinkedList.tail.data).toBe("Big");

      doublyLinkedList.push("Box");
      doublyLinkedList.push("Code");

      expect(doublyLinkedList.head.data).toBe("Big");
      expect(doublyLinkedList.tail.data).toBe("Code");
    });

    it("Should have correct length", () => {
      expect(doublyLinkedList.length).toBe(0);

      doublyLinkedList.push("Big");

      expect(doublyLinkedList.length).toBe(1);

      doublyLinkedList.push("Box");

      expect(doublyLinkedList.length).toBe(2);

      doublyLinkedList.push("Code");

      expect(doublyLinkedList.length).toBe(3);
    });

    it("Should point to the correct node", () => {
      doublyLinkedList.push("Big");

      expect(doublyLinkedList.head.next).toBeNull();
      expect(doublyLinkedList.head.previous).toBeNull();

      doublyLinkedList.push("Box");

      expect(doublyLinkedList.head.next).not.toBeNull();
      expect(doublyLinkedList.head.next.data).toBe("Box");
      expect(doublyLinkedList.head.previous).toBeNull();

      expect(doublyLinkedList.tail.next).toBeNull();
      expect(doublyLinkedList.tail.previous).not.toBeNull();
      expect(doublyLinkedList.tail.previous.data).toBe("Big");

      doublyLinkedList.push("Code");

      expect(doublyLinkedList.head.next).not.toBeNull();
      expect(doublyLinkedList.head.next.data).toBe("Box");
      expect(doublyLinkedList.head.previous).toBeNull();

      expect(doublyLinkedList.tail.next).toBeNull();
      expect(doublyLinkedList.tail.previous).not.toBeNull();
      expect(doublyLinkedList.tail.previous.data).toBe("Box");
    });
  });
});

Time Complexity

The time complexity of operation on a Doubly Linked List is as below-

Operation	Complexity
Insertion	O(1)
Removal	O(1)
Search	O(N)
Access element	O(N)

Source Code

Use the following links to get the source code used in this article-

Source Code of	Implementation Code	Demo Code	Test Code
JavaScript Implementation	GitHub	GitHub	GitHub
TypeScript Implementation	GitHub	GitHub	GitHub

Related Data Structures

Command	Details
Singly Linked List	Singly Linked List Detail

Other Code Implementations

Use the following links to check the Doubly Link List implementation in other programming languages-