LRU Cache - Learning Module

Loading content...

0/276

Requirements: O(1) get and put

The O(1) Mandate

In the world of caching, performance isn't just desirable — it's existential. A cache that takes O(n) time per operation defeats its own purpose. If accessing cached data takes longer than fetching from the original source, why have a cache at all?

The LRU cache interview question almost universally specifies: implement get and put with O(1) average time complexity. This isn't arbitrary — it reflects the real-world requirement that caches must be blindingly fast, no matter how many items they contain.

But achieving O(1) for both operations simultaneously is surprisingly tricky. In this page, we'll rigorously analyze what O(1) means for LRU, why this requirement is non-negotiable, and what constraints it places on our implementation approach.

What You Will Learn

By the end of this page, you will understand exactly why O(1) time complexity is required for production LRU caches, what specific sub-operations must each be O(1), and why naive approaches fail to meet these requirements. You'll develop a clear mental model of the algorithmic constraints that will guide our design.

Why O(1) Matters

Let's quantify why O(1) isn't just nice-to-have — it's mandatory for any cache at scale.

The Cache Access Paradox:

A cache exists to avoid slow operations. If accessing the cache itself becomes slow, the cure becomes worse than the disease. Consider the access time breakdown:

Total Time = Cache Lookup Time + Miss Penalty × Miss Rate

If your cache has 100,000 items and lookup takes O(n), that's 100,000 operations per lookup — potentially milliseconds even for in-memory operations. At that point, the cache lookup might be slower than just querying the database directly.

Time Complexity Impact at Scale
Cache Size	O(1) get/put	O(log n) get/put	O(n) get/put
1,000	~100 ns	~1 μs (10x slower)	~100 μs (1000x slower)
10,000	~100 ns	~1.3 μs	~1 ms
100,000	~100 ns	~1.7 μs	~10 ms
1,000,000	~100 ns	~2 μs	~100 ms
10,000,000	~100 ns	~2.3 μs	~1 second

Notice how O(1) remains constant regardless of size, while O(n) becomes catastrophic. With 10 million cache entries and O(n) operations, each cache lookup takes a full second — utterly useless.

Real production requirements:

Let's consider a realistic production scenario:

Web application serving 10,000 requests/second
Each request makes 5 cache lookups
Total: 50,000 cache operations per second

Time budget per operation: 1,000,000 μs ÷ 50,000 = 20 μs maximum

With O(1) operations at ~100ns each, we use 0.5% of our time budget — excellent. With O(n) at 100,000 items, we'd need ~10,000 μs per operation — a 500x overrun.

The Hidden Constant Factor

O(1) doesn't mean instant — it means constant time regardless of input size. An O(1) operation that takes 1ms is worse than an O(log n) operation that takes 100ns. In practice, well-implemented LRU caches achieve ~100-500 nanoseconds per operation, making them suitable for millions of operations per second.

Decomposing the Operations

To design an O(1) LRU cache, we must first understand exactly what sub-operations each method performs. Let's decompose get and put into their atomic steps.

get(key) decomposition:

get-decomposition.pseudo

Pseudocode

get(key):
    // Step 1: LOOKUP — Find the key in the cache
    item = lookup(key)              // Must be O(1)
    
    if item is null:
        return null (cache miss)
    
    // Step 2: UPDATE RECENCY — Move item to "most recently used" position
    move_to_front(item)             // Must be O(1)
    
    // Step 3: RETURN VALUE — Return the cached value
    return item.value               // O(1) - trivial

put(key, value) decomposition:

put-decomposition.pseudo

Pseudocode

put(key, value):
    // Step 1: LOOKUP — Check if key already exists
    item = lookup(key)              // Must be O(1)
    
    if item is not null:
        // Step 2a: UPDATE — Update existing item's value
        item.value = value          // O(1) - direct assignment
        
        // Step 2b: UPDATE RECENCY — Move to front
        move_to_front(item)         // Must be O(1)
    else:
        // Step 3: CHECK CAPACITY — Evict if full
        if size >= capacity:
            lru_item = find_lru()   // Must be O(1)
            remove(lru_item)        // Must be O(1)
        
        // Step 4: INSERT — Add new item at front
        new_item = create(key, value)
        insert_at_front(new_item)   // Must be O(1)
        add_to_lookup(key, new_item)// Must be O(1)

