The LRU Cache Puzzle: Discovering Why We Need HashMap + LinkedList

A conversation about solving the LRU Cache problem that reveals one of the most elegant hybrid data structure designs—and why sometimes the "crazy" idea of combining two data structures is actually brilliant.

---

The Problem

Teacher: Today we're tackling one of the most famous system design problems in interviews. Let me show you the LRU Cache problem:

Problem: Design and implement an LRU (Least Recently Used) cache

Implement the LRUCache class:

• LRUCache(int capacity) - Initialize the cache with positive size capacity
• int get(int key) - Return the value of the key if it exists, otherwise return -1
• void put(int key, int value) - Update the value if key exists, otherwise add the key-value pair. When the cache reaches capacity, it should evict the least recently used item before inserting a new item.

Example:

LRUCache cache = new LRUCache(2); // capacity = 2

cache.put(1, 100);   // cache: {1=100}
cache.put(2, 200);   // cache: {1=100, 2=200}
cache.get(1);        // returns 100, cache: {2=200, 1=100}
                     // 1 is now most recently used
cache.put(3, 300);   // evicts key 2, cache: {1=100, 3=300}
cache.get(2);        // returns -1 (not found)
cache.put(4, 400);   // evicts key 1, cache: {3=300, 4=400}

---

Understanding "Least Recently Used"

Teacher: Before we think about data structures, let's understand what "least recently used" means. Look at the example carefully.

Question 1: After put(3, 300) causes key 1 to be evicted... wait, no! It evicts key 2, not key 1. Why was key 2 chosen for eviction?

Think about the timeline of operations and when each key was last "touched"...

Me: Hmm... let me trace through:

1. put(1, 100) - key 1 was used
2. put(2, 200) - key 2 was used
3. get(1) - key 1 was used again!

So at this point, key 2 was used before key 1. When we add key 3, we evict the least recently used, which is key 2!

Teacher: Perfect! 🎯 So "recently used" means the last time the key was accessed, either through get() OR put(). Every access updates the "recency."

---

The Two-Part Challenge

Teacher: Now let's think about what operations we need to support:

1. get(key) - Fast access to values
2. put(key, value) - Fast insertion
3. Track usage order - Know which item was least recently used
4. Evict LRU - Remove the least recently used item when full

Question 2: If you were designing a cache, what time complexity would make it useful? If get() took O(n) time, would that be a good cache?

Me: No way! A cache should be fast. I'd want O(1) for both get() and put()!

Teacher: Exactly! So here's the challenge:

The Core Challenge

You need to:

1. ✅ Access items in O(1) time (get operation)
2. ✅ Keep track of usage order
3. ✅ Remove the least recently used item in O(1) time

Can a single data structure give you ALL of this?

---

My Initial Intuition: LinkedList

Me: I don't know exactly, but maybe we can do something useful using a linked list with a head pointer and tail pointer?

We can:

• Directly add new items to the tail (most recently used)
• Use head pointer to remove from the front (least recently used)

But I can't think of how to mark an entity as "used" and update its position...

Wait! When we call get(key), we should move that node to the tail, right? To mark it as most recently used?

Teacher: Excellent intuition! You're thinking in the right direction!

But here's the challenge...

---

Question 1: The Search Problem

Teacher: If you have a linked list and you need to find key "4" to move it to the tail, how would you find it?

[Node1] → [Node2] → [Node4] → [Node3] → null
  head                           tail

To execute get(4), you need to:

1. Find where Node4 is located
2. Move it to the tail position

What's the time complexity of searching through a linked list?

Me: Oh no... that's O(n)! I'd have to traverse from the head until I find key 4.

And even if I found the node, to remove it from the middle, I need to know its previous node to update the next pointer...

Teacher: Exactly! You've identified the core problem:

Finding a node in linked list: O(n) ❌
But we need: O(1) ✓

So linked list alone won't work for fast access!

---

The "Crazy" Idea

