advanced12 min read·Updated October 9, 2026

LRU Cache Explained: Tracing Capacity 2 Step by Step

Master the LRU cache design pattern with a full walkthrough of a capacity 2 sequence. Build the dual-data mental model with hash map and linked list.

By Learnisim AI·Published October 9, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Hash map operations in O(1)
  • Doubly linked list pointer manipulation
  • Basic class-based object orientation
LRU Cache (Capacity = 2) Step-by-Step Trace Dual Data Structure: Hash Map (O(1) lookup) + Doubly Linked List (O(1) eviction) Dual-Data-Structure Model Hash Map Key -> Node* Linked List Head(MRU) <-> Tail(LRU) get(k): O(1) time put(k,v): evict tail if size > 2 Sequence Execution: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4)... 1. put(1,1) & put(2,2) MRU [2:2] <-> [1:1] LRU Capacity: 2 / 2 2. get(1) Returns 1 (Key 1 fresh) MRU [1:1] <-> [2:2] LRU 3. put(3,3) Evicts key 2! [3:3] <-> [1:1] 4. get(2) Returns -1 Key 2 was evicted 5. put(4,4) Evicts LRU key 1 [4:4] <-> [3:3] 6. get(1) Returns -1 Key 1 evicted earlier 7. get(3) Returns 3 (Key 3 fresh) MRU [3:3] <-> [4:4] LRU 8. get(4) Returns 4 MRU [4:4] <-> [3:3] Final Cache State: Keys 3 and 4 retained in memory. O(1) operations achieved! Why Naive Approaches Fail Arrays: O(N) shift on insert/delete Hash Map alone: no ordering Random eviction: drops hot items LRU Solution: Map + DLL Guarantees strict O(1) time complexity for both get and put operations.
Capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4) overview diagram
Why

Why Standard Caches Fall Short When Memory is Limited

Phase 1: The Bottleneck of Unbounded Growth

Imagine you are building a high-throughput microservice that frequently fetches user profiles from a remote database. Every query latency hit costs milliseconds, so you decide to store results in memory. But RAM is finite; you cannot store all one million profiles forever. When memory hits its absolute limit, your application faces a brutal choice: throw an out-of-memory exception or discard something.
Consider our working example with a strict Capacity 2: we execute put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4). If we use a naive array or standard dictionary without eviction logic, storing key 3 will either crash the program or cause memory bloat. If we implement a random eviction policy, we might accidentally throw away key 1, which was just accessed moments ago, tanking our cache hit ratio.
We need an eviction strategy that makes a principled guarantee: when capacity is exhausted, discard the item that has been idle the longest. This is the Least Recently Used (LRU) guarantee. Without a specialized data structure combining a hash map and a doubly linked list, checking and reordering items on every get or put operation degrades from constant time to a sluggish linear scan.
LRU Cache (Capacity = 2): Step-by-Step Eviction Walkthrough 1. put(1, 1) [1: 1] (MRU) empty 2. put(2, 2) [2: 2] (MRU) [1: 1] (LRU) 3. get(1) → returns 1 [1: 1] (MRU) [2: 2] (LRU) 4. put(3, 3) — Evicts 2! [3: 3] (MRU) [1: 1] (LRU) 5. get(2) → returns -1 (Miss) [3: 3] (MRU) [1: 1] (LRU) 6. put(4, 4) — Evicts 1! [4: 4] (MRU) [3: 3] (LRU) 7. Final Lookups & State get(1) → -1 (Evicted earlier) get(3) → returns 3 get(4) → returns 4 Why O(1)? Hash Map + Doubly Linked List Architecture Hash Map (Key → Node Address) Provides instant O(1) item lookup Doubly Linked List O(1) reordering & tail eviction
Why Standard Caches Fall Short When Memory is Limited diagram
Model

The Dual-Data-Structure Model: Why We Need Both a Hash Map and a Doubly Linked List

Phase 2: The Two-Pillar Architecture