The O(1) requirement breakdown:

For both get and put to be O(1), every sub-operation must be O(1). One O(n) sub-operation would dominate and make the entire operation O(n).

Here are the atomic operations we need:

Required O(1) Operations

•lookup(key) — Find an item by its key → Hash map gives us this
•move_to_front(item) — Move an arbitrary item to the front of recency order → Arrays can't do this in O(1)
•find_lru() — Get the least recently used item → Need direct access to the tail
•remove(item) — Remove an arbitrary item from the middle → Arrays can't do this in O(1)
•insert_at_front(item) — Add a new item at the front → Need direct access to the head

The Critical Insight

The tricky operations are move_to_front and remove from an arbitrary position. These require simultaneously knowing an item's position in the recency order AND being able to modify that position in O(1) time. No single standard data structure provides both capabilities.

Why Arrays Fail

Arrays seem like a natural choice for maintaining order, but they fundamentally cannot support O(1) arbitrary removal or insertion.

Array-based recency tracking:

Imagine maintaining recency as an array where index 0 is most recent and the last index is least recent:

array-based-lru.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
// Array-based LRU attempt (FLAWED)
class ArrayLRU<K, V> {
    private map: Map<K, V>;
    private recencyOrder: K[];  // Index 0 = most recent
    private capacity: number;
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.map = new Map();
        this.recencyOrder = [];
    }
 
    get(key: K): V | null {
        if (!this.map.has(key)) return null;
        
        // Move key to front — O(n) operation!
        const index = this.recencyOrder.indexOf(key);  // O(n) search
        this.recencyOrder.splice(index, 1);            // O(n) shift
        this.recencyOrder.unshift(key);                // O(n) shift
        
        return this.map.get(key)!;
    }
 
    put(key: K, value: V): void {
        if (this.map.has(key)) {
            this.map.set(key, value);
            // Move to front — O(n)
            const index = this.recencyOrder.indexOf(key);
            this.recencyOrder.splice(index, 1);
            this.recencyOrder.unshift(key);
        } else {
            if (this.map.size >= this.capacity) {
                // Evict LRU — O(1) for pop, but moving was O(n)
                const lruKey = this.recencyOrder.pop()!;
                this.map.delete(lruKey);
            }
            this.map.set(key, value);
            this.recencyOrder.unshift(key);  // O(n) shift
        }
    }
}

Why this fails:

indexOf/remove is O(n) — Finding an element's position in an array requires linear search
splice/insert at position 0 is O(n) — All existing elements must shift right
Removing from the middle is O(n) — All elements after the removed one must shift left

With n=100,000 elements, each get or put involves ~100,000 comparisons and shifts. The O(1) hash map lookup is dwarfed by the O(n) array operations.

The Array Trap

Arrays provide O(1) access by index, but LRU access is by key, not index. We don't know an item's array index without searching. And even if we did, inserting/removing at arbitrary positions requires shifting elements — inherently O(n).

Why Standard Data Structures Fail

Let's systematically evaluate common data structures against our requirements. Each succeeds at some operations but fails at others.

Hash Map alone:

Hash Map Capability Analysis
Operation	Complexity	Verdict
lookup(key)	O(1) average	✓ Perfect
insert/update(key, value)	O(1) average	✓ Perfect
remove(key)	O(1) average	✓ Perfect
find_lru()	O(n) — must scan all entries	✗ Fails
move_to_front(item)	N/A — no ordering	✗ No concept of order

Hash maps provide perfect key-based access but have no concept of ordering. You can't ask a hash map "What was the least recently added item?" without scanning all entries.

Singly Linked List alone:

Singly Linked List Capability Analysis
Operation	Complexity	Verdict
lookup(key)	O(n) — must traverse list	✗ Too slow
insert_at_front(item)	O(1)	✓ Perfect
find_lru() (tail)	O(n) unless we track tail	✗/✓ With tail pointer
remove(item)	O(n) — must find predecessor	✗ Fundamental issue

Singly linked lists allow O(1) insertion at head, but removing an arbitrary node requires finding its predecessor — which takes O(n) traversal.

Binary Search Tree (BST):

BST Capability Analysis (ordered by access timestamp)
Operation	Complexity	Verdict
lookup(key)	Keys aren't timestamps — still O(n)	✗ Wrong ordering
find_lru() (min)	O(log n) balanced	✗ Not O(1)
insert	O(log n) balanced	✗ Not O(1)
remove(item)	O(log n) balanced	✗ Not O(1)