Teacher: You mentioned something interesting earlier. What data structure gives you O(1) access by key?

Me: The only data structure I know with O(1) lookup is HashMap! But... I don't think we're gonna use it, are we?

I mean, what's the point of using a linked list if we need a HashMap too?

Teacher: Ah! But why not? Let me challenge your thinking:

Question: Can a HashMap alone solve this problem?

• Can HashMap maintain the order of "recently used"?
• How would you know which element to evict when capacity is full?

Me: Hmm... no, HashMap doesn't maintain any order. It just stores key-value pairs. I'd have no idea which item is the "least recently used."

Teacher: And can a linked list alone give you O(1) access?

Me: No... we already established that's O(n) for searching.

---

💡 The Breakthrough Moment

Teacher: What if I told you that using BOTH HashMap AND LinkedList together is not crazy but elegant?

Think about this setup:

• HashMap stores: key -> reference to the node in linked list
• LinkedList maintains the order (head = LRU, tail = MRU)

Question: If the HashMap stores direct references/pointers to nodes in the linked list, what happens when you call get(4)?

Me: Wait... let me think:

1. HashMap lookup: O(1) - gives me direct reference to Node4
2. Now I have the node directly - no traversal needed!
3. I can manipulate it in the linked list...

Teacher: EXACTLY! 🎯

Me: I am speechless. What an amazing idea! Use the HashMap for direct address to nodes. So I won't have to traverse the linked list each time I need to find something!

This is brilliant! Each structure does what it's best at:

• HashMap: Instant access to any node
• LinkedList: Maintains usage order

---

But Wait... The Removal Problem

Me: Okay, I understand the HashMap gives me the node reference in O(1). But here's what I'm stuck on:

Taking a node from its current position and putting it at the tail will require O(n), right?

For example, to remove Node B from the middle:

[A] → [B] → [C] → [D]

I need to:

1. Find Node A (the previous node)
2. Update A's next pointer to skip B: A.next = C

But to find Node A, don't I need to traverse from the head? That's O(n)!

Teacher: Brilliant question! This is where the magic happens...

---

The Doubly Linked List Revelation

Teacher: You mentioned: "how about we store next AND previous values inside each node?"

YES! This is called a doubly linked list!

Let me show you:

[A] ←→ [B] ←→ [C] ←→ [D]

Question: If HashMap gives you a direct reference to Node B, and Node B knows:

• B.prev = Node A
• B.next = Node C

To remove B from its current position:

• Can you access Node A directly? (Yes! B.prev)
• Can you access Node C directly? (Yes! B.next)

Me: Oh! So to extract Node B, I just need to:

A.next = C  // Make A point to C
C.prev = A  // Make C point back to A

And I can access both A and C through B's pointers!

Teacher: Exactly! How many nodes did you have to traverse to do this?

Me: Zero! I had direct access to all three nodes involved!

This is O(1)! 🤯

---

Moving to Tail: The Complete Picture

Teacher: Now let's say you maintain a tail pointer that always points to the most recently used node. To add the extracted Node B after the current tail:

Before:
[A] ←→ [C] ←→ [D]
              tail

Want:
[A] ←→ [C] ←→ [D] ←→ [B]
                    tail

You have:

1. Direct reference to Node B (from HashMap)
2. Direct reference to current tail (from your cache class variable)

What pointer updates would make B the new tail?

Me: Let me try:

tail.next = B      // D points to B
B.prev = tail      // B points back to D
B.next = null      // B is the end
tail = B           // Update tail reference

Teacher: Perfect! And notice - all O(1) operations! No traversal!

---

The Complete get() Operation

Let me trace through get(4) with our hybrid structure:

Initial State:

HashMap: {1 -> Node1, 4 -> Node4, 2 -> Node2}

LinkedList:
[Node1] ←→ [Node4] ←→ [Node2]
  head                   tail

After get(4):

Step 1: HashMap lookup - O(1)

Node node = map.get(4);  // Direct reference to Node4

Step 2: Extract Node4 from current position - O(1)

