Lru Cache - Learning Module

Loading content...

0/279

Hash map + doubly linked list design

The Perfect Partnership

In the previous pages, we established that no single data structure can satisfy all LRU cache requirements. Hash maps provide O(1) key lookup but have no concept of ordering. Linked lists provide O(1) insertion and removal but require O(n) search.

The breakthrough comes from recognizing that these weaknesses are complementary. What one structure lacks, the other provides. By combining them synergistically, we create something greater than the sum of its parts — an O(1) LRU cache.

This page presents the complete design: how the hash map and doubly linked list work together, how data flows between them, and why this combination achieves O(1) for every operation. Understanding this design deeply is essential — it's one of the most elegant examples of composite data structure design in computer science.

What You Will Learn

By the end of this page, you will understand the complete architecture of an O(1) LRU cache, how the hash map and doubly linked list complement each other, the role of sentinel nodes in simplifying edge cases, and the invariants that keep everything consistent.

The Core Insight

The key insight is deceptively simple: use the hash map to store pointers to linked list nodes, not the values themselves.

Traditionally, when we think of hash maps, we think:

HashMap<Key, Value>

For LRU cache, we instead use:

HashMap<Key, Node<Key, Value>>

Where Node is a doubly linked list node that contains both the key, the value, and pointers to adjacent nodes.

What this enables:

The Power of Node References

•O(1) key lookup — Hash map provides this directly
•O(1) access to the node — Hash map value IS the node, not a copy
•O(1) node removal — With the node in hand, we can update prev/next pointers directly
•O(1) move to front — Remove from current position + insert at head, both O(1)
•O(1) find LRU — Tail pointer gives immediate access to the oldest node

The synergy:

The hash map compensates for the linked list's O(n) search by providing O(1) access to any node by key.

The linked list compensates for the hash map's lack of ordering by maintaining a total order from most to least recently used.

Neither alone is sufficient. Together, they form a complete solution.

Why Store the Key in the Node?

You might wonder: if we look up by key, why store the key in the node too? The answer: during eviction. When we remove the tail node, we need to also remove its entry from the hash map. To do that, we need to know what key to remove — which requires storing the key in the node itself.

Architecture Overview

Let's visualize the complete LRU cache architecture. Understanding the physical layout is essential for implementing it correctly.

Visual representation:

lru-architecture.txt

Diagram

LRU Cache Architecture
═══════════════════════════════════════════════════════════════════
 
                         HASH MAP
                    ┌─────────────────┐
                    │  key → node     │
                    ├─────────────────┤
                    │ "A" ──────────────────────────────────┐
                    │ "B" ───────────────────────┐          │
                    │ "C" ────────────┐          │          │
                    └─────────────────┘          │          │
                                       │          │          │
                                       ▼          ▼          ▼
                   DOUBLY LINKED LIST (recency order)
                   ┌───────────────────────────────────────────────────┐
                   │                                                   │
    Most Recent    │   ┌─────────┐   ┌─────────┐   ┌─────────┐        │   Least Recent
         ┌─────────┼──▶│ Node C  │◀─▶│ Node B  │◀─▶│ Node A  │◀───────┼─────┐
         │         │   │ key="C" │   │ key="B" │   │ key="A" │        │     │
         │         │   │ val=300 │   │ val=200 │   │ val=100 │        │     │
    ┌────┴────┐    │   └─────────┘   └─────────┘   └─────────┘        │  ┌──┴──┐
    │  HEAD   │    │        ▲             ▲             ▲             │  │TAIL │
    │(sentinel)────┘        │             │             │             └──(sentinel)
    └─────────┘             │             │             │                └─────┘
                            │             │             │
                            └─────────────┴─────────────┘
                               Bidirectional links
                               
═══════════════════════════════════════════════════════════════════
Key Properties:
• HEAD.next = Most Recently Used item
• TAIL.prev = Least Recently Used item (eviction candidate)
• Every node is reachable via hash map in O(1)
• Every node can be removed/moved in O(1) via its links

Component breakdown:

1. The Hash Map (Map<Key, Node>):

Maps each key to its corresponding doubly linked list node
Provides O(1) lookup: given a key, get the node instantly
Size equals the number of cached items
Standard library HashMap/Map/dict works perfectly

2. The Doubly Linked List:

Maintains recency order from head (MRU) to tail (LRU)
Each node contains: key, value, prev pointer, next pointer
Supports O(1) removal and insertion at any position
Uses sentinel nodes at head and tail to simplify edge cases

3. Sentinel Nodes (Head and Tail):

Dummy nodes that mark the boundaries of the list
Head sentinel: head.next always points to MRU node
Tail sentinel: tail.prev always points to LRU node
Never contain real data — they're structural markers only

Why Two Structures Point to the Same Nodes

The hash map and linked list don't store separate copies of data — they store references to the same node objects. When you update a node's value via the hash map, the linked list 'sees' the update because it's the same object. This shared reference is crucial for consistency and space efficiency.

The Sentinel Node Pattern

Sentinel nodes (also called dummy nodes or boundary nodes) are a crucial implementation technique that dramatically simplifies linked list code. Let's understand why they matter.

The problem without sentinels:

Without sentinel nodes, every operation must handle special cases for empty lists, single-element lists, and operations at the head or tail:

without-sentinels.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// WITHOUT SENTINELS - Complex edge case handling
class LRUWithoutSentinels {
    private head: Node | null = null;
    private tail: Node | null = null;
 
    removeNode(node: Node): void {
        // Case 1: Node is the only element
        if (node.prev === null && node.next === null) {
            this.head = null;
            this.tail = null;
            return;
        }
 
        // Case 2: Node is at the head
        if (node.prev === null) {
            this.head = node.next;
            this.head!.prev = null;
            return;
        }
 
        // Case 3: Node is at the tail
        if (node.next === null) {
            this.tail = node.prev;
            this.tail!.prev = null;
            return;
        }
 
        // Case 4: Node is in the middle
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    addToHead(node: Node): void {
        // Case 1: List is empty
        if (this.head === null) {
            this.head = node;
            this.tail = node;
            node.prev = null;
            node.next = null;
            return;
        }
 
        // Case 2: List has elements
        node.next = this.head;
        node.prev = null;
        this.head.prev = node;
        this.head = node;
    }
    // Every method needs 3-4 cases!
}

The elegance with sentinels:

With sentinel nodes, the list is never truly empty — it always contains at least the head and tail sentinels. This eliminates null checks and special cases:

with-sentinels.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// WITH SENTINELS - Clean, uniform code
class LRUWithSentinels<K, V> {
    private head: Node<K, V>;  // Sentinel - never null
    private tail: Node<K, V>;  // Sentinel - never null
 
    constructor() {
        // Create sentinel nodes with dummy values
        this.head = new Node(null as any, null as any);
        this.tail = new Node(null as any, null as any);
        
        // Link them together - this is the "empty" state
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
 
    removeNode(node: Node<K, V>): void {
        // ONE case handles ALL scenarios!
        // Works whether node is first, last, middle, or only element
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
        // That's it. No null checks. No special cases.
    }
 
    addToHead(node: Node<K, V>): void {
        // ONE case handles ALL scenarios!
        // Works whether list is empty or has elements
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next!.prev = node;
        this.head.next = node;
        // That's it. Always works.
    }
 
    removeTail(): Node<K, V> | null {
        // Get the actual tail (not the sentinel)
        const lru = this.tail.prev!;
        
        // If lru is the head sentinel, list is empty
        if (lru === this.head) return null;
        
        this.removeNode(lru);
        return lru;
    }
}

The Sentinel Guarantee

With sentinels: • Every real node always has a valid prev (never null) • Every real node always has a valid next (never null) • head.next is always valid (might be tail if empty) • tail.prev is always valid (might be head if empty)

This invariant eliminates entire categories of null pointer bugs.

Data Flow — The get() Operation

Let's trace through exactly what happens during a get(key) operation, step by step.

Scenario: Cache contains keys A, B, C. We call get("B").

Before state:

get-operation-trace.txt

Trace

BEFORE get("B"):
═══════════════════════════════════════════════════════════════════
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }
 
Linked List (MRU → LRU):
HEAD ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
         ↑ most recent           ↑ least recent
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
═══════════════════════════════════════════════════════════════════
node = map.get("B")  // Returns pointer to NodeB
if (node === undefined) return -1;  // Cache miss - but B exists
 
node is now: [B:200] with prev→[C:300], next→[A:100]
 
═══════════════════════════════════════════════════════════════════
STEP 2: Remove node from current position — O(1)
═══════════════════════════════════════════════════════════════════
// Update C's next pointer
node.prev.next = node.next    // C.next = A
 
// Update A's prev pointer  
node.next.prev = node.prev    // A.prev = C
 
Intermediate state:
HEAD ←→ [C:300] ←→ [A:100] ←→ TAIL
         (B is disconnected but still in hash map)
 
═══════════════════════════════════════════════════════════════════
STEP 3: Insert node at head (most recent) — O(1)
═══════════════════════════════════════════════════════════════════
node.next = head.next         // B.next = C
node.prev = head              // B.prev = HEAD
head.next.prev = node         // C.prev = B
head.next = node              // HEAD.next = B
 
═══════════════════════════════════════════════════════════════════
AFTER get("B"):
═══════════════════════════════════════════════════════════════════
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }  // Unchanged!
 