The Fundamental Gap

No single standard data structure provides: • O(1) key-based lookup • O(1) ordering manipulation (move to front, remove from middle) • O(1) access to both ends (newest and oldest)

The solution requires combining multiple structures that complement each other's weaknesses.

The Key Insight — Doubly Linked Lists

To remove a node from a linked list in O(1), we must be able to update both its predecessor and successor. This is impossible with a singly linked list (we don't have the predecessor), but doubly linked lists solve this problem.

How doubly linked lists enable O(1) removal:

dll-removal.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
/**
 * Node in a doubly linked list
 * Each node knows both its predecessor and successor
 */
class DoublyLinkedNode<K, V> {
    key: K;
    value: V;
    prev: DoublyLinkedNode<K, V> | null = null;
    next: DoublyLinkedNode<K, V> | null = null;
 
    constructor(key: K, value: V) {
        this.key = key;
        this.value = value;
    }
}
 
/**
 * O(1) removal from a doubly linked list
 * Given direct access to a node, we can remove it without traversal
 */
function removeNode<K, V>(node: DoublyLinkedNode<K, V>): void {
    // Step 1: Link predecessor to successor
    if (node.prev !== null) {
        node.prev.next = node.next;
    }
    
    // Step 2: Link successor to predecessor
    if (node.next !== null) {
        node.next.prev = node.prev;
    }
    
    // Step 3: Clear the node's links (optional, helps GC)
    node.prev = null;
    node.next = null;
    
    // Total: 4 pointer updates = O(1)
}

The magic of O(1) arbitrary removal:

With a doubly linked list, if we have a direct reference to a node, we can:

Look at node.prev to find the predecessor
Look at node.next to find the successor
Update node.prev.next to point to the successor
Update node.next.prev to point to the predecessor

This requires exactly 4 pointer updates — O(1) regardless of the list's length.

But how do we get that direct reference?

Here's the breakthrough insight: the hash map doesn't just store values — it stores pointers to nodes.

The Eureka Moment

Instead of: HashMap<Key, Value>

Use: HashMap<Key, DoublyLinkedNode<Key, Value>>

The hash map gives O(1) access to the node. With the node, the doubly linked list gives O(1) removal. Synergy!

Amortized vs Worst-Case O(1)

When we say LRU cache provides O(1) operations, we typically mean amortized O(1), not worst-case. Understanding this distinction is important for production systems.

Amortized O(1):

Most operations complete in O(1), but occasionally an operation takes longer. When averaged over many operations, the time per operation is constant.

For hash maps, this happens during resizing: when the load factor exceeds a threshold, the hash map allocates a new array and rehashes all entries — an O(n) operation. But if done infrequently (every O(n) insertions), the amortized cost per insert remains O(1).

Worst-case O(1):

Every single operation, without exception, completes in O(1). This is harder to achieve but sometimes necessary for real-time systems.

Time Complexity Breakdown for LRU Cache
Component	Operation	Amortized	Worst-Case
Hash Map	get/put	O(1)	O(n) during resize
Doubly Linked List	insert at head	O(1)	O(1)
Doubly Linked List	remove node	O(1)	O(1)
Doubly Linked List	access tail	O(1)	O(1)
Overall LRU	get	O(1)	O(n) during resize
Overall LRU	put	O(1)	O(n) during resize

In practice:

For most applications, amortized O(1) is acceptable. Hash map resizes are rare (only when the map grows significantly), and modern hash map implementations are highly optimized.

For hard real-time systems (aerospace, medical devices), where every operation must complete within a deadline, you'd need:

Pre-allocate the hash map to final size (no resizing)
Use open addressing with bounded probing
Consider specialized data structures like cuckoo hashing

For interview purposes and most production code, amortized O(1) using standard library hash maps is the expected answer.

Interview Tip

When asked about time complexity in an interview, clarify: "The hash map gives us amortized O(1), and the doubly linked list operations are all worst-case O(1). So overall, we achieve amortized O(1) for both get and put." This demonstrates you understand the nuance.

Space Complexity Considerations

While time complexity gets the spotlight, space complexity matters too — especially for caches, which often hold millions of entries.

Memory overhead analysis:

For an LRU cache with n entries where each key-value pair has size S:

Hash Map overhead:

Entry array: ~n × (hash + pointer size) = n × 16 bytes (64-bit)
Load factor typically 0.75, so actual array size ≈ 1.33n
Total: ~21 bytes per entry

Doubly Linked List overhead:

Each node: key + value + 2 pointers = S + 16 bytes
Head/tail sentinels: 2 × 16 = 32 bytes (constant)
Total: 16 bytes per entry + 32 constant

Combined overhead:

space-analysis.txt

Analysis

LRU Cache Memory Layout (per entry):
┌─────────────────────────────────────┐
│  HASH MAP ENTRY                     │
│  ├── Hash code:      4-8 bytes      │
│  └── Pointer to node: 8 bytes       │
│  Total: 12-16 bytes                 │
└─────────────────────────────────────┘
┌─────────────────────────────────────┐
│  DOUBLY LINKED NODE                 │
│  ├── Key:           variable        │
│  ├── Value:         variable        │
│  ├── Prev pointer:  8 bytes         │
│  └── Next pointer:  8 bytes         │
│  Total: 16 bytes + key/value size   │
└─────────────────────────────────────┘
 
Overall per-entry overhead: ~28-32 bytes + key + value
 
For 1 million entries with 100-byte key+value:
  - Data: 100 MB
  - Overhead: ~30 MB
  - Total: ~130 MB (30% overhead)
 
For 1 million entries with 10-byte key+value:
  - Data: 10 MB
  - Overhead: ~30 MB
  - Total: ~40 MB (75% overhead!)

Key insight: The overhead is fixed per entry, regardless of value size. This means:

For large values, overhead is negligible (a few percent)
For small values, overhead can dominate (>50%)

If your cache stores small integers or short strings, the pointer overhead might exceed the data itself. Consider whether the LRU functionality is worth the memory cost.

Space-Time Tradeoff

We're paying extra space (the linked list pointers) to gain O(1) time. With just a hash map + timestamps, we'd save 16 bytes per entry but pay O(n) per eviction. For caches that evict frequently, the time savings vastly outweigh the space cost.

The Complete Requirements

Let's crystallize everything into a precise requirements specification that our implementation must satisfy.

LRU Cache Requirements Specification

•Capacity-Limited — The cache holds at most capacity key-value pairs. When at capacity, inserting a new key triggers eviction.
•O(1) get(key) — Returns the value for key if present, null/-1 otherwise. If present, marks key as most recently used.
•O(1) put(key, value) — If key exists, updates its value. If not, inserts the pair. Either way, marks key as most recently used. Evicts LRU if at capacity.
•LRU Eviction — When eviction is needed, the key that has gone longest without being accessed (by get or put) is removed.
•Space: O(capacity) — Memory usage is proportional to capacity, not to the number of operations performed.

Data structure requirements derived from the above:

Derived Requirements → Data Structure Choices
Requirement	Needed Capability	Provided By
O(1) get by key	Fast key lookup	Hash Map
O(1) update recency	Move node to front	Doubly Linked List
O(1) evict LRU	Access tail + remove	DLL with tail pointer
O(1) remove by key	Find node + remove from list	Hash Map → Node + DLL

What's next:

Now that we understand exactly what requirements we must satisfy and why, the next page presents the elegant solution: combining a hash map with a doubly linked list. We'll see how these two structures complement each other perfectly, with the hash map providing O(1) access and the doubly linked list providing O(1) ordering operations.

Page Complete

You now understand why O(1) operations are mandatory for LRU caches, what specific sub-operations must be O(1), and why no single standard data structure suffices. The stage is set for the elegant hash map + doubly linked list solution.

Requirements: O(1) get and put

The O(1) Mandate

What You Will Learn

Why O(1) Matters

Let's quantify why O(1) isn't just nice-to-have — it's mandatory for any cache at scale.

The Cache Access Paradox:

A cache exists to avoid slow operations. If accessing the cache itself becomes slow, the cure becomes worse than the disease. Consider the access time breakdown:

Total Time = Cache Lookup Time + Miss Penalty × Miss Rate

Time Complexity Impact at Scale
Cache Size	O(1) get/put	O(log n) get/put	O(n) get/put
1,000	~100 ns	~1 μs (10x slower)	~100 μs (1000x slower)
10,000	~100 ns	~1.3 μs	~1 ms
100,000	~100 ns	~1.7 μs	~10 ms
1,000,000	~100 ns	~2 μs	~100 ms
10,000,000	~100 ns	~2.3 μs	~1 second

Notice how O(1) remains constant regardless of size, while O(n) becomes catastrophic. With 10 million cache entries and O(n) operations, each cache lookup takes a full second — utterly useless.

Real production requirements:

Let's consider a realistic production scenario:

Web application serving 10,000 requests/second
Each request makes 5 cache lookups
Total: 50,000 cache operations per second

Time budget per operation: 1,000,000 μs ÷ 50,000 = 20 μs maximum

With O(1) operations at ~100ns each, we use 0.5% of our time budget — excellent. With O(n) at 100,000 items, we'd need ~10,000 μs per operation — a 500x overrun.

The Hidden Constant Factor

Decomposing the Operations

To design an O(1) LRU cache, we must first understand exactly what sub-operations each method performs. Let's decompose get and put into their atomic steps.

get(key) decomposition:

get-decomposition.pseudo

Pseudocode

get(key):
    // Step 1: LOOKUP — Find the key in the cache
    item = lookup(key)              // Must be O(1)
    
    if item is null:
        return null (cache miss)
    
    // Step 2: UPDATE RECENCY — Move item to "most recently used" position
    move_to_front(item)             // Must be O(1)
    
    // Step 3: RETURN VALUE — Return the cached value
    return item.value               // O(1) - trivial

put(key, value) decomposition:

put-decomposition.pseudo

Pseudocode

put(key, value):
    // Step 1: LOOKUP — Check if key already exists
    item = lookup(key)              // Must be O(1)
    
    if item is not null:
        // Step 2a: UPDATE — Update existing item's value
        item.value = value          // O(1) - direct assignment
        
        // Step 2b: UPDATE RECENCY — Move to front
        move_to_front(item)         // Must be O(1)
    else:
        // Step 3: CHECK CAPACITY — Evict if full
        if size >= capacity:
            lru_item = find_lru()   // Must be O(1)
            remove(lru_item)        // Must be O(1)
        
        // Step 4: INSERT — Add new item at front
        new_item = create(key, value)
        insert_at_front(new_item)   // Must be O(1)
        add_to_lookup(key, new_item)// Must be O(1)

The O(1) requirement breakdown:

For both get and put to be O(1), every sub-operation must be O(1). One O(n) sub-operation would dominate and make the entire operation O(n).

Here are the atomic operations we need:

Required O(1) Operations

•lookup(key) — Find an item by its key → Hash map gives us this
•move_to_front(item) — Move an arbitrary item to the front of recency order → Arrays can't do this in O(1)
•find_lru() — Get the least recently used item → Need direct access to the tail
•remove(item) — Remove an arbitrary item from the middle → Arrays can't do this in O(1)
•insert_at_front(item) — Add a new item at the front → Need direct access to the head

The Critical Insight

Why Arrays Fail

Arrays seem like a natural choice for maintaining order, but they fundamentally cannot support O(1) arbitrary removal or insertion.

Array-based recency tracking:

Imagine maintaining recency as an array where index 0 is most recent and the last index is least recent:

array-based-lru.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
// Array-based LRU attempt (FLAWED)
class ArrayLRU<K, V> {
    private map: Map<K, V>;
    private recencyOrder: K[];  // Index 0 = most recent
    private capacity: number;
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.map = new Map();
        this.recencyOrder = [];
    }
 
    get(key: K): V | null {
        if (!this.map.has(key)) return null;
        
        // Move key to front — O(n) operation!
        const index = this.recencyOrder.indexOf(key);  // O(n) search
        this.recencyOrder.splice(index, 1);            // O(n) shift
        this.recencyOrder.unshift(key);                // O(n) shift
        
        return this.map.get(key)!;
    }
 
    put(key: K, value: V): void {
        if (this.map.has(key)) {
            this.map.set(key, value);
            // Move to front — O(n)
            const index = this.recencyOrder.indexOf(key);
            this.recencyOrder.splice(index, 1);
            this.recencyOrder.unshift(key);
        } else {
            if (this.map.size >= this.capacity) {
                // Evict LRU — O(1) for pop, but moving was O(n)
                const lruKey = this.recencyOrder.pop()!;
                this.map.delete(lruKey);
            }
            this.map.set(key, value);
            this.recencyOrder.unshift(key);  // O(n) shift
        }
    }
}

