Doubly Linked List Explained Tutorial

What Is a Doubly Linked List?

A doubly linked list is a linked list in which every node maintains two references: one reference to the next node and another reference to the previous node. This allows the list to be traversed in both forward and backward directions.

In a singly linked list, a node normally stores its data and a reference to the next node. A doubly linked list adds a prev reference, making navigation in both directions possible.

Structure of a Doubly Linked List

A typical doubly linked list node contains three parts:

Data: The value stored by the node.
Next: A reference to the next node.
Previous: A reference to the previous node.

null ← 10 ⇄ 20 ⇄ 30 → null

The first node has no previous node, so its prev reference is null. The last node has no next node, so its next reference is null.

Doubly Linked List Node

A JavaScript node can be represented with a class containing data, a previous reference, and a next reference.

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

When a new node is created, it is not connected to any other node. Its prev and next references are initially null.

Connecting Doubly Linked List Nodes

When two nodes are connected, both directions should be updated. Suppose first and second are adjacent nodes.

first.next = second;
second.prev = first;

The relationship can then be represented as:

first ⇄ second

Both references are necessary. Updating only one side creates an inconsistent list.

Building a Doubly Linked List

A small doubly linked list can be created by explicitly connecting neighboring nodes.

const first = new Node(10);
const second = new Node(20);
const third = new Node(30);

first.next = second;

second.prev = first;
second.next = third;

third.prev = second;

The resulting structure is:

null ← 10 ⇄ 20 ⇄ 30 → null

Head and Tail

A practical doubly linked list usually maintains both a head and a tail reference. The head points to the first node, while the tail points to the final node.

head
 ↓
10 ⇄ 20 ⇄ 30
          ↑
         tail

Maintaining both references makes insertion at either end efficient and also makes backward traversal straightforward.

Forward Traversal

Forward traversal starts at the head and follows the next references until the end of the list is reached.

function printForward(head) {
  let current = head;

  while (current !== null) {
    console.log(current.data);
    current = current.next;
  }
}

For the list 10 ⇄ 20 ⇄ 30, forward traversal produces:

10
20
30

Backward Traversal

The major advantage of a doubly linked list is that it can be traversed backward without starting from the head. Starting at the tail, the algorithm follows prev references.

function printBackward(tail) {
  let current = tail;

  while (current !== null) {
    console.log(current.data);
    current = current.prev;
  }
}

The same list produces:

30
20
10

Inserting at the Beginning

To insert a node at the beginning, the new node points forward to the current head and the current head points backward to the new node.

const newNode = new Node(5);

newNode.next = head;
head.prev = newNode;
head = newNode;

If the original list is:

10 ⇄ 20 ⇄ 30

inserting 5 at the beginning produces:

5 ⇄ 10 ⇄ 20 ⇄ 30

With a head reference, insertion at the beginning takes O(1) time.

Inserting at the End

When a tail reference is maintained, inserting at the end is also constant time. The new node points backward to the current tail, and the current tail points forward to the new node.

const newNode = new Node(40);

newNode.prev = tail;
tail.next = newNode;
tail = newNode;

The resulting list is:

10 ⇄ 20 ⇄ 30 ⇄ 40

Inserting Between Two Nodes

Inserting into the middle of a doubly linked list requires updating four references. Suppose newNode needs to be inserted between current and current.next.

const nextNode = current.next;

newNode.prev = current;
newNode.next = nextNode;

current.next = newNode;
nextNode.prev = newNode;

For example:

Before:

10 ⇄ 20 ⇄ 40

Insert 30:

10 ⇄ 20 ⇄ 30 ⇄ 40

The important difference from a singly linked list is that both forward and backward connections must be maintained.

Deleting the First Node

Deleting the first node means moving the head to the next node and clearing the new head's prev reference.

head = head.next;

if (head !== null) {
  head.prev = null;
}

If the list contained only one node, the deletion should leave both head and tail as null.

Deleting the Last Node

Because the tail is directly available, deleting the last node does not require traversing the entire list.

tail = tail.prev;

if (tail !== null) {
  tail.next = null;
}

With a maintained tail reference, deleting the last node takes O(1) time.

Deleting a Known Middle Node

If the node to remove is already known, its previous and next nodes can be connected directly.

const previous = current.prev;
const next = current.next;

if (previous !== null) {
  previous.next = next;
}

if (next !== null) {
  next.prev = previous;
}

The target node is effectively removed from the chain because no remaining node points to it.

Complete Doubly Linked List Implementation