Linked List (MRU → LRU):
HEAD ←→ [B:200] ←→ [C:300] ←→ [A:100] ←→ TAIL
         ↑ B is now most recent
 
STEP 4: Return value — O(1)
return node.value  // Returns 200

Key observations:

The hash map contents don't change — only the linked list order changes
We modified exactly 4 pointers to remove the node
We modified exactly 4 pointers to insert at head
Total: 8 pointer updates + 1 hash lookup = O(1)

Cache miss case:

If get("X") is called and X isn't in the hash map, we simply return -1/null without touching the linked list. The recency order remains unchanged.

The Move-to-Front Pattern

The combination of 'remove from current position' and 'insert at head' is so common it's often extracted as a single helper method: moveToHead(node). This encapsulates the recency update logic and is used by both get() and put().

Data Flow — The put() Operation

The put(key, value) operation is more complex because it has two main branches: updating an existing key vs. inserting a new key (which may trigger eviction).

Case 1: Key already exists

put-update-trace.txt

Trace

put("B", 999) when B already exists:
═══════════════════════════════════════════════════════════════════
BEFORE:
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }
List: HEAD ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
node = map.get("B")  // Returns NodeB
// Key exists! This is an update, not an insert.
 
STEP 2: Update value — O(1)
node.value = 999     // NodeB now contains 999
 
STEP 3: Move to head — O(1)
removeNode(node)     // Disconnect from current position
addToHead(node)      // Insert after head sentinel
 
═══════════════════════════════════════════════════════════════════
AFTER:
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }  // Same references
List: HEAD ←→ [B:999] ←→ [C:300] ←→ [A:100] ←→ TAIL
                ↑ B updated and moved to front

Case 2: Key doesn't exist, no eviction needed

put-insert-trace.txt

Trace

put("D", 400) when D doesn't exist, capacity = 4:
═══════════════════════════════════════════════════════════════════
BEFORE (size = 3, capacity = 4):
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }
List: HEAD ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
node = map.get("D")  // Returns undefined
// Key doesn't exist! This is an insert.
 
STEP 2: Check capacity — O(1)
if (size >= capacity) { evict() }  // size=3 < capacity=4, no eviction
 
STEP 3: Create new node — O(1)
newNode = new Node("D", 400)
 
STEP 4: Add to hash map — O(1)
map.set("D", newNode)
 
STEP 5: Add to head of list — O(1)
addToHead(newNode)
 
═══════════════════════════════════════════════════════════════════
AFTER (size = 4):
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC, "D" → NodeD }
List: HEAD ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
                ↑ D is most recent

Case 3: Key doesn't exist, eviction required

put-eviction-trace.txt

Trace

put("E", 500) when E doesn't exist, capacity = 4, size = 4:
═══════════════════════════════════════════════════════════════════
BEFORE (size = 4, capacity = 4 — FULL):
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC, "D" → NodeD }
List: HEAD ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
                                                   ↑ A is LRU (eviction target)
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
node = map.get("E")  // Returns undefined - new key
 
STEP 2: Check capacity — triggers eviction!
if (size >= capacity) { evict() }  // size=4 >= capacity=4, must evict
 
    EVICTION SUB-STEPS:
    ─────────────────────────────────────────────────────────────
    a) Find LRU node — O(1)
       lruNode = tail.prev  // NodeA (the one before tail sentinel)
    
    b) Remove from linked list — O(1)
       removeNode(lruNode)
    
    c) Remove from hash map — O(1)
       // This is why we store the key in the node!
       map.delete(lruNode.key)  // map.delete("A")
    ─────────────────────────────────────────────────────────────
 
