Module P-3·12 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.

Written by Jatin Jain Saraf · Architect of SupraScan

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

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

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
    }
  }
}