node.prev.next = node.next;  // Node1.next = Node2
node.next.prev = node.prev;  // Node2.prev = Node1

Step 3: Add Node4 to tail - O(1)

tail.next = node;      // Node2.next = Node4
node.prev = tail;      // Node4.prev = Node2
node.next = null;      // Node4.next = null
tail = node;           // tail = Node4

Final State:

LinkedList:
[Node1] ←→ [Node2] ←→ [Node4]
  head                   tail

Total Time Complexity: O(1)! ✓

---

What HashMap Actually Stores

Me: Wait, so what exactly do we store in the HashMap? All nodes and their prev/next addresses?

Teacher: Great question! The HashMap is actually very simple:

HashMap<Integer, Node> map = new HashMap<>();

Key: The cache key (e.g., 1, 2, 3, 4) Value: Reference/pointer to the actual Node in the linked list

The Node itself contains:

class Node {
    int key;      // Why store key in node? We'll see!
    int value;    // The actual cached value
    Node prev;    // Previous node in list
    Node next;    // Next node in list
}

Question for you: Why do we store the key in BOTH the HashMap AND the node?

Me: Hmm... maybe for eviction? When we remove the LRU node from the head, we need to remove it from the HashMap too, and we need its key to do that!

Teacher: Exactly! When you evict:

Node toRemove = head;
map.remove(toRemove.key);  // Need the key to remove from map!

---

The Complete put() Operation

Let's trace through put(3, 300) when cache is full:

Initial State (capacity = 2):

HashMap: {1 -> Node1, 2 -> Node2}

LinkedList:
[Node2] ←→ [Node1]
  head       tail

Step 1: Check if cache is full

if (map.size() >= capacity) {
    // Evict LRU (head node)
    Node toRemove = head;
    map.remove(toRemove.key);  // Remove from HashMap
    head = head.next;          // Move head forward
    if (head != null) {
        head.prev = null;      // New head has no previous
    }
}

Step 2: Create and add new node

Node newNode = new Node(3, 300);
map.put(3, newNode);  // Add to HashMap
addToTail(newNode);   // Add to tail of list

Final State:

HashMap: {1 -> Node1, 3 -> Node3}

LinkedList:
[Node1] ←→ [Node3]
  head       tail

---

The Edge Cases That Matter

Me: I understand the core logic, but what about edge cases? Like what if the node is already the tail?

Teacher: Excellent! These edge cases are crucial. Let's explore them:

Edge Case 1: get() on a node that's already the tail

The Problem:

[Node1] ←→ [Node2] ←→ [Node4]
  head                   tail

If you call get(4) and blindly execute:

node.next.prev = node.prev;  // NULL.prev = Node2 💥 NullPointerException!

The Solution:

if (node == tail) {
    return node.value;  // Already most recent, nothing to move!
}

Edge Case 2: put() when cache is empty

The Problem: No head, no tail. You call put(1, 100).

The Solution:

if (head == null) {  // Empty cache
    newNode.prev = null;
    newNode.next = null;
    head = newNode;
    tail = newNode;  // First node is BOTH head and tail!
}

Edge Case 3: put() when capacity is 1

The Scenario: Capacity = 1, cache has [Node1], you call put(2, 200)

if (capacity == 1 && map.size() == 1) {
    map.remove(head.key);
    head = newNode;
    tail = newNode;
    newNode.prev = null;
    newNode.next = null;
}

Edge Case 4: Removing head when it's the only node

if (head == tail) {  // Only one node
    map.remove(head.key);
    head = null;
    tail = null;
} else {
    Node toRemove = head;
    head = head.next;
    head.prev = null;
    map.remove(toRemove.key);
}

Edge Case 5: put() with existing key

If put(2, 300) is called but key 2 already exists:

• Update the value: node.value = 300
• Move to tail (most recent) - just like get()
• DON'T increase size (it's an update, not insertion)

---