Why this fails:

indexOf/remove is O(n) — Finding an element's position in an array requires linear search
splice/insert at position 0 is O(n) — All existing elements must shift right
Removing from the middle is O(n) — All elements after the removed one must shift left

With n=100,000 elements, each get or put involves ~100,000 comparisons and shifts. The O(1) hash map lookup is dwarfed by the O(n) array operations.

The Array Trap

Why Standard Data Structures Fail

Let's systematically evaluate common data structures against our requirements. Each succeeds at some operations but fails at others.

Hash Map alone:

Hash Map Capability Analysis
Operation	Complexity	Verdict
lookup(key)	O(1) average	✓ Perfect
insert/update(key, value)	O(1) average	✓ Perfect
remove(key)	O(1) average	✓ Perfect
find_lru()	O(n) — must scan all entries	✗ Fails
move_to_front(item)	N/A — no ordering	✗ No concept of order

Hash maps provide perfect key-based access but have no concept of ordering. You can't ask a hash map "What was the least recently added item?" without scanning all entries.

Singly Linked List alone:

Singly Linked List Capability Analysis
Operation	Complexity	Verdict
lookup(key)	O(n) — must traverse list	✗ Too slow
insert_at_front(item)	O(1)	✓ Perfect
find_lru() (tail)	O(n) unless we track tail	✗/✓ With tail pointer
remove(item)	O(n) — must find predecessor	✗ Fundamental issue

