Module P-3·16 min read

Combining a hash map with a doubly linked list for O(1) reads and writes — the exact structure behind Redis-style cache eviction.

JJS

Written by Jatin Jain Saraf · Senior Software Engineer

Module P-3 — The LRU Cache: Hash Map + Doubly Linked List for O(1) Access

Q: Why is neither a plain hash map alone nor a plain doubly linked list alone sufficient to implement an LRU cache with O(1) `get` and `put`?

A hash map alone gives O(1) lookup by key but has no way to track which key was least recently used without an O(n) scan or a separate O(n) reordering step; a doubly linked list alone gives O(1) reordering of a known node but has no O(1) way to find a specific key's node without scanning — combining them (map values pointing to list nodes) supplies both properties at once. — The module lays out precisely this gap for each structure individually: a hash map has no built-in concept of "least recently used" ordering, and a linked list has no O(1) way to locate an arbitrary key's node. The fix is architectural — store node references as the hash map's values, so a hash lookup gets you directly to the node, and the doubly linked list's O(1) removal/reinsertion (from Module P-2) handles reordering without any scanning. Option B is factually false — JavaScript `Map` values can be any type, including object references, which is exactly what's used here. Option C is an overgeneralization the module never makes; linked lists are specifically bad at lookup-by-key, which is the whole reason the hash map is needed alongside them. Option D ignores the actual mechanism entirely — capacity determines when eviction happens, not how any operation achieves O(1).

Q: What specific role do the sentinel `head` and `tail` nodes play in the `LRUCache` implementation?

They act as permanent placeholder nodes so that `head.next` and `tail.prev` are always valid references to read and link against, eliminating the need for special-case handling of an empty list or a list with only one real node — structurally the same purpose as the `dummy` node in Module P-2's `mergeSorted`. — `head` and `tail` never hold real cache entries — they exist purely so that `insertAtFront` and eviction logic (`this.tail.prev!`) always have a valid node to link against, regardless of whether the "real" list currently has zero, one, or many entries. This removes the need for conditional logic checking "is the list empty" before inserting or evicting, mirroring the exact purpose the module attributes to Module P-2's `dummy` node in `mergeSorted`. Option A is incorrect — the sentinels are explicitly described as placeholders holding `null` key/value, never real cache data. Option C understates their role — while TypeScript's null-checking does benefit, the module frames their purpose as eliminating edge-case logic at runtime, not merely satisfying the type checker. Option D fabricates an error-recovery mechanism that doesn't exist in this implementation.

Q: Why does calling `get(key)` correctly update the cache's recency ordering, given that the hash map (`this.map`) is never re-written or updated inside the `get` method itself?

`this.map`'s values are references to the actual linked-list node objects, not copies of their contents — so calling `removeNode`/`insertAtFront` on the node retrieved from the map directly mutates the very object the map is already pointing to, meaning the map's entry remains correct (pointing at the newly repositioned node) without ever needing to be reassigned. — The module calls out this exact detail: the hash map stores object references to nodes, not snapshots of their state. `removeNode`/`insertAtFront` operate on that same node object in place — changing its position within the linked list — while the map's entry for that key still points at the identical object, now repositioned. No separate update to `this.map` is ever required, because the map was never storing positional information in the first place; position lives entirely in the linked list's pointer structure. Option A is false — `get` explicitly calls `removeNode` and `insertAtFront` specifically to mark the accessed entry as most recently used, which is real recency tracking, not something deferred to `put`. Option C fabricates a nonexistent JavaScript `Map` auto-synchronization behavior. Option D misdescribes the code — `get` never calls `this.map.delete` or `this.map.set`; it only manipulates the linked list.

What this module covers: This module is the payoff for the last two — it combines Module F-4's hash map with Module P-2's doubly linked list to solve a problem neither one can solve alone in O(1): a fixed-capacity cache that evicts its least recently used entry the moment it's full, with O(1) reads and O(1) writes. This is also, structurally, close to how a real caching layer like Redis actually manages memory under pressure.

The Problem: Neither Structure Alone Is Enough

An LRU (Least Recently Used) cache needs to support two operations, both in O(1):

get(key) — return the value if present, and mark this key as the most recently used.
put(key, value) — insert or update a value, marking it as most recently used; if the cache is now over capacity, evict whichever key is least recently used.

A plain hash map (Module F-4) gives O(1) get/put — but a Map has no built-in notion of "which key was touched longest ago." You could track recency with an array of keys in usage order, but moving a key to the "most recent" position in an array means removing it from the middle and re-inserting at the end — O(n), because of exactly the shifting cost from Module F-2.

A plain doubly linked list (Module P-2) gives O(1) reordering — move a node to the front, remove a node from the back — but finding a specific key's node in the first place means scanning the list, O(n), because a linked list has no O(1) lookup-by-key.

Neither structure alone gets you both O(1) lookup and O(1) recency reordering. Combined, they do: the hash map's values aren't the cached data itself — they're direct references to nodes in the doubly linked list, so a get is one O(1) hash lookup followed by O(1) pointer manipulation to move that node to the front of the list.

Analogy: Think of the linked list as a line of people ordered by "who spoke to the cashier most recently," front to back. The hash map is the cashier's private notebook mapping each person's name directly to their exact position in that line — so instead of scanning the whole line to find someone, the cashier flips straight to their name and walks right to them.

The Structure

typescript