The Basic Implementation

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer, Node> map;
    private int capacity;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = null;
        this.tail = null;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        Node node = map.get(key);

        // If already tail (most recent), just return
        if (node == tail) {
            return node.value;
        }

        // Remove from current position
        removeNode(node);

        // Add to tail (most recent)
        addToTail(node);

        return node.value;
    }

    public void put(int key, int value) {
        // Key exists - update value and move to tail
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;

            if (node != tail) {
                removeNode(node);
                addToTail(node);
            }
            return;
        }

        // Evict LRU if at capacity
        if (map.size() >= capacity) {
            map.remove(head.key);
            removeNode(head);
        }

        // Add new node
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToTail(newNode);
    }

    private void removeNode(Node node) {
        if (node == head && node == tail) {
            // Only node
            head = null;
            tail = null;
        } else if (node == head) {
            // Head node
            head = head.next;
            head.prev = null;
        } else if (node == tail) {
            // Tail node
            tail = tail.prev;
            tail.next = null;
        } else {
            // Middle node
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    private void addToTail(Node node) {
        node.prev = null;
        node.next = null;

        if (tail == null) {
            // Empty cache
            head = node;
            tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }
}

Complexity:

• Time: O(1) for both get() and put()
• Space: O(capacity) for HashMap and LinkedList

---

The Dummy Node Trick (Advanced)

Teacher: There's an even more elegant approach that eliminates most edge cases!

Me: I didn't understand the dummy node logic you mentioned. How do they help exactly?

Teacher: Let me show you with visuals!

Without Dummy Nodes

Empty cache:

head = null
tail = null

One node:

[Node1]
head = Node1, tail = Node1
Node1.prev = null, Node1.next = null

Multiple nodes:

[Node1] ←→ [Node2] ←→ [Node3]
head = Node1, tail = Node3

With Dummy Nodes

Empty cache:

[DummyHead] ←→ [DummyTail]

One node:

[DummyHead] ←→ [Node1] ←→ [DummyTail]

Multiple nodes:

[DummyHead] ←→ [Node1] ←→ [Node2] ←→ [Node3] ←→ [DummyTail]

Why This Eliminates Edge Cases

Example: Removing a Node

WITHOUT dummy nodes - need null checks:

void removeNode(Node node) {
    if (node.prev != null) {
        node.prev.next = node.next;
    } else {
        head = node.next;  // Special case: removing head
    }

    if (node.next != null) {
        node.next.prev = node.prev;
    } else {
        tail = node.prev;  // Special case: removing tail
    }
}

WITH dummy nodes - no null checks!

void removeNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    // That's it! No null checks needed!
}

Question: Why no null checks?

Answer: Even if you're removing the "first real node", its prev is DummyHead, not null!

Adding to Tail

WITHOUT dummy nodes:

void addToTail(Node node) {
    if (tail == null) {
        head = node;
        tail = node;
        node.prev = null;
        node.next = null;
    } else {
        tail.next = node;
        node.prev = tail;
        node.next = null;
        tail = node;
    }
}

WITH dummy nodes:

void addToTail(Node node) {
    node.prev = dummyTail.prev;     // Always valid!
    node.next = dummyTail;           // Always valid!
    dummyTail.prev.next = node;      // Always valid!
    dummyTail.prev = node;           // Always valid!
}

The Key Insight

With dummy nodes:

• Every real node ALWAYS has a non-null prev (at minimum, DummyHead)
• Every real node ALWAYS has a non-null next (at minimum, DummyTail)
• Least recent = dummyHead.next (might be DummyTail if empty)
• Most recent = dummyTail.prev (might be DummyHead if empty)

Checking if Cache is Empty:

• Without dummy nodes: if (head == null)
• With dummy nodes: if (dummyHead.next == dummyTail)

---

The Elegant Dummy Node Implementation

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer, Node> map;
    private int capacity;
    private Node dummyHead;
    private Node dummyTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();

        // Initialize dummy nodes
        this.dummyHead = new Node(0, 0);
        this.dummyTail = new Node(0, 0);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        Node node = map.get(key);

        // Move to most recent (tail)
        removeNode(node);
        addToTail(node);

        return node.value;
    }

    public void put(int key, int value) {
        // Update existing key
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            removeNode(node);
            addToTail(node);
            return;
        }

        // Evict LRU if at capacity
        if (map.size() >= capacity) {
            Node lru = dummyHead.next;
            map.remove(lru.key);
            removeNode(lru);
        }

        // Add new node
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToTail(newNode);
    }

    private void removeNode(Node node) {
        // No null checks needed!
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToTail(Node node) {
        // No null checks needed!
        node.prev = dummyTail.prev;
        node.next = dummyTail;
        dummyTail.prev.next = node;
        dummyTail.prev = node;
    }
}

