LRU Cache - HashMap + Doubly Linked List Complete Guide

The LRU (Least Recently Used) Cache is one of the most frequently asked interview questions at top tech companies. It tests your understanding of both data structure design and real-world system components.

Why Interviewers Love This Problem

1. Tests data structure design - You must combine multiple data structures to achieve O(1) operations
2. Real-world relevance - LRU caches are used everywhere: browsers, databases, CDNs, operating systems
3. Forces trade-off thinking - Why not just use a HashMap? Why do we need a linked list?
4. Follow-up questions - Thread safety, distributed caches, TTL expiration, etc.

Core Intuition: HashMap + Doubly Linked List

The challenge is achieving O(1) time for both get and put operations while also tracking the order of access.

┌─────────────────────────────────────────────────────────────┐
│                        HashMap                              │
│    key → Node pointer (for O(1) lookup)                     │
│                                                             │
│    ┌───┐  ┌───┐  ┌───┐  ┌───┐                               │
│    │ 1 │  │ 2 │  │ 3 │  │ 4 │                               │
│    └─┬─┘  └─┬─┘  └─┬─┘  └─┬─┘                               │
│      │      │      │      │                                 │
│      ▼      ▼      ▼      ▼                                 │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │              Doubly Linked List                         │ │
│ │  HEAD ⟷ [1:A] ⟷ [2:B] ⟷ [3:C] ⟷ [4:D] ⟷ TAIL           │ │
│ │   ↑                                  ↑                  │ │
│ │  MRU                                LRU                 │ │
│ │  (Most Recently Used)         (Least Recently Used)     │ │
│ └─────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────┘

Key insight:

• HashMap → O(1) lookup by key
• Doubly Linked List → O(1) removal and insertion (when we have the node pointer)

When we access an item, we move it to the front. When we need to evict, we remove from the back.

---

Interactive Visualizer

Watch how the LRU Cache handles a sequence of get and put operations. Notice how items move to the front when accessed:

Initializing...

---

Problem: LRU Cache (LC 146)

Problem: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) - Initialize with positive capacity
• int get(int key) - Return value if exists, else return -1
• void put(int key, int value) - Update or insert. If capacity exceeded, evict least recently used item.

Both operations must run in O(1) average time.

Algorithm Steps

1. Initialize: Create a HashMap and a doubly linked list with dummy head/tail nodes
2. get(key):
   • If key not in HashMap → return -1
   • Else → move node to front, return value
3. put(key, value):
   • If key exists → update value, move to front
   • If key doesn’t exist:
     • If at capacity → remove LRU (tail.prev), delete from HashMap
     • Create new node → insert at front, add to HashMap

---

Code Template: HashMap + Doubly Linked List

JavaPythonJavaScript

Loading...

---

Alternative: Using Built-in Ordered Collections

Most languages have ordered data structures that can simplify the implementation:

JavaPythonJavaScript

Loading...

⚠️ Interview Warning: Many interviewers expect you to implement from scratch using HashMap + Doubly Linked List, not built-in solutions. Always ask!

---

Worked Example

Let’s trace through: LRUCache(2), then put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)

Step 1: LRUCache(2)
Cache: Empty  |  HashMap: {}

Step 2: put(1, 1)
Cache: [1:1]  |  HashMap: {1→node}
        ↑
       MRU

Step 3: put(2, 2)
Cache: [2:2] ⟷ [1:1]  |  HashMap: {1→node, 2→node}
        ↑        ↑
       MRU      LRU

Step 4: get(1) → returns 1
Cache: [1:1] ⟷ [2:2]  |  Move 1 to front!
        ↑        ↑
       MRU      LRU

Step 5: put(3, 3) → Evict LRU (key 2)!
Cache: [3:3] ⟷ [1:1]  |  HashMap: {1→node, 3→node}
        ↑        ↑
       MRU      LRU       ❌ key 2 evicted

Step 6: get(2) → returns -1 (was evicted!)

Step 7: put(4, 4) → Evict LRU (key 1)!
Cache: [4:4] ⟷ [3:3]  |  HashMap: {3→node, 4→node}
                          ❌ key 1 evicted

Step 8: get(1) → returns -1 (was evicted!)

Step 9: get(3) → returns 3
Cache: [3:3] ⟷ [4:4]  |  Move 3 to front!

Step 10: get(4) → returns 4
Cache: [4:4] ⟷ [3:3]  |  Move 4 to front!

---

Time & Space Complexity

Operation	Time	Space
get(key)	O(1)	-
put(key, value)	O(1)	-
Overall Space	-	O(capacity)

Why O(1)?

