The LRU Cache, with a Map and a Linked List

This is the capstone of everything trees, linked lists, and hashing have built toward in this course: a least-recently-used (LRU) cache, one of the most commonly asked "build a real data structure" interview problems, and a genuinely useful piece of infrastructure — a bounded memoization layer, an image or thumbnail cache, "recently viewed items" — that combines a hash map's O(1) lookup with a doubly linked list's O(1) reordering.

The requirement

An LRU cache needs three operations, all in O(1):

• get(key) — return the value if present, and mark this entry as just used.
• put(key, value) — insert or update, also marking it as just used.
• Eviction — once the cache is over capacity, remove whichever entry hasn't been used in the longest time.

Why neither structure alone is enough

A plain Map gives O(1) get/set, but has no built-in notion of "which entry was used longest ago" — you'd need to scan for it, which is O(n).

A plain array kept in usage order would need to relocate an entry to the "just used" end on every access — and relocating an arbitrary array element means removing it from its current position (O(n), because later elements shift down to fill the gap). Neither structure, alone, gets you there.

The combination: Map (key → node) + doubly linked list (usage order)

The trick is to keep the actual key-value data in a doubly linked list, ordered from most-recently-used to least-recently-used, and keep a Map from key to that exact list node so you never have to search the list — only jump directly to a node by key, then relocate it in O(1) because a doubly linked list's prev pointer lets you detach a node without walking from the head to find its predecessor (exactly the capability flagged at the end of the linked-lists lesson).

class LRUCache {
  #capacity;
  #map = new Map();     // key -> node
  #head;                  // most-recently-used end (sentinel)
  #tail;                  // least-recently-used end (sentinel)
 
  constructor(capacity) {
    this.#capacity = capacity;
    this.#head = { key: null, value: null, prev: null, next: null };
    this.#tail = { key: null, value: null, prev: null, next: null };
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }
 
  #remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev; // O(1) — only touches the two neighbors, thanks to prev
  }
 
  #insertAtFront(node) {
    node.next = this.#head.next;
    node.prev = this.#head;
    this.#head.next.prev = node;
    this.#head.next = node; // O(1) — always inserting right after the head sentinel
  }
 
  get(key) {
    if (!this.#map.has(key)) return undefined;
    const node = this.#map.get(key);
    this.#remove(node);
    this.#insertAtFront(node); // mark as most-recently-used
    return node.value;
  }
 
  put(key, value) {
    if (this.#map.has(key)) {
      const node = this.#map.get(key);
      node.value = value;
      this.#remove(node);
      this.#insertAtFront(node);
      return;
    }
 
    const node = { key, value, prev: null, next: null };
    this.#map.set(key, node);
    this.#insertAtFront(node);
 
    if (this.#map.size > this.#capacity) {
      const lru = this.#tail.prev; // the node right before the tail sentinel — least recently used
      this.#remove(lru);
      this.#map.delete(lru.key);
    }
  }
}

The two sentinel nodes (#head and #tail) are a standard trick to avoid special-casing "is the list empty" or "is this the first/last real node" — every real node always has a genuine prev and next to work with, even at the boundaries.

Why every step is genuinely O(1)

• get: map lookup (O(1)) + detach (O(1), using prev) + re-insert at front (O(1)).
• put (new key): map insert (O(1) average) + insert at front (O(1)) +, if over capacity, evict the tail's neighbor (O(1) — no search, because the list's ordering guarantees the LRU entry is always exactly there).
• put (existing key): same shape as get, plus updating the value.

No step scans the list or the map. This is the entire payoff of combining the two structures: the map removes the linked list's "find by key" weakness (which would otherwise be O(n)), and the doubly linked list removes a plain map's "who's least recently used" weakness (which would otherwise require a scan or a separate, harder-to-maintain ordering).

What to remember

• An LRU cache needs O(1) get/put/evict, and no single structure alone achieves all three — a Map alone can't track usage order without a scan, and a plain array can't relocate an entry to the front without shifting everything after it.
• Combining a Map (key → node) with a doubly linked list (usage order) gets every operation to genuine O(1): the map avoids searching the list, and the list's prev pointers let a node be detached and re-inserted without a scan.
• The least-recently-used entry is always exactly the node next to the tail sentinel, by construction — eviction never needs to search for who deserves removal.
• Sentinel head/tail nodes remove the need to special-case empty-list or boundary conditions — every real node always has genuine neighbors to work with.