Singly linked lists allow O(1) insertion at head, but removing an arbitrary node requires finding its predecessor — which takes O(n) traversal.

Binary Search Tree (BST):

BST Capability Analysis (ordered by access timestamp)
Operation	Complexity	Verdict
lookup(key)	Keys aren't timestamps — still O(n)	✗ Wrong ordering
find_lru() (min)	O(log n) balanced	✗ Not O(1)
insert	O(log n) balanced	✗ Not O(1)
remove(item)	O(log n) balanced	✗ Not O(1)

The Fundamental Gap

No single standard data structure provides: • O(1) key-based lookup • O(1) ordering manipulation (move to front, remove from middle) • O(1) access to both ends (newest and oldest)

The solution requires combining multiple structures that complement each other's weaknesses.

The Key Insight — Doubly Linked Lists

How doubly linked lists enable O(1) removal:

dll-removal.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
/**
 * Node in a doubly linked list
 * Each node knows both its predecessor and successor
 */
class DoublyLinkedNode<K, V> {
    key: K;
    value: V;
    prev: DoublyLinkedNode<K, V> | null = null;
    next: DoublyLinkedNode<K, V> | null = null;
 
    constructor(key: K, value: V) {
        this.key = key;
        this.value = value;
    }
}
 
/**
 * O(1) removal from a doubly linked list
 * Given direct access to a node, we can remove it without traversal
 */
