Types

Doubly Linked List

Doubly Linked List

A doubly linked list gives every node two pointers instead of one: one pointing forward to the next node, and one pointing backward to the previous node. That extra backward link is what lets you walk the list in either direction.

Because both a head and tail pointer are kept, you get O(1) access at either end. The chain of "next" pointers reads the list forward, while the chain of "previous" pointers reads it backward.

The tradeoff is straightforward: you pay for an extra pointer per node in memory, but in exchange you get backward traversal and fast operations at both ends, which a singly linked list can't offer as cheaply.

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

How It Lives in Memory

Like any linked list, a doubly linked list's nodes are scattered across memory rather than sitting in one contiguous block. The chain only exists because of the pointers each node stores, not because of where the nodes physically live.

The difference here is that every node carries two of those pointers instead of one, so the per-node overhead is doubled. In exchange, any node you already hold a reference to can be removed in O(1), because it knows both of its neighbours and can splice itself out without a traversal to find the one behind it.

Basic Operations

OperationComplexityDescription
Insertion at HeadO(1)Add new node at beginning, update head and adjacent node's pointers
Insertion at TailO(1)Add new node at end using tail pointer
Insertion at PositionO(n)Traverse to position and insert with pointer updates
Deletion at HeadO(1)Remove first node and update head pointer
Deletion at TailO(1)Remove last node using tail pointer
Deletion by ValueO(n)Traverse to find node and update adjacent pointers
Forward TraversalO(n)Traverse from head to tail using next pointers
Backward TraversalO(n)Traverse from tail to head using prev pointers

How Does It Work?

Each node below is drawn as its three parts: a prev cell, the data, and a next cell. The grey address under each box is where that node lives in memory, and the pointer cells hold nothing but addresses — prev stores the address of the node behind, next the address of the node ahead. At the two ends there is nothing to point at, so those cells read null. Every pair of neighbours is therefore joined by two links, one running forward along the top and one running back along the bottom, and keeping both correct is the entire job of every operation on this list.

Read across the middle node below: its prev says 0x1A and its next says 0x3C, which are exactly the addresses printed under its two neighbours. The addresses here are made up and kept short so they fit; real ones are far longer but behave identically.

headtailAnull0x2F0x1AB0x1A0x3C0x2FC0x2Fnull0x3C

Insertion Process

Inserting at the head means writing four pointers in total: the new node's prev (null) and next (the old head's address), the old head's prev (the new node's address), and the head pointer itself. Watch A's prev cell below change from null to 0x4D. No traversal is involved, so it runs in O(1).

headtailAnull0x2F0x1AB0x1Anull0x2F

↓ insert X at head ↓

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

Deletion Process

To remove a node, its two neighbours are pointed at each other: X's next is overwritten with the address in A's next (0x2F), and B's prev is overwritten with the address in A's prev (0x4D). Crucially, A already holds both of those addresses in its own cells, so no walk from the head is needed to find the node in front of it — which is exactly what a singly linked list would have to do.

headtailXnull0x1A0x4DA0x4D0x2F0x1AB0x1Anull0x2F

↓ delete A ↓

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

Operation Walkthrough

A full sequence on an empty list, one operation at a time:

Initialization — An empty list is just two null pointers.

headnulltail

insertFirst(10) — The first node is both head and tail, and both of its pointer cells are null.

headtail10nullnull0x1A

insertFirst(20) — The new node's next points at 10, and 10's prev points back at it — one link written in each direction.

headtail20null0x1A0x2F100x2Fnull0x1A

insertLast(30) — Because tail is tracked, the end is reached without walking the list, so this is O(1) rather than O(n).

headtail20null0x1A0x2F100x2F0x3C0x1A300x1Anull0x3C

deleteFirst() — head moves to 10 and 10's prev is set to null. The detached node is now unreachable.

headtail10null0x3C0x1A300x1Anull0x3C

deleteLast() — tail moves back to 10 using 30's prev pointer — the step a singly linked list cannot take without traversing.

headtail10nullnull0x1A

Comparison with Singly Linked List

FeatureSingly Linked ListDoubly Linked List
Traversal DirectionForward onlyBoth directions
Memory OverheadLower (1 pointer/node)Higher (2 pointers/node)
Insert/Delete at HeadO(1)O(1)
Insert/Delete at TailO(n) (or O(1) with tail pointer)O(1)
Delete Current NodeRequires previous nodeDirect access via prev pointer
Implementation ComplexitySimplerMore 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

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

Done With the Learning

Mark Doubly Linked List as done and view it on your dashboard

Explore Other Types

Singly Linked List

Circular Linked List