Notice: The core logic is much cleaner with no edge case handling!

---

Testing Our Implementation

public class TestLRUCache {
    public static void main(String[] args) {
        // Test case 1: Basic operations
        LRUCache cache = new LRUCache(2);

        cache.put(1, 100);
        cache.put(2, 200);
        System.out.println(cache.get(1));  // Expected: 100

        cache.put(3, 300);  // Evicts key 2
        System.out.println(cache.get(2));  // Expected: -1

        cache.put(4, 400);  // Evicts key 1
        System.out.println(cache.get(1));  // Expected: -1
        System.out.println(cache.get(3));  // Expected: 300
        System.out.println(cache.get(4));  // Expected: 400

        // Test case 2: Capacity 1
        LRUCache cache2 = new LRUCache(1);
        cache2.put(1, 1);
        cache2.put(2, 2);  // Evicts 1
        System.out.println(cache2.get(1));  // Expected: -1
        System.out.println(cache2.get(2));  // Expected: 2

        // Test case 3: Update existing key
        LRUCache cache3 = new LRUCache(2);
        cache3.put(1, 100);
        cache3.put(2, 200);
        cache3.put(1, 300);  // Update, not eviction
        System.out.println(cache3.get(1));  // Expected: 300
        System.out.println(cache3.get(2));  // Expected: 200
    }
}

---

Common Mistakes

❌ Mistake 1: Using Singly Linked List

// Wrong: Can't remove from middle in O(1)
class Node {
    int key, value;
    Node next;  // Missing prev!
}

You need prev pointer to remove a node without traversal!

❌ Mistake 2: Not Storing Key in Node

// Wrong: Can't remove from HashMap during eviction
class Node {
    int value;  // Missing key!
    Node prev, next;
}

// When evicting:
map.remove(???);  // What key to remove?

❌ Mistake 3: Forgetting to Update on get()

// Wrong: get() should mark item as recently used!
public int get(int key) {
    if (!map.containsKey(key)) return -1;
    return map.get(key).value;  // Forgot to move to tail!
}

❌ Mistake 4: Not Handling Existing Keys in put()

// Wrong: Existing keys should update, not duplicate!
public void put(int key, int value) {
    // Missing: if (map.containsKey(key)) { update and return; }
    Node newNode = new Node(key, value);
    map.put(key, newNode);  // Creates duplicate!
}

❌ Mistake 5: Wrong Order in get()

// Wrong order: Don't update map during get()!
public int get(int key) {
    Node node = map.get(key);
    removeNode(node);
    addToTail(node);
    map.put(key, node);  // Unnecessary! Reference didn't change
    return node.value;
}

---

Visual Trace: Complete Example

Let's trace the full example with visualizations:

LRUCache cache = new LRUCache(2);

State:

HashMap: {}
List: [DummyHead] ←→ [DummyTail]

---

cache.put(1, 100);

State:

HashMap: {1 -> Node1}
List: [DummyHead] ←→ [Node1(1,100)] ←→ [DummyTail]
                        LRU             MRU

---

cache.put(2, 200);

State:

HashMap: {1 -> Node1, 2 -> Node2}
List: [DummyHead] ←→ [Node1(1,100)] ←→ [Node2(2,200)] ←→ [DummyTail]
                        LRU                  MRU

---

cache.get(1);  // Returns 100

Node1 moves to tail (most recent):

State:

HashMap: {1 -> Node1, 2 -> Node2}
List: [DummyHead] ←→ [Node2(2,200)] ←→ [Node1(1,100)] ←→ [DummyTail]
                        LRU                  MRU

---

cache.put(3, 300);  // Evicts key 2

Evict Node2 (LRU), add Node3:

State:

HashMap: {1 -> Node1, 3 -> Node3}
List: [DummyHead] ←→ [Node1(1,100)] ←→ [Node3(3,300)] ←→ [DummyTail]
                        LRU                  MRU

---

cache.get(2);  // Returns -1 (not found)

State: (unchanged)

---

cache.put(4, 400);  // Evicts key 1

Evict Node1 (LRU), add Node4:

State:

HashMap: {3 -> Node3, 4 -> Node4}
List: [DummyHead] ←→ [Node3(3,300)] ←→ [Node4(4,400)] ←→ [DummyTail]
                        LRU                  MRU

Perfect! ✓

---

The Broader Pattern: OrderedDict in Python

Interestingly, Python has a built-in data structure that combines HashMap + LinkedList:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # Mark as most recent
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # Remove LRU (first item)

This is basically the same hybrid structure we designed!

---

Key Takeaways

What We Learned

1. Hybrid Data Structures Can Be Elegant:

   • HashMap alone: Fast access, but no order
   • LinkedList alone: Order, but slow access
   • Both together: Fast access AND order tracking!

2. Doubly Linked List Enables O(1) Removal:

   node.prev.next = node.next
   node.next.prev = node.prev

   Access neighbors through the node itself - no traversal!

3. HashMap Stores Node References:

   HashMap<Integer, Node> map
   // Key: cache key
   // Value: reference to node in linked list

4. Why Store Key in Node:

   • Needed to remove from HashMap during eviction

   map.remove(nodeToEvict.key);

5. Dummy Nodes Simplify Edge Cases:

   • No null checks needed
   • Cleaner code, fewer bugs
   • Empty cache: dummyHead ←→ dummyTail

6. Access = Update Recency:

   • Both get() and put() mark items as recently used
   • Move accessed node to tail (most recent position)

7. Time Complexity: O(1) for Everything:

   • get(): O(1) HashMap lookup + O(1) move to tail
   • put(): O(1) HashMap insert + O(1) add to tail
   • Eviction: O(1) remove from head

8. Space Complexity: O(capacity)

   • HashMap stores up to capacity entries
   • LinkedList stores up to capacity nodes

---

Similar Problems

Try these to solidify your understanding:

1. LFU Cache - Least Frequently Used (LeetCode 460)
2. Design HashMap - Build a HashMap from scratch (LeetCode 706)
3. Design LinkedHashMap - Combined structure (similar to our LRU)
4. Time Based Key-Value Store - Versioned cache (LeetCode 981)

Tags: #algorithms #data-structures #hashmap #linked-list #cache #system-design #learning-journey #interview-prep

---

The Final Wisdom

Teacher: So what did we discover today?

Me: That sometimes the "crazy" idea of combining two data structures is actually the most elegant solution!

We needed:

• Fast access → HashMap provides it
• Order tracking → Doubly LinkedList provides it
• O(1) operations → The combination provides it!

Each structure handles what it's best at. The HashMap gives us instant access to any node, and the doubly linked list lets us manipulate order in constant time.

Teacher: Exactly! And this pattern appears in many real systems:

• Browser history
• Database query caches
• Operating system page replacement
• CDN caching layers

The LRU Cache is one of the most practical algorithm problems you'll encounter because it models real-world caching systems used everywhere!

---

This conversation happened during a real learning session. Sometimes the best solutions come from combining different tools, each doing what it does best—like a HashMap for speed and a LinkedList for order!