Intermediate state:
HashMap: { "B" → NodeB, "C" → NodeC, "D" → NodeD }  // A removed
List: HEAD ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ TAIL
 
STEP 3: Create new node — O(1)
newNode = new Node("E", 500)
 
STEP 4: Add to hash map — O(1)
map.set("E", newNode)
 
STEP 5: Add to head of list — O(1)
addToHead(newNode)
 
═══════════════════════════════════════════════════════════════════
AFTER (size = 4):
HashMap: { "B" → NodeB, "C" → NodeC, "D" → NodeD, "E" → NodeE }
List: HEAD ←→ [E:500] ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ TAIL
                ↑ E is most recent        B is now LRU (was second-oldest)

Critical: Remove from Hash Map During Eviction

A common bug is forgetting to remove the evicted key from the hash map. If you only remove from the linked list, the hash map still points to a 'zombie' node. Future get() calls for that key would return stale data or crash. Always remove from BOTH structures.

Invariants and Consistency

For the LRU cache to function correctly, certain conditions must always be true. These are called invariants. Violating any invariant leads to bugs.

The LRU Cache Invariants:

Must Always Be True

•Size Invariant: map.size equals the number of real nodes in the linked list (excluding sentinels)
•Capacity Invariant: map.size <= capacity — the cache never exceeds its capacity
•Bijection Invariant: Every key in the map has exactly one corresponding node in the list, and vice versa
•Pointer Invariant: For every real node N: N.prev.next === N and N.next.prev === N (bidirectional links are consistent)
•Sentinel Invariant: head.prev === null and tail.next === null — sentinels mark boundaries
•Order Invariant: Nodes are ordered from most to least recently accessed when traversing head → tail

Common invariant violations and their symptoms:

Invariant Violations and Debugging
Violation	Symptom	Likely Cause
Map size ≠ list size	Memory leak or missing items	Forgot to add/remove from one structure
Size > capacity	Eviction not triggered	Capacity check uses > instead of >=
Stale map entry	get() returns wrong/deleted value	Removed from list but not map during eviction
Broken prev/next link	Traversal skips nodes or crashes	Pointer update in wrong order
Lost reference	Node unreachable	Overwrote pointer before reading old value

Defensive Invariant Checking

During development, add an assertInvariants() method that walks the list and verifies all invariants. Call it after every operation. This catches bugs immediately at their source rather than later when symptoms appear. Remove or disable in production for performance.

Why This Design is Optimal

Let's formally verify that our hash map + doubly linked list design achieves the O(1) requirements.

Time complexity analysis:

Complete Operation Complexity Breakdown
Operation	Sub-operations	Each Sub-op	Total
get(key)	map.get + removeNode + addToHead	O(1) + O(1) + O(1)	O(1)
put(key, value) - update	map.get + update value + removeNode + addToHead	O(1) each	O(1)
put(key, value) - insert	map.get + new Node + map.set + addToHead	O(1) each	O(1)
put(key, value) - evict	Above + tail.prev + removeNode + map.delete	O(1) each	O(1)

Space complexity analysis:

Hash map: O(n) for n entries
Doubly linked list: O(n) for n nodes, but these ARE the same data
Sentinel nodes: O(1) — just 2 extra nodes regardless of n
Total: O(n) where n is the cache capacity

Why this is (essentially) optimal:

Any cache must store n items → Ω(n) space is unavoidable
Any correct LRU must track recency → need n ordered elements
O(1) access requires direct addressing → need hash-based structure
O(1) reordering requires prev/next pointers → need doubly linked structure

The only additional overhead is the constant factor of pointer storage and the two sentinel nodes — both unavoidable given our requirements.

No known alternative achieves O(1) get and O(1) put with less overhead. This design is the canonical solution taught in advanced data structures courses and used in production systems worldwide.

A Timeless Design Pattern

The hash map + doubly linked list combination isn't just for LRU caches. It's a general pattern for any problem requiring both O(1) key lookup AND O(1) order manipulation. Ordered dictionaries, LFU caches, and various scheduling algorithms use the same core idea.

Summary: The Design Foundation

We've covered the complete design of an O(1) LRU cache. Let's consolidate the key insights:

Key Takeaways

•Two structures, one purpose — Hash map provides O(1) lookup; doubly linked list provides O(1) ordering operations. Together they achieve what neither can alone.
•Store node references, not values — The hash map values are pointers to linked list nodes. This enables O(1) access to any node by key.
•Sentinel nodes simplify everything — Dummy head and tail nodes eliminate null checks and special cases, making code cleaner and less bug-prone.
•Both structures must stay synchronized — Every insert/delete must update both the hash map and the linked list. Forgetting either causes bugs.
•Move-to-front on every access — Both get() and put() move the accessed key to the front, maintaining the recency invariant.
•Eviction uses the tail — The LRU item is always at tail.prev, giving O(1) access to the eviction target.

What's next:

With the design fully understood, the next page provides a complete, production-quality implementation of the LRU cache. We'll translate these concepts into working code, handle all edge cases, and discuss implementation details that affect real-world performance.

Page Complete

You now understand the complete architecture of an O(1) LRU cache: how hash maps and doubly linked lists work together, the role of sentinel nodes, the data flow through get() and put() operations, and the invariants that keep everything consistent. Next, we'll implement it!

Hash map + doubly linked list design

The Perfect Partnership

What You Will Learn

The Core Insight

The key insight is deceptively simple: use the hash map to store pointers to linked list nodes, not the values themselves.

Traditionally, when we think of hash maps, we think:

HashMap<Key, Value>

For LRU cache, we instead use:

HashMap<Key, Node<Key, Value>>

Where Node is a doubly linked list node that contains both the key, the value, and pointers to adjacent nodes.

What this enables:

The Power of Node References

•O(1) key lookup — Hash map provides this directly
•O(1) access to the node — Hash map value IS the node, not a copy
•O(1) node removal — With the node in hand, we can update prev/next pointers directly
•O(1) move to front — Remove from current position + insert at head, both O(1)
•O(1) find LRU — Tail pointer gives immediate access to the oldest node

The synergy:

The hash map compensates for the linked list's O(n) search by providing O(1) access to any node by key.

The linked list compensates for the hash map's lack of ordering by maintaining a total order from most to least recently used.

Neither alone is sufficient. Together, they form a complete solution.

Why Store the Key in the Node?

Architecture Overview

Let's visualize the complete LRU cache architecture. Understanding the physical layout is essential for implementing it correctly.

Visual representation:

lru-architecture.txt

Diagram

LRU Cache Architecture
═══════════════════════════════════════════════════════════════════
 
                         HASH MAP
                    ┌─────────────────┐
                    │  key → node     │
                    ├─────────────────┤
                    │ "A" ──────────────────────────────────┐
                    │ "B" ───────────────────────┐          │
                    │ "C" ────────────┐          │          │
                    └─────────────────┘          │          │
                                       │          │          │
                                       ▼          ▼          ▼
                   DOUBLY LINKED LIST (recency order)
                   ┌───────────────────────────────────────────────────┐
                   │                                                   │
    Most Recent    │   ┌─────────┐   ┌─────────┐   ┌─────────┐        │   Least Recent
         ┌─────────┼──▶│ Node C  │◀─▶│ Node B  │◀─▶│ Node A  │◀───────┼─────┐
         │         │   │ key="C" │   │ key="B" │   │ key="A" │        │     │
         │         │   │ val=300 │   │ val=200 │   │ val=100 │        │     │
    ┌────┴────┐    │   └─────────┘   └─────────┘   └─────────┘        │  ┌──┴──┐
    │  HEAD   │    │        ▲             ▲             ▲             │  │TAIL │
    │(sentinel)────┘        │             │             │             └──(sentinel)
    └─────────┘             │             │             │                └─────┘
                            │             │             │
                            └─────────────┴─────────────┘
                               Bidirectional links
                               
═══════════════════════════════════════════════════════════════════
Key Properties:
• HEAD.next = Most Recently Used item
• TAIL.prev = Least Recently Used item (eviction candidate)
• Every node is reachable via hash map in O(1)
• Every node can be removed/moved in O(1) via its links

Component breakdown:

1. The Hash Map (Map<Key, Node>):

Maps each key to its corresponding doubly linked list node
Provides O(1) lookup: given a key, get the node instantly
Size equals the number of cached items
Standard library HashMap/Map/dict works perfectly

