Doubly linked list

Overview

A doubly linked list gives every node two pointers: next and prev. You can walk in both directions, and, most importantly, remove any node in O(1) when you hold a reference to it, because the node already knows its predecessor.

This property makes the doubly linked list the backbone of LRU caches, browser history, and deques. Paired with a hash map from key to node, it supports O(1) lookup, O(1) move-to-front, and O(1) eviction of the oldest item.

When to use it

• You need O(1) removal of arbitrary nodes that you can locate quickly (usually through a hash map).
• You need to traverse both forward and backward.
• You maintain recency or order under frequent moves: LRU / LFU caches.
• You implement a deque or a text editor buffer.

Problem patterns it solves

Where it is used in real software

Key terms

prev / next

Pointers to the previous and next nodes.

Sentinel head and tail

Dummy nodes at both ends so every real node always has non-null neighbors.

Unlink

node.prev.next = node.next; node.next.prev = node.prev.

Move to front

Unlink a node and insert it right after the head sentinel.

LRU cache operations

1. 1
   Structure

   A Map from key to node, and a doubly linked list with sentinel head (most recent side) and tail (least recent side).

2. 2
   get(key)

   Look up the node in the map. If found, move it to the front and return its value. O(1).

3. 3
   put(key, value), existing key

   Update the value and move the node to the front.

4. 4
   put(key, value), new key

   Create a node, insert it at the front, and add it to the map.

5. 5
   Evict when over capacity

   Remove the node before the tail sentinel (least recently used) from both the list and the map.

LRU cache with capacity 2

Front = most recent, back = least recent

Every operation touches a constant number of pointers and one hash map entry, so each is O(1).

Implementation

1class Node {2  constructor(key, value) {3    this.key = key;4    this.value = value;5    this.prev = null;6    this.next = null;7  }8}9 10class LRUCache {11  constructor(capacity) {12    this.capacity = capacity;13    this.map = new Map();14    this.head = new Node(); // most recent side15    this.tail = new Node(); // least recent side16    this.head.next = this.tail;17    this.tail.prev = this.head;18  }19 20  #unlink(node) {21    node.prev.next = node.next;22    node.next.prev = node.prev;23  }24 25  #addToFront(node) {26    node.next = this.head.next;27    node.prev = this.head;28    this.head.next.prev = node;29    this.head.next = node;30  }31 32  get(key) {33    const node = this.map.get(key);34    if (!node) return -1;35    this.#unlink(node);36    this.#addToFront(node);37    return node.value;38  }39 40  put(key, value) {41    if (this.map.has(key)) {42      const node = this.map.get(key);43      node.value = value;44      this.#unlink(node);45      this.#addToFront(node);46      return;47    }48    const node = new Node(key, value);49    this.map.set(key, node);50    this.#addToFront(node);51    if (this.map.size > this.capacity) {52      const lru = this.tail.prev;53      this.#unlink(lru);54      this.map.delete(lru.key);55    }56  }57}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Updating pointers in the wrong order.

  Fix: When inserting, set the new node's prev and next first, then update the neighbors.

• Forgetting to delete the evicted key from the map.

  Fix: Store the key inside the node so you can remove it from the map during eviction.

• Null checks everywhere.

  Fix: Use head and tail sentinels so neighbors always exist.

Interview questions

Practice problems