class DLLNode<K, V> {
  key: K;
  value: V;
  prev: DLLNode<K, V> | null = null;
  next: DLLNode<K, V> | null = null;
  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache<K, V> {
  private capacity: number;
  private map = new Map<K, DLLNode<K, V>>(); // Module F-4 — key -> node reference, O(1) lookup
  private head: DLLNode<K, V>;                // sentinel — most-recently-used side
  private tail: DLLNode<K, V>;                // sentinel — least-recently-used side

  constructor(capacity: number) {
    this.capacity = capacity;
    // Sentinel (dummy) nodes eliminate special-casing an empty list or a list with one node —
    // the same trick used for the `dummy` node in Module P-2's mergeSorted.
    this.head = new DLLNode<K, V>(null as unknown as K, null as unknown as V);
    this.tail = new DLLNode<K, V>(null as unknown as K, null as unknown as V);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private removeNode(node: DLLNode<K, V>): void {
    node.prev!.next = node.next; // O(1) — Module P-2's doubly linked list deletion
    node.next!.prev = node.prev;
  }

  private insertAtFront(node: DLLNode<K, V>): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node; // O(1) — insert right after the head sentinel
  }

  get(key: K): V | undefined {
    const node = this.map.get(key); // O(1) — Module F-4
    if (!node) return undefined;

    this.removeNode(node);     // O(1)
    this.insertAtFront(node);  // O(1) — mark as most recently used
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.removeNode(existing);
      this.insertAtFront(existing);
      return;
    }

    const node = new DLLNode(key, value);
    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.removeNode(lru);
      this.map.delete(lru.key);          // must remove from the map too, or it'd be a stale reference
    }
  }
}

Walk through what happens on a get: this.map.get(key) is O(1) and hands back a direct node reference — no scanning. removeNode and insertAtFront are both O(1), because a doubly linked list's prev pointer means removing a node never requires searching for its neighbor (Module P-2's exact point about doubly vs. singly linked lists). Every operation this class exposes is O(1), end to end — that's the entire value of combining the two structures.

Why the sentinel head/tail nodes matter: without them, insertAtFront and eviction from the tail would each need separate handling for "the list is currently empty" or "the list has exactly one node." Two permanent placeholder nodes mean the list is never truly empty from the code's perspective — head.next and tail.prev are always valid nodes to read, even when no real entries exist yet. This is the same category of trick as Module P-2's dummy node in mergeSorted — a placeholder that makes edge cases disappear rather than needing to be handled explicitly.

Why the Hash Map's Values Are Node References, Not Copies

The detail that makes this whole structure work is subtle enough to say directly: this.map doesn't store the cached value — it stores a reference to the linked list node holding that value. That's what lets get mutate the list (move the node to the front) using the exact same object the map already points to, with no need to also update the map afterward — the map's entry is still correct, because it was always pointing at the node object itself, not a snapshot of its contents at insertion time.

Where This Shows Up in Your Stack

Redis's actual eviction policies: Redis supports an allkeys-lru (and similar) eviction policy, but worth being precise here — at scale, true LRU tracking (touching a global recency structure on every access) is too expensive to do exactly, so Redis approximates it by sampling a small random set of keys and evicting the least-recently-used among that sample, repeated as needed. The redis-in-depth course covers this trade-off — and Redis's other eviction policies (allkeys-lfu, volatile-ttl, and others) — in full.
Browser HTTP caches and CDN edge caches use LRU or LRU-like policies to decide which cached responses to evict first once storage fills up — exactly the "capacity exceeded, drop the least recently touched entry" logic in put above.
Database buffer pools: PostgreSQL's shared_buffers (covered in depth in the postgresql-in-depth course) doesn't use textbook LRU either — it uses a clock-sweep algorithm, a cheaper approximation with similar goals (keep frequently-accessed pages in memory, evict cold ones) without the overhead of maintaining a perfectly ordered recency list on every single page access.
In-process memoization caches (Module F-4's preview, Module P-11's dynamic programming) that need a size cap — "cache the last 500 computed results, evict the oldest untouched one when full" — are a direct, practical use of exactly the LRUCache class built above, with no approximation needed at that smaller scale.

Summary

An LRU cache needs O(1) get and O(1) put, plus O(1) eviction of the least recently used entry — no single structure covered so far provides all three alone.
A hash map gives O(1) lookup but no recency ordering; a doubly linked list gives O(1) reordering but no O(1) lookup by key. Combined — map values are node references — you get both.
Sentinel head/tail nodes eliminate edge-case handling for an empty list or single-node list, the same category of trick as Module P-2's dummy node.
The critical detail: the map stores a reference to the actual linked-list node, not a copy of the value — so reordering the list via that same reference keeps the map correct automatically, with no separate update step.
Real caching systems approximate this rather than implementing it exactly at scale — Redis samples instead of tracking global recency, and Postgres uses clock-sweep instead of LRU — because true LRU's per-access bookkeeping becomes expensive at very large scale, even though it's O(1) per operation.

The next module, Tree Traversal: Inorder, Preorder, Postorder, and Level-Order, moves from linear structures (lists, queues, stacks) to the first branching structure in this course — building directly on Module P-1's recursion and Module F-7's queue.

Knowledge Check

Why is neither a plain hash map alone nor a plain doubly linked list alone sufficient to implement an LRU cache with O(1) get and put?

What specific role do the sentinel head and tail nodes play in the LRUCache implementation?

Why does calling get(key) correctly update the cache's recency ordering, given that the hash map (this.map) is never re-written or updated inside the get method itself?

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule P-2: Linked Lists: Singly, Doubly, and Core Operations Next Module P-4: Tree Traversal: Inorder, Preorder, Postorder, and Level-order

Discussion

Join the discussion

Loading comments...