function removeNode<K, V>(node: DoublyLinkedNode<K, V>): void {
    // Step 1: Link predecessor to successor
    if (node.prev !== null) {
        node.prev.next = node.next;
    }
    
    // Step 2: Link successor to predecessor
    if (node.next !== null) {
        node.next.prev = node.prev;
    }
    
    // Step 3: Clear the node's links (optional, helps GC)
    node.prev = null;
    node.next = null;
    
    // Total: 4 pointer updates = O(1)
}

The magic of O(1) arbitrary removal:

With a doubly linked list, if we have a direct reference to a node, we can:

Look at node.prev to find the predecessor
Look at node.next to find the successor
Update node.prev.next to point to the successor
Update node.next.prev to point to the predecessor

This requires exactly 4 pointer updates — O(1) regardless of the list's length.

But how do we get that direct reference?

Here's the breakthrough insight: the hash map doesn't just store values — it stores pointers to nodes.

The Eureka Moment

Instead of: HashMap<Key, Value>

Use: HashMap<Key, DoublyLinkedNode<Key, Value>>

The hash map gives O(1) access to the node. With the node, the doubly linked list gives O(1) removal. Synergy!

Amortized vs Worst-Case O(1)

When we say LRU cache provides O(1) operations, we typically mean amortized O(1), not worst-case. Understanding this distinction is important for production systems.

Amortized O(1):