When working through our locked example LRUCache(2) with operations put(1,1), put(2,2), and get(1), we face a dual constraint: we must locate any key instantly, and we must track which key was accessed least recently so we know what to evict when capacity overflows.
Neither data structure alone can achieve time complexity for both operations. A hash map gives us access by key, but standard hash tables have no concept of chronological order. A doubly linked list gives us insertions and deletions at the ends, but searching for a specific key requires traversing the list in time.

Phase 2: Combining Map and List

The solution is to combine them into a unified structure. The hash map stores keys mapped directly to node pointers inside a doubly linked list. When we execute get(1), the map instantly finds the node, and the list pointers allow us to pluck that node out and move it to the front in constant time.

Phase 2: The Role of Sentinels

To avoid tedious edge-case checks for empty lists or single-element boundaries during our example sequence, we use dummy head and dummy tail sentinel nodes. These fixed anchors ensure that every real insertion or deletion happens between established nodes, keeping pointer arithmetic clean and predictable.
LRU Cache: The Dual-Data-Structure Model (Capacity = 2) Hash Map (O(1) Access) + Doubly Linked List (O(1) Reordering & Eviction) Hash Map (Key → Node Pointer) Key 1 Ptr → [Node 1] Key 3 Ptr → [Node 3] ... other hash buckets ... Why Hash Map? • Instant O(1) key lookup • Bypasses O(N) list traversal • Directly targets node pointers Doubly Linked List (Chronological Order: Most Recent ⇄ Least Recent) HEAD Sentinel Anchor Most Recent Key: 1 | Val: 1 prev ⇄ next MRU / New Key: 3 | Val: 3 prev ⇄ next TAIL Sentinel Anchor next pointer prev pointer Why Doubly Linked List & Sentinels? • O(1) Insertion & Removal: Pluck and re-insert nodes instantly without scanning. • Sentinel Nodes: Dummy head & tail eliminate edge cases (empty list or boundary checks). • O(1) Eviction: Tail's predecessor is always the Least Recently Used item, ready to pop. Result: Combined, they give exact O(1) time complexity for both get() and put()! Map Value
The Dual-Data-Structure Model: Why We Need Both a Hash Map and a Doubly Linked List diagram
Syntax

Syntax and APIs: Writing the LRUCache Class for Capacity 2

Phase 3: Syntax & APIs

To execute our locked example—LRUCache(2) followed by put(1,1), put(2,2), get(1)—we need concrete code structures that glue a hash map to a doubly linked list. In Python, this requires defining a helper Node class alongside the main LRUCache class shell.
The Node needs key, val, prev, and next pointers. The LRUCache class initializes the capacity, a dictionary mapping keys to Node references, and sentinel head/tail nodes to avoid null pointer checks during reordering.
python
class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
When writing this skeleton for our capacity 2 instance, a common mistake is omitting the sentinel nodes or failing to cross-link head.next = tail and tail.prev = head. Without sentinels, every get or put operation requires tedious edge-case checks for empty lists or single-node lists, destroying clean pointer manipulation.
python
class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        # TODO: Initialize capacity, dictionary, and sentinel head/tail nodes
        pass

def get(self, key: int) -> int:
        pass

def put(self, key: int, value: int) -> None:
        pass
Worked example

Tracing the Capacity 2 Sequence Step by Step

Phase 4: Worked Example

To see how the hash map and doubly linked list cooperate in practice, let us execute the complete locked example sequence for an LRUCache of capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4). We will trace the exact state of our internal map (cache) and list (from head to tail) after each operation.

Given

An instance of LRUCache with capacity = 2. The doubly linked list starts with dummy head and dummy tail nodes connected directly to each other.

Steps