• HashMap provides O(1) lookup
• Doubly linked list provides O(1) insertion/removal when we have the node pointer
• We always have the node pointer from the HashMap!

---

Critical Points & Common Mistakes

1. Dummy Head and Tail Nodes

Why use dummy nodes?

Without dummy nodes:
- Must check if node is head before removal
- Must check if node is tail before removal  
- Edge cases everywhere!

With dummy nodes:
- Uniform removal/insertion logic
- No edge cases!

Common Mistake: Forgetting to initialize head.next = tail and tail.prev = head.

2. Store Key in Node

Why store key in the node?

When evicting the LRU node, we need to remove it from the HashMap too. But we only have the node reference! Without storing the key in the node, we can’t delete from the HashMap.

// WRONG - can't delete from HashMap
Node lru = tail.prev;
remove(lru);
// map.remove(???) - We don't know the key!

// CORRECT - key stored in node
Node lru = tail.prev;
remove(lru);
map.remove(lru.key); // ✓

3. Update vs Insert Order

Common Mistake: Forgetting to move the node to front when updating an existing key.

// WRONG
public void put(int key, int value) {
    if (map.containsKey(key)) {
        map.get(key).val = value; // Only updates value, doesn't move!
    }
    // ...
}

// CORRECT
public void put(int key, int value) {
    if (map.containsKey(key)) {
        Node node = map.get(key);
        node.val = value;
        remove(node);       // Remove from current position
        insertFront(node);  // Move to front!
    }
    // ...
}

4. Eviction Check Timing

Common Mistake: Evicting before checking if key already exists.

// WRONG - might evict even when just updating
public void put(int key, int value) {
    if (map.size() == capacity) {
        evict(); // Wrong! Key might already exist
    }
    // ...
}

// CORRECT - check existing first
public void put(int key, int value) {
    if (map.containsKey(key)) {
        // Update existing - no eviction needed
    } else {
        if (map.size() == capacity) {
            evict(); // Only evict when adding new key
        }
    }
}

5. Pointer Update Order

Common Mistake: Updating pointers in wrong order, breaking the list.

// WRONG - breaks the list!
private void insertFront(Node node) {
    head.next = node;        // Lost reference to old head.next!
    node.prev = head;
    node.next = head.next;   // This is now node itself!
    head.next.prev = node;
}

// CORRECT - preserve references first
private void insertFront(Node node) {
    node.next = head.next;   // 1. Point to old first node
    node.prev = head;        // 2. Point back to head
    head.next.prev = node;   // 3. Old first points back to new node
    head.next = node;        // 4. Head points to new node
}

---

Interview Follow-up Questions

1. Thread Safety

Q: How would you make this thread-safe?

A:

• Simple approach: Use synchronized or ReentrantLock on all methods
• Better approach: Read-write lock (allow concurrent reads)
• Best approach: Concurrent data structures + careful locking

class ThreadSafeLRUCache {
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    
    public int get(int key) {
        lock.writeLock().lock(); // Need write lock because we modify order
        try {
            // ... get logic
        } finally {
            lock.writeLock().unlock();
        }
    }
}

2. TTL (Time-To-Live) Expiration

Q: How would you add expiration for entries?

A: Store timestamp in each node. Check on access and lazy evict, or use a background thread.

3. Distributed LRU Cache

Q: How would you scale this to multiple servers?

A:

• Consistent hashing to distribute keys
• Each server runs its own LRU cache
• Consider cache invalidation across nodes

---

When NOT to Use LRU

Scenario	Better Alternative
Frequency matters more than recency	LFU (Least Frequently Used)
Need predictable eviction order	FIFO
Random access patterns	ARC (Adaptive Replacement Cache)
Very large cache	Approximate LRU (sampling)

---

Related Problems

Problem	Description	Link
LFU Cache	Evict least frequently used	LC 460 🔒 - Tutorial
Design Twitter	Uses caching concepts	LC 355
Time Based Key-Value Store	Key-value with timestamps	LC 981
All O’one Data Structure	Track min/max keys	LC 432

---

Summary

Key Takeaways

1. Data Structure Combination: HashMap + Doubly Linked List = O(1) for everything
2. Dummy Nodes: Simplify edge cases significantly
3. Store Key in Node: Essential for eviction cleanup
4. Move to Front: Any access makes item most recently used
5. Evict from Back: Tail.prev is always the LRU item

Pattern to Memorize

LRU Cache = HashMap<Key, Node> + DoublyLinkedList<Node>

get(key):
  1. HashMap lookup → O(1)
  2. Move node to front → O(1)
  
put(key, value):
  1. If exists: update + move to front
  2. If new: 
     - If full: evict tail.prev
     - Insert at front

This pattern is foundational for many system design and data structure problems!