2. The Doubly Linked List:

Maintains recency order from head (MRU) to tail (LRU)
Each node contains: key, value, prev pointer, next pointer
Supports O(1) removal and insertion at any position
Uses sentinel nodes at head and tail to simplify edge cases

3. Sentinel Nodes (Head and Tail):

Dummy nodes that mark the boundaries of the list
Head sentinel: head.next always points to MRU node
Tail sentinel: tail.prev always points to LRU node
Never contain real data — they're structural markers only

Why Two Structures Point to the Same Nodes

The Sentinel Node Pattern

Sentinel nodes (also called dummy nodes or boundary nodes) are a crucial implementation technique that dramatically simplifies linked list code. Let's understand why they matter.

The problem without sentinels:

Without sentinel nodes, every operation must handle special cases for empty lists, single-element lists, and operations at the head or tail:

without-sentinels.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// WITHOUT SENTINELS - Complex edge case handling
class LRUWithoutSentinels {
    private head: Node | null = null;
    private tail: Node | null = null;
 
    removeNode(node: Node): void {
        // Case 1: Node is the only element
        if (node.prev === null && node.next === null) {
            this.head = null;
            this.tail = null;
            return;
        }
 
        // Case 2: Node is at the head
        if (node.prev === null) {
            this.head = node.next;
            this.head!.prev = null;
            return;
        }
 
        // Case 3: Node is at the tail
        if (node.next === null) {
            this.tail = node.prev;
            this.tail!.prev = null;
            return;
        }
 
        // Case 4: Node is in the middle
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    addToHead(node: Node): void {
        // Case 1: List is empty
        if (this.head === null) {
            this.head = node;
            this.tail = node;
            node.prev = null;
            node.next = null;
            return;
        }
 
        // Case 2: List has elements
        node.next = this.head;
        node.prev = null;
        this.head.prev = node;
        this.head = node;
    }
    // Every method needs 3-4 cases!
}

The elegance with sentinels:

With sentinel nodes, the list is never truly empty — it always contains at least the head and tail sentinels. This eliminates null checks and special cases:

with-sentinels.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// WITH SENTINELS - Clean, uniform code
class LRUWithSentinels<K, V> {
    private head: Node<K, V>;  // Sentinel - never null
    private tail: Node<K, V>;  // Sentinel - never null
 
    constructor() {
        // Create sentinel nodes with dummy values
        this.head = new Node(null as any, null as any);
        this.tail = new Node(null as any, null as any);
        
        // Link them together - this is the "empty" state
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
 
    removeNode(node: Node<K, V>): void {
        // ONE case handles ALL scenarios!
        // Works whether node is first, last, middle, or only element
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
        // That's it. No null checks. No special cases.
    }
 
    addToHead(node: Node<K, V>): void {
        // ONE case handles ALL scenarios!
        // Works whether list is empty or has elements
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next!.prev = node;
        this.head.next = node;
        // That's it. Always works.
    }
 
    removeTail(): Node<K, V> | null {
        // Get the actual tail (not the sentinel)
        const lru = this.tail.prev!;
        
        // If lru is the head sentinel, list is empty
        if (lru === this.head) return null;
        
        this.removeNode(lru);
        return lru;
    }
}

The Sentinel Guarantee

This invariant eliminates entire categories of null pointer bugs.

Data Flow — The get() Operation

Let's trace through exactly what happens during a get(key) operation, step by step.

Scenario: Cache contains keys A, B, C. We call get("B").

Before state:

get-operation-trace.txt

Trace

BEFORE get("B"):
═══════════════════════════════════════════════════════════════════
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }
 
Linked List (MRU → LRU):
HEAD ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
         ↑ most recent           ↑ least recent
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
═══════════════════════════════════════════════════════════════════
node = map.get("B")  // Returns pointer to NodeB
if (node === undefined) return -1;  // Cache miss - but B exists
 
node is now: [B:200] with prev→[C:300], next→[A:100]
 
═══════════════════════════════════════════════════════════════════
STEP 2: Remove node from current position — O(1)
═══════════════════════════════════════════════════════════════════
// Update C's next pointer
node.prev.next = node.next    // C.next = A
 
// Update A's prev pointer  
node.next.prev = node.prev    // A.prev = C
 
Intermediate state:
HEAD ←→ [C:300] ←→ [A:100] ←→ TAIL
         (B is disconnected but still in hash map)
 
═══════════════════════════════════════════════════════════════════
STEP 3: Insert node at head (most recent) — O(1)
═══════════════════════════════════════════════════════════════════
node.next = head.next         // B.next = C
node.prev = head              // B.prev = HEAD
head.next.prev = node         // C.prev = B
head.next = node              // HEAD.next = B
 
═══════════════════════════════════════════════════════════════════
AFTER get("B"):
═══════════════════════════════════════════════════════════════════
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }  // Unchanged!
 
