Doubly Linked List

Overview

A doubly linked list is a linked list where each node has both a next and a prev pointer. This allows traversal in both directions and O(1) removal of a node when you have a reference to it (you only need to update the two neighbors' pointers). It is the basis for many data structures: LRU cache, browser history, and ordered collections that need fast insert/delete at both ends.

Trade-offs: Doubly linked uses more memory (two pointers per node) and requires maintaining both next and prev on every insert/delete. In return you get O(1) delete-by-reference and backward traversal without extra space.

When to Use

• Delete a node when you have a reference — O(1) by rewiring prev and next.
• Traverse backward — e.g. "previous page," "move to previous element."
• LRU cache — Map + doubly linked list for O(1) move-to-front and eviction.
• Flatten multilevel doubly linked list — Child pointers; flatten while keeping prev/next correct.

How It Works

Node structure: { val, prev, next } with prev and next possibly null at the ends.

Insert after a node: Create newNode; set newNode.next = node.next, newNode.prev = node; if node.next exists set node.next.prev = newNode; set node.next = newNode.

Insert before a node: Same idea with prev; or insert after node.prev.

Delete a node: Given node, set node.prev.next = node.next (if prev exists) and node.next.prev = node.prev (if next exists). If using a sentinel head/tail, head and tail are never null so the logic is uniform.

Sentinel head and tail: A dummy head and dummy tail (that point to each other when empty) remove "if head is null" and "if tail is null" branches and make insert/delete at ends the same as in the middle.

Example 1: Delete Node Given Only That Node (O(1))

Problem: You are given a node in a doubly linked list (not the head). Delete it in O(1). Assume prev and next are never null (e.g. sentinel nodes).

function deleteNode(node: DoublyListNode): void {
  node.prev!.next = node.next;
  node.next!.prev = node.prev;
}

• If the list uses sentinel head/tail, prev and next are always non-null for a real node.

Example 2: Insert at Head (With Sentinel)

Problem: Insert a new node at the front. Assume a sentinel head so head.next is the first real node (or null if empty).

function insertAtHead(head: DoublyListNode, val: number): void {
  const node = new DoublyListNode(val);
  node.next = head.next;
  node.prev = head;
  if (head.next) head.next.prev = node;
  head.next = node;
}

Example 3: LRU Cache (Map + Doubly Linked List)

Idea: Map stores key → node. List order = access order (most recent at head). On get: move node to head (remove then insert at head). On put: if exists move to head; else insert at head and evict from tail if over capacity.

class LRUNode {
  key: number; val: number; prev: LRUNode | null; next: LRUNode | null;
  constructor(k: number, v: number) { this.key = k; this.val = v; this.prev = this.next = null; }
}
class LRUCache {
  private map = new Map<number, LRUNode>();
  private cap: number;
  private head = new LRUNode(-1, -1);
  private tail = new LRUNode(-1, -1);
  constructor(capacity: number) {
    this.cap = capacity;
    this.head.next = this.tail; this.tail.prev = this.head;
  }
  private addToHead(node: LRUNode): void {
    node.next = this.head.next; node.prev = this.head;
    this.head.next!.prev = node; this.head.next = node;
  }
  private remove(node: LRUNode): void {
    node.prev!.next = node.next; node.next!.prev = node.prev;
  }
  get(key: number): number {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key)!;
    this.remove(node); this.addToHead(node);
    return node.val;
  }
  put(key: number, value: number): void {
    if (this.map.has(key)) {
      const node = this.map.get(key)!;
      node.val = value; this.remove(node); this.addToHead(node);
      return;
    }
    const node = new LRUNode(key, value);
    this.map.set(key, node); this.addToHead(node);
    if (this.map.size > this.cap) {
      const evict = this.tail.prev!;
      this.remove(evict); this.map.delete(evict.key);
    }
  }
}

Example 4: Flatten Multilevel Doubly Linked List

Problem: Each node may have a child pointer to another list. Flatten so all nodes are in a single doubly linked list (by next/prev). Order: follow next, when a node has child, flatten the child list and insert it after the node, then continue.

Approach: traverse; when you find a node with child, connect node to child head, find the tail of the child list, connect that tail to the original node.next, set child to null. Recursive or iterative (use a stack for "pending next" when going into a child).

Edge Cases

• Empty list — With sentinels, head.next === tail and tail.prev === head.
• Single node — prev and next point to sentinels (or null if no sentinel).
• Delete head/tail — With sentinels, "head" and "tail" are the dummies; you never delete them, only the nodes between.

Common Mistakes

1. Forgetting to update both sides — When inserting or deleting, update both the node's prev and next and the neighbors' prev/next.
2. Order of updates — When deleting, you can do prev.next = next and next.prev = prev in either order. When inserting, set the new node's pointers first, then the neighbors', to avoid losing references.
3. Null checks — Without sentinels, check prev/next for null before dereferencing.

Time and Space Complexity

• Access by reference, delete: O(1). Insert after/before known node: O(1).
• Search by value: O(n). Space: O(1) per node extra compared to singly linked (one more pointer).

Summary

• Doubly linked list: each node has prev and next; O(1) delete by reference and backward traversal.
• Use sentinels for uniform insert/delete at ends.
• Foundation for Flatten Multilevel Doubly Linked List and design problems like LRU cache.

See Dummy Head for the sentinel idea applied to singly linked lists.