1. put(1, 1)
- Action: Key 1 is not in the map. Insert node (1:1) right after head. Map gets 1 -> node1.
- State: List: head <-> node1(1:1) <-> tail. Map: {1: node1}.
2. put(2, 2)
- Action: Key 2 is not in the map. Insert node (2:2) right after head. Map gets 2 -> node2.
- State: List: head <-> node2(2:2) <-> node1(1:1) <-> tail. Map: {1: node1, 2: node2}.
3. get(1)
- Action: Key 1 is found in map (node1). Extract node1 from its position and move it right after head to mark it most recently used.
- Result: Returns 1.
- State: List: head <-> node1(1:1) <-> node2(2:2) <-> tail. Map: {1: node1, 2: node2}.
4. put(3, 3)
- Action: Key 3 is missing. Capacity is 2 (at limit). Evict the least recently used node, which is tail.prev (node2). Remove 2 from map and unlink node2. Then insert new node (3:3) at head.
- State: List: head <-> node3(3:3) <-> node1(1:1) <-> tail. Map: {1: node1, 3: node3}.
5. get(2)
- Action: Key 2 is looked up in the map.
- Result: Returns -1 because 2 was evicted during step 4.
6. put(4, 4)
- Action: Key 4 is missing. Capacity is at limit. Evict tail.prev (node1). Remove 1 from map and unlink node1. Insert new node (4:4) at head.
- State: List: head <-> node4(4:4) <-> node3(3:3) <-> tail. Map: {3: node3, 4: node4}.
7. get(1)
- Action: Key 1 is looked up.
- Result: Returns -1 (evicted in step 6).
8. get(3)
- Action: Key 3 is found (node3). Move node3 to head.
- Result: Returns 3.
- State: List: head <-> node3(3:3) <-> node4(4:4) <-> tail. Map: {3: node3, 4: node4}.
9. get(4)
- Action: Key 4 is found (node4). Move node4 to head.
- Result: Returns 4.
- State: List: head <-> node4(4:4) <-> node3(3:3) <-> tail. Map: {3: node3, 4: node4}.
python
# Complete the final trace verification for capacity 2
# Given cache after the operations above:
# List: head <-> node4(4:4) <-> node3(3:3) <-> tail
# Write a quick check to confirm cache.get(3) returns 3 and updates recency.
Phase 4: Executing put(3, 3) & Eviction (Capacity = 2) Capacity is full (2 items). Key 3 is missing. Evict tail.prev (node2), then insert node3 after head. Hash Map State Key 1 node1 (1:1) Key 2 node2 (2:2) - EVICT Key 3 node3 (3:3) - NEW Remove Key 2 from Map Map gets 3 -> node3 Doubly Linked List State (Head to Tail) HEAD dummy node3 key: 3 val: 3 node1 key: 1 val: 1 TAIL Evicted: tail.prev (node2) Unlinked from list & removed List State: head <-> node3(3:3) <-> node1(1:1) <-> tail
Tracing the Capacity 2 Sequence Step by Step diagram
Practice

Predicting the Final State for a Modified Capacity 3 Sequence

Phase 5: Practice

Now that you have traced the standard capacity 2 sequence where put(4,4) evicted key 2, let us test your mental model by modifying the parameters slightly. Suppose we initialize our LRUCache with a capacity of 3 instead of 2, and run the exact same operation stream: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4).
With a capacity of 3, the hash map can hold all three keys 1, 2, and 3 simultaneously without any evictions occurring during the first four operations. Your task is to trace the doubly linked list and hash map state immediately after put(3,3) executes, and then predict the return value of get(2) before put(4,4) is called.
python
class LRUCachePractice:
    # Given: capacity = 3
    # Operations: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4)
    # Question: What is the exact sequence of keys in the doubly linked list 
    # from head to tail immediately AFTER put(3,3) completes?
    pass
Edge cases

Edge Cases and Failure Modes in LRU Caches

Phase 6: Edge Cases