Linked List (MRU → LRU):
HEAD ←→ [B:200] ←→ [C:300] ←→ [A:100] ←→ TAIL
         ↑ B is now most recent
 
STEP 4: Return value — O(1)
return node.value  // Returns 200

Key observations:

The hash map contents don't change — only the linked list order changes
We modified exactly 4 pointers to remove the node
We modified exactly 4 pointers to insert at head
Total: 8 pointer updates + 1 hash lookup = O(1)

Cache miss case:

If get("X") is called and X isn't in the hash map, we simply return -1/null without touching the linked list. The recency order remains unchanged.

The Move-to-Front Pattern

Data Flow — The put() Operation

The put(key, value) operation is more complex because it has two main branches: updating an existing key vs. inserting a new key (which may trigger eviction).

Case 1: Key already exists

put-update-trace.txt

Trace

put("B", 999) when B already exists:
═══════════════════════════════════════════════════════════════════
BEFORE:
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }
List: HEAD ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
node = map.get("B")  // Returns NodeB
// Key exists! This is an update, not an insert.
 
STEP 2: Update value — O(1)
node.value = 999     // NodeB now contains 999
 
STEP 3: Move to head — O(1)
removeNode(node)     // Disconnect from current position
addToHead(node)      // Insert after head sentinel
 
═══════════════════════════════════════════════════════════════════
AFTER:
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }  // Same references
List: HEAD ←→ [B:999] ←→ [C:300] ←→ [A:100] ←→ TAIL
                ↑ B updated and moved to front

Case 2: Key doesn't exist, no eviction needed

put-insert-trace.txt

Trace

put("D", 400) when D doesn't exist, capacity = 4:
═══════════════════════════════════════════════════════════════════
BEFORE (size = 3, capacity = 4):
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC }
List: HEAD ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
node = map.get("D")  // Returns undefined
// Key doesn't exist! This is an insert.
 
STEP 2: Check capacity — O(1)
if (size >= capacity) { evict() }  // size=3 < capacity=4, no eviction
 
STEP 3: Create new node — O(1)
newNode = new Node("D", 400)
 
STEP 4: Add to hash map — O(1)
map.set("D", newNode)
 
STEP 5: Add to head of list — O(1)
addToHead(newNode)
 
═══════════════════════════════════════════════════════════════════
AFTER (size = 4):
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC, "D" → NodeD }
List: HEAD ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
                ↑ D is most recent

Case 3: Key doesn't exist, eviction required

put-eviction-trace.txt

Trace

put("E", 500) when E doesn't exist, capacity = 4, size = 4:
═══════════════════════════════════════════════════════════════════
BEFORE (size = 4, capacity = 4 — FULL):
HashMap: { "A" → NodeA, "B" → NodeB, "C" → NodeC, "D" → NodeD }
List: HEAD ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ [A:100] ←→ TAIL
                                                   ↑ A is LRU (eviction target)
 
═══════════════════════════════════════════════════════════════════
STEP 1: Hash map lookup — O(1)
node = map.get("E")  // Returns undefined - new key
 
STEP 2: Check capacity — triggers eviction!
if (size >= capacity) { evict() }  // size=4 >= capacity=4, must evict
 
    EVICTION SUB-STEPS:
    ─────────────────────────────────────────────────────────────
    a) Find LRU node — O(1)
       lruNode = tail.prev  // NodeA (the one before tail sentinel)
    
    b) Remove from linked list — O(1)
       removeNode(lruNode)
    
    c) Remove from hash map — O(1)
       // This is why we store the key in the node!
       map.delete(lruNode.key)  // map.delete("A")
    ─────────────────────────────────────────────────────────────
 