The following implementation supports insertion at both ends, deletion from both ends, searching, and forward and backward traversal.

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

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

  insertAtBeginning(data) {
    const newNode = new Node(data);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.size++;
  }

  insertAtEnd(data) {
    const newNode = new Node(data);

    if (this.tail === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.size++;
  }

  deleteFirst() {
    if (this.head === null) {
      return;
    }

    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }

    this.size--;
  }

  deleteLast() {
    if (this.tail === null) {
      return;
    }

    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }

    this.size--;
  }

  find(data) {
    let current = this.head;

    while (current !== null) {
      if (current.data === data) {
        return current;
      }

      current = current.next;
    }

    return null;
  }

  printForward() {
    const values = [];
    let current = this.head;

    while (current !== null) {
      values.push(current.data);
      current = current.next;
    }

    console.log(values.join(' ⇄ '));
  }

  printBackward() {
    const values = [];
    let current = this.tail;

    while (current !== null) {
      values.push(current.data);
      current = current.prev;
    }

    console.log(values.join(' ⇄ '));
  }
}

const list = new DoublyLinkedList();

list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtBeginning(10);
list.insertAtEnd(40);

list.printForward();
list.printBackward();

list.deleteFirst();
list.deleteLast();

list.printForward();

The list initially becomes:

10 ⇄ 20 ⇄ 30 ⇄ 40

After deleting the first and last nodes, the remaining list is:

20 ⇄ 30

Doubly Linked List Complexity

Operation	Time Complexity	Notes
Insert at beginning	O(1)	Head reference is available
Insert at end	O(1)	Tail reference is maintained
Delete first	O(1)	Head is updated directly
Delete last	O(1)	Tail is updated directly
Search	O(n)	Nodes may need to be traversed
Delete known node	O(1)	Previous and next nodes are directly available

Doubly Linked List vs Singly Linked List

The main difference is the number of references stored by each node. A singly linked list only knows about the next node, while a doubly linked list maintains both neighboring directions.

Feature	Singly Linked List	Doubly Linked List
Node references	Next	Previous and next
Forward traversal	Yes	Yes
Backward traversal	Not directly	Yes
Memory per node	Lower	Higher
Reference updates	Fewer	More

Advantages of a Doubly Linked List

Supports traversal in both forward and backward directions.
Provides direct access to the previous node from the current node.
Deletion of a known node can be performed without separately searching for its previous node.
Insertion and deletion at both ends can be efficient when head and tail are maintained.
Useful for applications that need navigation in both directions.

Limitations of a Doubly Linked List

Each node requires an additional prev reference.
Insertion and deletion require more reference updates than a singly linked list.
There is no direct random access by index.
Incorrect reference updates can break either the forward or backward chain.

Common Applications

Doubly linked lists are useful when an application needs to move in both directions or frequently insert and remove elements from a sequence.

Browser history navigation.
Undo and redo functionality.
Music or media playlist navigation.
Navigation between recently visited items.
LRU cache implementations.
Deque implementations.

Common Implementation Mistakes

Updating next without updating the corresponding prev reference.
Forgetting to set the head's prev to null.
Forgetting to set the tail's next to null.
Failing to update both head and tail when the list becomes empty.
Using a stale reference after deleting a node.
Incorrectly connecting neighboring nodes during middle insertion or deletion.

A Reliable Reference Pattern

When inserting or deleting a node in the middle of a doubly linked list, think about both directions. For a node inserted between previous and next, the connections should become:

previous ⇄ newNode ⇄ next

That means four references may need to be updated:

previous.next = newNode;
newNode.prev = previous;

newNode.next = next;
next.prev = newNode;

Thinking in terms of both directions helps prevent partially connected lists.

Doubly Linked Lists in Interviews

Doubly linked lists are frequently used in interview questions involving navigation, insertion, deletion, caches, deques, and bidirectional traversal. A common expectation is that you can correctly update both prev and next references.

When solving a doubly linked list problem, identify the neighboring nodes first, then update the forward and backward connections together. Always consider empty-list and single-node cases separately.

Key Takeaways

A doubly linked list stores both previous and next references.
It supports forward and backward traversal.
Maintaining head and tail makes insertion and deletion at both ends efficient.
Deleting a known node can be performed in O(1) time.
Searching still requires O(n) time because there is no direct random access.
Doubly linked lists use more memory than singly linked lists because of the additional reference.
Every insertion and deletion must keep both directions consistent.

Topics

Doubly Linked List Explained