Doubly Linked List

A Doubly Linked List is an advanced variation of the linked list where each node contains data and two pointers - one to the next node and another to the previous node. This bidirectional linkage enables traversal in both directions.

The list maintains head and tail pointers, allowing O(1) operations at both ends. Each node's previous pointer forms the backward chain, while the next pointer forms the forward chain.

Doubly linked lists are particularly useful when you need frequent backward traversal or operations at both ends of the list, providing more flexibility than singly linked lists at the cost of slightly higher memory overhead.

Key Property: Each node is represented as [prev|data|next], showing the bidirectional links between nodes.

Basic Operations

Operation	Complexity	Description
Insertion at Head	O(1)	Add new node at beginning, update head and adjacent node's pointers
Insertion at Tail	O(1)	Add new node at end using tail pointer
Insertion at Position	O(n)	Traverse to position and insert with pointer updates
Deletion at Head	O(1)	Remove first node and update head pointer
Deletion at Tail	O(1)	Remove last node using tail pointer
Deletion by Value	O(n)	Traverse to find node and update adjacent pointers
Forward Traversal	O(n)	Traverse from head to tail using next pointers
Backward Traversal	O(n)	Traverse from tail to head using prev pointers

Implementation

class DoublyNode {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  isEmpty() {
    return this.head === null;
  }
  // Insert at head
  insertFirst(data) {
    const newNode = new DoublyNode(data);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.size++;
  }

Insertion Process

1. Create new node with data, prev, and next pointers
2. For head insertion: Set new node's next to current head
3. Update current head's prev to new node
4. Move head pointer to new node
5. For empty list, set both head and tail to new node
6. For tail insertion: Similar steps but working from tail

head →

[•|A|•] ↔ [•|B|•]

← tail

↓ Insert X at head ↓

head →

[null|X|•] ↔ [•|A|•] ↔ [•|B|•]

← tail

Deletion Process

1. Check if list is empty
2. For head deletion: Store head reference, move head to head.next
3. Set new head's prev to null (if exists)
4. For tail deletion: Similar steps working from tail
5. For middle deletion: Find node, update adjacent nodes' pointers
6. Handle special cases (single node removal)

head →

[•|X|•] ↔ [•|A|•] ↔ [•|B|•]

← tail

↓ Delete A ↓

head →

[•|X|•] ↔ [•|B|•]

← tail

Operation Visualization

Operation	List State
Initialization	head → null ← tail
insertFirst(10)	head → [null\|10\|•] ← tail
insertFirst(20)	head → [null\|20\|•] ↔ [•\|10\|•] ← tail
insertLast(30)	head → [null\|20\|•] ↔ [•\|10\|•] ↔ [•\|30\|null] ← tail
deleteFirst()	head → [null\|10\|•] ↔ [•\|30\|null] ← tail
deleteLast()	head → [null\|10\|null] ← tail

Comparison with Singly Linked List

Feature	Singly Linked List	Doubly Linked List
Traversal Direction	Forward only	Both directions
Memory Overhead	Lower (1 pointer/node)	Higher (2 pointers/node)
Insert/Delete at Head	O(1)	O(1)
Insert/Delete at Tail	O(n) (or O(1) with tail pointer)	O(1)
Delete Current Node	Requires previous node	Direct access via prev pointer
Implementation Complexity	Simpler	More complex

Pros and Cons

Advantages

Bidirectional traversal capability
O(1) operations at both ends
Easier node removal (no need to track previous node)
Better for certain algorithms (e.g., LRU cache)

Limitations

Extra memory for prev pointers
More pointer operations (slightly complex implementation)
Slightly slower operations due to extra pointer updates

Applications

Browser forward/backward navigation
Undo/Redo functionality in software
LRU (Least Recently Used) cache implementation
Navigation systems with bidirectional movement
Music/video playlists with forward/backward controls
Text editors with cursor movement in both directions

When to Choose: Prefer doubly linked lists when you need bidirectional traversal, frequent operations at both ends, or when the ability to delete arbitrary nodes without traversal is valuable.

Visualize Singly Linked List Operations

Node Value

Doubly Linked List Representation

No nodes in the list yet. Add your first node!

Test Your Knowledge before moving forward!

Linked List Quiz Challenge

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Doubly Linked List Implementation

// Doubly Linked List Implementation in JavaScript
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

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

  // Insert at beginning
  insertFirst(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.size++;
  }

  // Insert at end
  insertLast(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  // Insert at index
  insertAt(data, index) {
    if (index < 0 || index > this.size) return;
    if (index === 0) return this.insertFirst(data);
    if (index === this.size) return this.insertLast(data);

    const newNode = new Node(data);
    let current = this.head;
    let count = 0;

    while (count < index) {
      current = current.next;
      count++;
    }

    newNode.prev = current.prev;
    newNode.next = current;
    current.prev.next = newNode;
    current.prev = newNode;
    this.size++;
  }

  // Remove from beginning
  removeFirst() {
    if (!this.head) return null;
    const removedNode = this.head;
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
    this.size--;
    return removedNode.data;
  }

  // Remove from end
  removeLast() {
    if (!this.tail) return null;
    const removedNode = this.tail;
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }
    this.size--;
    return removedNode.data;
  }

  // Remove at index
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    if (index === 0) return this.removeFirst();
    if (index === this.size - 1) return this.removeLast();

    let current = this.head;
    let count = 0;

    while (count < index) {
      current = current.next;
      count++;
    }

    current.prev.next = current.next;
    current.next.prev = current.prev;
    this.size--;
    return current.data;
  }

  // Get at index (forward traversal)
  getAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current = this.head;
    let count = 0;
    while (count < index) {
      current = current.next;
      count++;
    }
    return current.data;
  }

  // Get at index (backward traversal)
  getAtFromEnd(index) {
    if (index < 0 || index >= this.size) return null;
    let current = this.tail;
    let count = 0;
    while (count < index) {
      current = current.prev;
      count++;
    }
    return current.data;
  }

  // Clear list
  clear() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // Print list forward
  printForward() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

  // Print list backward
  printBackward() {
    let current = this.tail;
    while (current) {
      console.log(current.data);
      current = current.prev;
    }
  }
}

// Usage Example
const dll = new DoublyLinkedList();
dll.insertFirst(100);
dll.insertFirst(200);
dll.insertLast(300);
dll.insertAt(500, 1);
dll.printForward(); // 200, 500, 100, 300
dll.printBackward(); // 300, 100, 500, 200
dll.removeAt(2);
console.log(dll.getAt(1)); // 500
console.log(dll.getAtFromEnd(1)); // 100

Explore Other Types

Singly Linked List

Circular Linked List