Intermediate state:
HashMap: { "B" → NodeB, "C" → NodeC, "D" → NodeD }  // A removed
List: HEAD ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ TAIL
 
STEP 3: Create new node — O(1)
newNode = new Node("E", 500)
 
STEP 4: Add to hash map — O(1)
map.set("E", newNode)
 
STEP 5: Add to head of list — O(1)
addToHead(newNode)
 
═══════════════════════════════════════════════════════════════════
AFTER (size = 4):
HashMap: { "B" → NodeB, "C" → NodeC, "D" → NodeD, "E" → NodeE }
List: HEAD ←→ [E:500] ←→ [D:400] ←→ [C:300] ←→ [B:200] ←→ TAIL
                ↑ E is most recent        B is now LRU (was second-oldest)

Critical: Remove from Hash Map During Eviction

Invariants and Consistency

For the LRU cache to function correctly, certain conditions must always be true. These are called invariants. Violating any invariant leads to bugs.

The LRU Cache Invariants:

Must Always Be True

•Size Invariant: map.size equals the number of real nodes in the linked list (excluding sentinels)
•Capacity Invariant: map.size <= capacity — the cache never exceeds its capacity
•Bijection Invariant: Every key in the map has exactly one corresponding node in the list, and vice versa
•Pointer Invariant: For every real node N: N.prev.next === N and N.next.prev === N (bidirectional links are consistent)
•Sentinel Invariant: head.prev === null and tail.next === null — sentinels mark boundaries
•Order Invariant: Nodes are ordered from most to least recently accessed when traversing head → tail

Common invariant violations and their symptoms:

Invariant Violations and Debugging
Violation	Symptom	Likely Cause
Map size ≠ list size	Memory leak or missing items	Forgot to add/remove from one structure
Size > capacity	Eviction not triggered	Capacity check uses > instead of >=
Stale map entry	get() returns wrong/deleted value	Removed from list but not map during eviction
Broken prev/next link	Traversal skips nodes or crashes	Pointer update in wrong order
Lost reference	Node unreachable	Overwrote pointer before reading old value

Defensive Invariant Checking

Why This Design is Optimal

Let's formally verify that our hash map + doubly linked list design achieves the O(1) requirements.

Time complexity analysis:

Complete Operation Complexity Breakdown
Operation	Sub-operations	Each Sub-op	Total
get(key)	map.get + removeNode + addToHead	O(1) + O(1) + O(1)	O(1)
put(key, value) - update	map.get + update value + removeNode + addToHead	O(1) each	O(1)
put(key, value) - insert	map.get + new Node + map.set + addToHead	O(1) each	O(1)
put(key, value) - evict	Above + tail.prev + removeNode + map.delete	O(1) each	O(1)

Space complexity analysis:

Hash map: O(n) for n entries
Doubly linked list: O(n) for n nodes, but these ARE the same data
Sentinel nodes: O(1) — just 2 extra nodes regardless of n
Total: O(n) where n is the cache capacity

Why this is (essentially) optimal:

Any cache must store n items → Ω(n) space is unavoidable
Any correct LRU must track recency → need n ordered elements
O(1) access requires direct addressing → need hash-based structure
O(1) reordering requires prev/next pointers → need doubly linked structure

The only additional overhead is the constant factor of pointer storage and the two sentinel nodes — both unavoidable given our requirements.

No known alternative achieves O(1) get and O(1) put with less overhead. This design is the canonical solution taught in advanced data structures courses and used in production systems worldwide.

A Timeless Design Pattern

Summary: The Design Foundation

We've covered the complete design of an O(1) LRU cache. Let's consolidate the key insights:

Key Takeaways

•Two structures, one purpose — Hash map provides O(1) lookup; doubly linked list provides O(1) ordering operations. Together they achieve what neither can alone.
•Store node references, not values — The hash map values are pointers to linked list nodes. This enables O(1) access to any node by key.
•Sentinel nodes simplify everything — Dummy head and tail nodes eliminate null checks and special cases, making code cleaner and less bug-prone.
•Both structures must stay synchronized — Every insert/delete must update both the hash map and the linked list. Forgetting either causes bugs.
•Move-to-front on every access — Both get() and put() move the accessed key to the front, maintaining the recency invariant.
•Eviction uses the tail — The LRU item is always at tail.prev, giving O(1) access to the eviction target.

What's next:

Page Complete