Even when our core put and get operations seem fully operational for our locked sequence Capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4), subtle corner cases can quietly corrupt the doubly linked list pointers or hash map references. Let us examine what happens when our assumptions break down under extreme inputs or duplicate keys.
First, consider the boundary case of a capacity 1 cache. If we instantiate LRUCache(1) and execute put(1,1) followed immediately by put(2,2), the cache size restriction (1) triggers eviction on the second insertion. Our head points to node 2, whose prev points to dummy tail and whose next points to dummy head, while node 1 is completely unlinked and garbage collected. If we then call get(1), it returns -1 because node 1 no longer exists in either the hash map or the list.
python
cache = LRUCache(1)
cache.put(1, 1)
cache.put(2, 2)  # Evicts key 1 immediately
print(cache.get(1))  # Returns -1
Second, consider duplicate key updates. When our locked example performs put(1,1) and later updates key 1 with a new value via put(1, 99), two things must happen: the value stored in the node must change from 1 to 99, and the node must be promoted to the head of the doubly linked list. Failing to promote the node on a duplicate key update treats a refreshed key as old, leading to premature eviction.
Third, consider a cache miss on get. When our sequence calls get(2) after key 2 was already evicted by put(4,4), our hash map lookup returns None or raises a key error. If our implementation attempts to call moveToHead(node) on a missing key, it will dereference a null pointer and crash the application.
python
def test_edge_cases():
    # Test capacity 1 eviction behavior
    cache = LRUCache(1)
    cache.put(1, 10)
    cache.put(2, 20)
    assert cache.get(1) == -1
    assert cache.get(2) == 20
    
    # Test duplicate key update and recency promotion
    cache2 = LRUCache(2)
    cache2.put(1, 1)
    cache2.put(2, 2)
    cache2.put(1, 10) # Updates key 1 and makes it most recent
    cache2.put(3, 3) # Should evict key 2, NOT key 1
    assert cache2.get(2) == -1
    assert cache2.get(1) == 10
    print("Edge case tests passed!")
Apply

Transferring the Dual-Data-Structure Pattern to LFU or Time-Window Caching

Phase 7: Transfer

We started our journey with a strict memory limit of capacity 2, tracing operations like put(1,1), put(2,2), and the eviction of key 2 when put(3,3) arrived. By combining a hash map with a doubly linked list, we achieved true time complexity for both lookups and recency reorderings, outperforming naive arrays or standard dictionaries.
Now we take this exact dual-data-structure pattern and ask how it transfers to a neighboring systems problem: Least Frequently Used (LFU) caching, or adding a TTL (Time-To-Live) expiration window. In an LFU cache, eviction depends on access frequency rather than recency. To maintain performance, we cannot simply scan counts; instead, we maintain a hash map of frequencies, where each frequency bucket itself points to a doubly linked list of items.
Whenever you encounter a problem requiring both rapid random access by key and rapid structural re-ordering based on dynamic metadata, the hash-map-plus-linked-list archetype is your primary architectural tool. Whether tracking recency, frequency, or expiration tiers, the pointer-manipulation invariants established in our capacity 2 walkthrough remain identical.
Consider how you would adapt the LRUCache class we built for capacity 2 if operations required evicting the item with the oldest timestamp instead of the least recently used access order.

FAQ

What happens during the capacity 2 sequence when put(3,3) is executed?
With capacity 2 and keys {1, 2} present, put(3,3) exceeds capacity. The least recently used key (2) is evicted, 2 is removed from the hash map and list, and 3 is inserted as the most recently used element.
Why do we need both a hash map and a doubly linked list?
The hash map provides O(1) random access to node references, while the doubly linked list maintains O(1) ordering updates (insertion and deletion) for recency tracking.
What are the time complexities of get and put operations in an LRU cache?
Both get and put operations run in strict O(1) time complexity by combining hash table lookups with constant-time pointer adjustments in the linked list.
What is the primary pitfall when implementing a doubly linked list from scratch for an LRU cache?
Forgetting to update tail and head pointers correctly during node removal or re-insertion can lead to broken chain references and null pointer exceptions.

Keep learning