Most operations complete in O(1), but occasionally an operation takes longer. When averaged over many operations, the time per operation is constant.

Worst-case O(1):

Every single operation, without exception, completes in O(1). This is harder to achieve but sometimes necessary for real-time systems.

Time Complexity Breakdown for LRU Cache
Component	Operation	Amortized	Worst-Case
Hash Map	get/put	O(1)	O(n) during resize
Doubly Linked List	insert at head	O(1)	O(1)
Doubly Linked List	remove node	O(1)	O(1)
Doubly Linked List	access tail	O(1)	O(1)
Overall LRU	get	O(1)	O(n) during resize
Overall LRU	put	O(1)	O(n) during resize

In practice:

For most applications, amortized O(1) is acceptable. Hash map resizes are rare (only when the map grows significantly), and modern hash map implementations are highly optimized.

For hard real-time systems (aerospace, medical devices), where every operation must complete within a deadline, you'd need:

Pre-allocate the hash map to final size (no resizing)
Use open addressing with bounded probing
Consider specialized data structures like cuckoo hashing

For interview purposes and most production code, amortized O(1) using standard library hash maps is the expected answer.

Interview Tip

Space Complexity Considerations

While time complexity gets the spotlight, space complexity matters too — especially for caches, which often hold millions of entries.

Memory overhead analysis:

For an LRU cache with n entries where each key-value pair has size S:

Hash Map overhead:

Entry array: ~n × (hash + pointer size) = n × 16 bytes (64-bit)
Load factor typically 0.75, so actual array size ≈ 1.33n
Total: ~21 bytes per entry

Doubly Linked List overhead:

Each node: key + value + 2 pointers = S + 16 bytes
Head/tail sentinels: 2 × 16 = 32 bytes (constant)
Total: 16 bytes per entry + 32 constant

Combined overhead:

space-analysis.txt

Analysis

LRU Cache Memory Layout (per entry):
┌─────────────────────────────────────┐
│  HASH MAP ENTRY                     │
│  ├── Hash code:      4-8 bytes      │
│  └── Pointer to node: 8 bytes       │
│  Total: 12-16 bytes                 │
└─────────────────────────────────────┘
┌─────────────────────────────────────┐
│  DOUBLY LINKED NODE                 │
│  ├── Key:           variable        │
│  ├── Value:         variable        │
│  ├── Prev pointer:  8 bytes         │
│  └── Next pointer:  8 bytes         │
│  Total: 16 bytes + key/value size   │
└─────────────────────────────────────┘
 
Overall per-entry overhead: ~28-32 bytes + key + value
 
For 1 million entries with 100-byte key+value:
  - Data: 100 MB
  - Overhead: ~30 MB
  - Total: ~130 MB (30% overhead)
 
For 1 million entries with 10-byte key+value:
  - Data: 10 MB
  - Overhead: ~30 MB
  - Total: ~40 MB (75% overhead!)

Key insight: The overhead is fixed per entry, regardless of value size. This means:

For large values, overhead is negligible (a few percent)
For small values, overhead can dominate (>50%)

If your cache stores small integers or short strings, the pointer overhead might exceed the data itself. Consider whether the LRU functionality is worth the memory cost.

Space-Time Tradeoff

The Complete Requirements

Let's crystallize everything into a precise requirements specification that our implementation must satisfy.

LRU Cache Requirements Specification

•Capacity-Limited — The cache holds at most capacity key-value pairs. When at capacity, inserting a new key triggers eviction.
•O(1) get(key) — Returns the value for key if present, null/-1 otherwise. If present, marks key as most recently used.
•O(1) put(key, value) — If key exists, updates its value. If not, inserts the pair. Either way, marks key as most recently used. Evicts LRU if at capacity.
•LRU Eviction — When eviction is needed, the key that has gone longest without being accessed (by get or put) is removed.
•Space: O(capacity) — Memory usage is proportional to capacity, not to the number of operations performed.

Data structure requirements derived from the above:

Derived Requirements → Data Structure Choices
Requirement	Needed Capability	Provided By
O(1) get by key	Fast key lookup	Hash Map
O(1) update recency	Move node to front	Doubly Linked List
O(1) evict LRU	Access tail + remove	DLL with tail pointer
O(1) remove by key	Find node + remove from list	Hash Map → Node + DLL

What's next:

Page Complete