LRU Cache Explained: Brute Force to Optimal (HashMap + Doubly Linked List) | C++

1. Introduction

What is an LRU Cache?

LRU stands for Least Recently Used. An LRU Cache is a fixed-size data structure that stores a limited number of key-value pairs. When the cache is full and a new item needs to be inserted, it evicts (removes) the item that was used least recently — i.e., the item that hasn't been accessed for the longest time.

In simple words:

• The cache has a capacity (maximum number of items it can hold).
• Every time you access or insert an item, that item becomes the "most recently used."
• When the cache is full and a new item comes in, the "least recently used" item is thrown out to make space.

🌍 Where is LRU Cache Used in Real-World Systems?

LRU is not just a textbook exercise — it powers real systems you use every day:

📌 Note: This problem is popular precisely because it tests multiple skills at once — hash maps, linked lists, pointer manipulation, and time-complexity reasoning — all in one question.

2. Problem Statement

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

Implement the LRUCache class:

• LRUCache(int capacity) — Initialize the LRU 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 of the key if it exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Explaining the Cache Capacity

The capacity is the maximum number of key-value pairs the cache can hold at any time. Once this limit is reached, inserting a new key requires evicting an old one — specifically, the one that was least recently accessed.

Explaining get(key)

• If key exists in the cache → return its value and mark it as recently used.
• If key does not exist → return -1 (cache miss).

Explaining put(key, value)

• If key already exists → update its value and mark it as recently used.
• If key doesn't exist:
  • If the cache is not full, simply insert the new pair.
  • If the cache is full, evict the least recently used item first, then insert the new pair.

Eviction Policy

🧠 Key Rule: "Recently used" means recently accessed via get() OR recently inserted/updated via put(). Any touch to a key refreshes its recency.

The eviction always removes the item that has gone the longest without being touched.

3. Examples

Example 1

Input:
LRUCache lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
lru.get(1);       // returns 1
lru.put(3, 3);    // evicts key 2
lru.get(2);       // returns -1 (not found)
lru.put(4, 4);    // evicts key 1
lru.get(1);       // returns -1 (not found)
lru.get(3);       // returns 3
lru.get(4);       // returns 4

Explanation with cache state after every operation (Most Recently Used → Least Recently Used, left to right):

Example 2 (Capacity = 1)

LRUCache lru = new LRUCache(1);
lru.put(5, 100);   // cache: {5=100}
lru.get(5);        // returns 100
lru.put(6, 200);   // evicts 5, cache: {6=200}
lru.get(5);        // returns -1
lru.get(6);        // returns 200

With capacity 1, every new key evicts the previous one, since only one item can exist at a time.

4. Constraints

Typical constraints (as seen on LeetCode #146):

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 calls will be made to get and put.
• Both get and put must run in O(1) average time complexity.

⚠️ Important: The O(1) requirement is the whole point of this problem. Any solution that uses O(n) search or O(n) deletion will technically produce correct output but will fail on time limits for large inputs (up to 2×10⁵ operations).

5. Intuition

Before writing any code, let's build the right mental model.

🚫 Why Normal Arrays Are Inefficient

If we store (key, value) pairs in a plain array or vector:

• To find a key, we must scan the array → O(n) search.
• To track recency, we'd need to move accessed elements to the front or back → O(n) shifting.
• To delete the least recently used element (which could be anywhere), we'd need to shift all subsequent elements → O(n) deletion.

This clearly violates the O(1) requirement.

🔍 Why Searching Becomes Expensive

Without an index (like a hash map), locating a key means checking every element one by one. As the cache grows toward its capacity limit (up to 3000, and total operations up to 2×10⁵), linear search becomes a bottleneck.

✂️ Why Deletion From the Middle Is Costly

Even if we knew where an element was, removing it from the middle of an array requires shifting all elements after it to fill the gap — again O(n).

This is why arrays (and even singly linked lists, as we'll see) struggle here: deletion from an arbitrary position is expensive unless we use a structure that supports O(1) removal given a pointer to the node.

⚡ Why We Need Constant Time Operations

Since the problem explicitly demands O(1) average time for both get and put, we need:

1. O(1) lookup → solved by a HashMap.
2. O(1) insertion/deletion at arbitrary positions → solved by a Doubly Linked List.

Neither structure alone is sufficient — we need both, working together.

🗺️ How HashMap Helps

A HashMap<key, Node*> lets us jump directly to the node holding a given key in O(1) average time, instead of searching for it. This solves the "search" problem instantly.

But a HashMap alone can't tell us which key was least recently used — hash maps have no inherent ordering. That's where the linked list comes in.

🔗 Why a Doubly Linked List Is Required

We need a structure that maintains usage order: most recently used at one end, least recently used at the other. Whenever a key is accessed, we move its node to the "most recently used" end.

A Doubly Linked List (DLL) allows:

• O(1) removal of a node if we already have a pointer to it (because we can directly access both prev and next pointers).
• O(1) insertion at the front (most recently used position).
• O(1) access to the tail's neighbor (least recently used) for eviction.

❌ Why a Singly Linked List Is Insufficient

In a Singly Linked List, each node only knows its next node — not its previous one.

To remove a node from a singly linked list, you need the previous node's reference to skip over it (prev->next = node->next). Since we don't have a prev pointer, we'd have to traverse from the head to find it → O(n).

This defeats the purpose. Only a Doubly Linked List gives us O(1) deletion given just a pointer to the node itself, which is exactly what our HashMap provides us.

6. Brute Force Approach

Idea

Use a simple vector (or array) of (key, value) pairs. To track recency, whenever a key is accessed, remove it from its current position and push it to the front (or back) of the vector. Eviction removes the last element.

Step-by-Step Algorithm

1. Maintain a vector<pair<int,int>> cache and an integer capacity.
2. get(key):
   • Linearly scan the vector for key.
   • If found, remember its value, erase it from its current position, and re-insert it at the front.
   • If not found, return -1.
3. put(key, value):
   • Linearly scan for key.
   • If found, erase the old entry.
   • If the vector size equals capacity (and we're inserting a brand-new key), remove the last element (least recently used).
   • Insert (key, value) at the front.

Dry Run

C++ Implementation (Brute Force)

#include <bits/stdc++.h>
using namespace std;

class LRUCacheBrute {
private:
    int capacity;
    vector<pair<int,int>> cache; // front = most recently used

public:
    LRUCacheBrute(int cap) : capacity(cap) {}

    int get(int key) {
        for (int i = 0; i < (int)cache.size(); i++) {
            if (cache[i].first == key) {
                pair<int,int> entry = cache[i];
                cache.erase(cache.begin() + i);   // O(n) removal
                cache.insert(cache.begin(), entry); // O(n) insertion at front
                return entry.second;
            }
        }
        return -1;
    }

    void put(int key, int value) {
        for (int i = 0; i < (int)cache.size(); i++) {
            if (cache[i].first == key) {
                cache.erase(cache.begin() + i); // remove old entry
                break;
            }
        }
        if ((int)cache.size() == capacity) {
            cache.pop_back(); // evict least recently used
        }
        cache.insert(cache.begin(), {key, value});
    }
};

Time Complexity

• get() → O(n) (linear search + shifting)
• put() → O(n) (linear search + shifting + possible eviction)

Space Complexity

• O(capacity) for storing the pairs.

Drawbacks

• ❌ Violates the O(1) requirement completely.
• ❌ Every operation involves shifting elements — very slow for large inputs (up to 2×10⁵ operations).
• ❌ Would Time Limit Exceed (TLE) on platforms like LeetCode for large test cases.

7. Better Approach

Idea

Improve lookup speed using a HashMap for O(1) key lookup, but still use a singly linked list (or a list with only "next" pointers) to track order. This partially optimizes search but deletion is still slow because we can't jump backward.

Data Structures Used

• unordered_map<int, value> for value lookup.
• A singly linked list (or list<int> used naively) to track usage order, where we still need to search for a node's position to remove it.

Algorithm

1. Maintain unordered_map<int,int> valueMap for key -> value.
2. Maintain a singly linked list (or std::list<int>) storing keys in order of use (front = most recent).
3. get(key):
   • If key not in valueMap, return -1.
   • Otherwise, traverse the list to find the key's node, remove it, and reinsert at the front. (This traversal is the bottleneck.)
   • Return valueMap[key].
4. put(key, value):
   • If the key exists, update the value and move it to front (again requires traversal in a singly linked structure to find the prev node).
   • If the key is new and cache is full, remove the tail key from both the list and hashmap.
   • Insert new key at front, update hashmap.

Dry Run

capacity = 2

Note: We are not providing a full implementation of the Better Approach because it is not commonly implemented in interviews. Its purpose is to illustrate why using a HashMap + Linked List alone is still insufficient. Since the HashMap stores only the values and not the node locations, we must traverse the linked list to locate a key before moving it to the front, resulting in O(n) time for get() and updating an existing key in put(). Understanding this limitation is more important than memorizing the code, as interviewers typically expect the optimal O(1) solution using a HashMap that stores node pointers along with a Doubly Linked List.

int get(int key) {
    if (valueMap.find(key) == valueMap.end())
        return -1; // cache miss — this check is O(1)

    // Search the usage order to find where this key currently sits
    removeKeyFromOrder(key); // O(n) — must scan the whole list
    order.insert(order.begin(), key); // move it to the front

    return valueMap[key];
}

Complexity

• get() → O(n) in the worst case (due to findInList scan), though hashmap lookup itself is O(1).
• put() → O(n) in the worst case for the same reason.
• Space → O(capacity).

Pros and Cons

Pros:

• ✅ Value lookup (valueMap.find) is O(1) — a genuine improvement over brute force.
• ✅ Simpler mental model than full DLL + hashmap.

Cons:

• ❌ We still don't have O(1) positional access — we know the value instantly, but not where the node lives in the ordering list, so reordering still costs O(n).
• ❌ Still fails the strict O(1) get/put requirement.

💡 The missing piece: we need the hashmap to store not just the value, but a direct pointer to the node in the list — so we can splice it out in O(1) without any search. That's exactly what the optimal approach does.

8. Optimal Approach

Core Intuition

The fix to the "Better Approach" is simple but powerful: instead of storing key → value in the hashmap, store key → node pointer. That way, given any key, we can jump directly to its node in the linked list in O(1) — no traversal needed — and since it's a doubly linked list, we can unlink and relink it in O(1) too.

Why HashMap + Doubly Linked List Is Optimal

Together, these two structures give us true O(1) average time for every operation.

Structure of Each Node

Each node in the doubly linked list stores:

class Node {
public:
    int key;     // needed so we can remove it from the hashmap during eviction
    int value;
    Node* prev;
    Node* next;
};

📌 Why store key inside the node? When we evict the least recently used node, we only have a Node* pointer (from the tail side) — we don't automatically know its key. Storing the key inside the node lets us do cache.erase(node->key) in O(1) without any extra lookup.

Head and Tail Dummy Nodes

We maintain two dummy (sentinel) nodes:

• head → a placeholder marking the most recently used side.
• tail → a placeholder marking the least recently used side.

Real nodes always live between head and tail.

• The node right after head is always the most recently used.
• The node right before tail is always the least recently used (eviction target).

Why Dummy Nodes Simplify Implementation

Without dummy nodes, we'd need to constantly check "is this the first node?" or "is this the last node?" with if (head == nullptr) style edge-case handling scattered everywhere.

With dummy head and tail nodes:

• Insertion at the front is always insertAfterHead(node) — no special case for an empty list.
• Eviction is always tail->prev — no special case for checking if the list is empty (as long as capacity >= 1 and we only evict when full).
• Removal never needs to check if node->prev == nullptr — because a real node's prev is never nullptr; it's at worst the head dummy.

✅ Callout: Dummy nodes trade a tiny bit of extra memory (2 nodes) for eliminating an entire category of null-pointer edge cases. This is a widely used technique in linked-list based interview problems.

Every Operation, Explained Visually

Helper Functions Explained

removeNode(Node* node)

Unlinks a node from wherever it currently sits in the list by rewiring its neighbors to point to each other.

void removeNode(Node* node) {
    Node* prevNode = node->prev;
    Node* nextNode = node->next;
    prevNode->next = nextNode;
    nextNode->prev = prevNode;
}

This works regardless of where the node is (front, middle, or just before tail) — that's the power of a doubly linked list. Runs in O(1).

insertAfterHead(Node* node)

Inserts a node right after the dummy head, making it the new "most recently used" node.

void insertAfterHead(Node* node) {
    Node* nextNode = head->next;
    head->next = node;
    node->prev = head;
    node->next = nextNode;
    nextNode->prev = node;
}

Runs in O(1) — always a fixed 4-pointer rewire.

moveToFront(Node* node)

Simply combines the two helpers above: remove the node from its current spot, then reinsert it right after head.

void moveToFront(Node* node) {
    removeNode(node);
    insertAfterHead(node);
}

This is called whenever a key is accessed via get() or updated via put(), since both actions make that key the most recently used.

9. Complete Algorithm

get(key) — Step by Step

1. Check if key exists in the hashmap.
2. Cache miss: If not found, return -1.
3. Cache hit: If found:
   • Retrieve the Node* from the hashmap.
   • Call moveToFront(node) to mark it as most recently used.
   • Return node->value.

put(key, value) — Step by Step

1. Key already exists:
   • Retrieve the Node* from the hashmap.
   • Update node->value = value.
   • Call moveToFront(node).
2. New key:
   • Check capacity: If cache.size() == capacity (cache is full):
     • Identify the least recently used node: tail->prev.
     • Remove it from the linked list using removeNode().
     • Erase its key from the hashmap.
     • Delete the node (free memory).
   • Create a new Node(key, value).
   • Insert it into the hashmap: cache[key] = newNode.
   • Call insertAfterHead(newNode) to place it as most recently used.

📌 Note: The order of "evict first, then insert" vs "insert first, then evict" doesn't matter functionally as long as you correctly check capacity before adding a brand-new key — never evict when simply updating an existing key.

10. Dry Run

Let's trace through the exact example requested, with Capacity = 2.

Operations: put(1,1) → put(2,2) → get(1) → put(3,3) → get(2) → put(4,4) → get(1) → get(3) → get(4)

Step-by-step reasoning for the tricky evictions:

• Step 4: Before inserting key 3, cache size is already 2 (= capacity). The LRU node (tail->prev) is key 2 (since key 1 was refreshed in step 3, making key 2 the least recently used). So key 2 is evicted.
• Step 6: Before inserting key 4, cache size is 2 again. The LRU node is key 1 (it hasn't been touched since step 3, while key 3 was touched in step 4). So key 1 is evicted.

C++ Code (Interview-Quality, Complete Implementation)

#include <unordered_map>
using namespace std;

// Doubly linked list node storing a key-value pair
class Node {
public:
    int key;
    int value;
    Node* prev;
    Node* next;

    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    unordered_map<int, Node*> cache; // key -> node pointer, gives O(1) lookup
    Node* head; // dummy head: node right after it = most recently used
    Node* tail; // dummy tail: node right before it = least recently used

    // Detach a node from its current position in the list. O(1).
    void removeNode(Node* node) {
        Node* prevNode = node->prev;
        Node* nextNode = node->next;
        prevNode->next = nextNode;
        nextNode->prev = prevNode;
    }

    // Insert a node right after the dummy head (marks it as most recently used). O(1).
    void insertAfterHead(Node* node) {
        Node* nextNode = head->next;
        head->next = node;
        node->prev = head;
        node->next = nextNode;
        nextNode->prev = node;
    }

    // Move an existing node to the front of the list. O(1).
    // Called whenever a key is accessed (get) or updated (put).
    void moveToFront(Node* node) {
        removeNode(node);
        insertAfterHead(node);
    }

public:
    LRUCache(int cap) {
        capacity = cap;
        head = new Node(-1, -1); // dummy, value unused
        tail = new Node(-1, -1); // dummy, value unused
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1; // cache miss
        }
        Node* node = it->second;
        moveToFront(node); // cache hit -> refresh recency
        return node->value;
    }

    void put(int key, int value) {
        auto it = cache.find(key);

        if (it != cache.end()) {
            // Key already exists: update value and refresh recency
            Node* node = it->second;
            node->value = value;
            moveToFront(node);
            return;
        }

        // New key: check capacity before inserting
        if ((int)cache.size() == capacity) {
            // Evict the least recently used node (just before tail)
            Node* lru = tail->prev;
            removeNode(lru);
            cache.erase(lru->key);
            delete lru; // free memory to avoid leaks
        }

        // Insert the new node as most recently used
        Node* newNode = new Node(key, value);
        cache[key] = newNode;
        insertAfterHead(newNode);
    }

    // Destructor: free all allocated nodes to prevent memory leaks
    ~LRUCache() {
        Node* curr = head;
        while (curr != nullptr) {
            Node* next = curr->next;
            delete curr;
            curr = next;
        }
    }
};

11. Correctness Proof

We need to prove two things:

Claim 1: The node immediately after head is always the most recently used key, and the node immediately before tail is always the least recently used key.

Proof by invariant: We maintain the invariant that every time a key is touched (via get returning a hit, or put inserting/updating), we immediately call either insertAfterHead() (for new nodes) or moveToFront() (for existing nodes) — both of which place that node directly after head. Since this happens immediately after every touch, and no other operation reorders the list, the node after head is, by induction, always the most recently touched key at any point in time. Since the list is finite and ordered, the node before tail must be the one that has gone the longest without being touched — i.e., the least recently used.

Claim 2: Eviction always removes the correct (least recently used) key.

Proof: Eviction only happens when inserting a brand-new key while cache.size() == capacity. At that moment, by Claim 1, tail->prev is guaranteed to be the least recently used node among all currently cached keys. Removing it and erasing it from the hashmap keeps the hashmap and linked list perfectly synchronized — every key in the hashmap has exactly one corresponding node in the list, and vice versa.

Claim 3: get() and put() always reflect the true current value.

Proof: The hashmap always stores the up-to-date Node* for a key (nodes are updated in place via node->value = value, never replaced), so get() always reads the latest value. Since keys are never duplicated (we check cache.find(key) before creating a new node), each key maps to exactly one node at all times.

Together, these three claims guarantee the algorithm always returns the correct value for get() and always evicts the correct key during put().

12. Complexity Analysis

Why Every Operation Becomes O(1) in the Optimal Approach

• HashMap lookup (cache.find(key)) → O(1) average, since hashing gives direct bucket access.
• removeNode() → O(1), because we directly access node->prev and node->next — no traversal needed.
• insertAfterHead() → O(1), because head is a fixed reference point — always a constant number of pointer updates.
• moveToFront() → O(1), since it's just removeNode() + insertAfterHead(), both O(1).
• Eviction → O(1), since tail->prev gives direct access to the LRU node without any search.

🚀 The key insight: O(1) is achievable only because the hashmap gives us the node pointer directly — eliminating the need to search for a node's position before we can remove or reorder it.

15. Interview Tips

Here are common follow-up questions interviewers ask after you present the optimal solution:

1. "Can you make this thread-safe?" Discuss using a mutex to lock around get/put, and mention trade-offs (a global lock hurts concurrency; finer-grained locking is complex due to shared list pointers).
2. "How would you implement an LFU (Least Frequently Used) Cache instead?" Explain that LFU requires tracking frequency counts, typically using a hashmap of frequency → doubly linked lists (an extra layer of complexity).
3. "What if capacity is 0?" Clarify with the interviewer — typically constraints guarantee capacity >= 1, but you should handle it gracefully (e.g., every put immediately evicts, or you simply never insert).
4. "Can you use std::list from STL instead of writing your own doubly linked list?" Yes — std::list<pair<int,int>> plus a hashmap of key -> list iterator achieves the same O(1) behavior, since std::list supports O(1) splicing given an iterator. Be ready to discuss why storing an iterator in the map (not just a value) is essential here.
5. "How would you scale this to a distributed cache?" Mention consistent hashing to distribute keys across multiple cache nodes, and that each node can run its own local LRU instance.
6. "What's the space overhead of your solution?" Each node stores extra prev/next pointers plus a hashmap entry, so it's roughly O(capacity) with a higher constant factor than a plain array — but this is the necessary trade-off for O(1) time.

💡 Tip: Always mention why simpler approaches fail (arrays, singly linked lists) before jumping to the optimal solution — interviewers want to see your reasoning process, not just memorized code.

16. Frequently Asked Questions

Q1. What is the time complexity of LRU Cache operations? Both get() and put() run in O(1) average time complexity using the HashMap + Doubly Linked List approach.

Q2. Why can't we use only a HashMap for LRU Cache? A HashMap gives O(1) lookup but has no concept of ordering, so it cannot tell us which key was least recently used without additional bookkeeping.

Q3. Why can't we use only a Doubly Linked List without a HashMap? Without a hashmap, finding whether a key exists (and where its node is) would require traversing the list — O(n) — defeating the purpose.

Q4. Why is a Doubly Linked List used instead of a Singly Linked List? Because deletion requires access to a node's previous node too. A singly linked list only knows the next node, forcing an O(n) traversal to find the previous node before deletion.

Q5. What is the purpose of dummy head and tail nodes? They eliminate special-case handling for empty lists or single-node lists, simplifying insertAfterHead() and eviction logic significantly.

Q6. Can I implement LRU Cache using Java's LinkedHashMap? Yes — Java's LinkedHashMap has a built-in "access order" mode and can override removeEldestEntry() to implement LRU in just a few lines, since it internally maintains a doubly linked list already.

Q7. What happens if put() is called with a key that already exists? The value is updated, and the key is marked as most recently used — no eviction occurs since no new key is being added.

Q8. Is LRU Cache related to Operating Systems concepts? Yes — it's directly analogous to the page replacement algorithm used in virtual memory management, where the OS evicts the least recently used memory page when RAM is full.

Q9. What is the space complexity of the optimal LRU Cache solution? O(capacity), since we store exactly one hashmap entry and one linked list node per cached key (plus 2 constant-size dummy nodes).

Q10. How is LRU different from LFU (Least Frequently Used)? LRU evicts based on recency of access (when it was last used), while LFU evicts based on frequency of access (how many times it was used) — different eviction philosophies for different workloads.

Q11. Does the order of checking capacity vs. inserting matter in put()? No, as long as you only evict for brand-new keys and check capacity before the cache would exceed its limit — both "evict-then-insert" and equivalent logic produce identical results.

Q12. Can this problem be solved without a linked list, using an ordered map? In some languages, an ordered structure with efficient reordering (like Python's OrderedDict) can substitute for the manual doubly linked list, since it provides similar O(1) move-to-end/front semantics internally.

17. Key Takeaways

• 🔑 LRU Cache evicts the least recently used item when capacity is exceeded.
• 🔑 A HashMap alone is insufficient because it lacks ordering information.
• 🔑 A Doubly Linked List alone is insufficient because lookups would require O(n) traversal.
• 🔑 The optimal solution combines both: HashMap for O(1) lookup, Doubly Linked List for O(1) reordering and eviction.
• 🔑 Dummy head/tail nodes remove edge-case complexity from insertion and deletion logic.
• 🔑 Every key touch — whether via get() or put() — must move that node to the "most recently used" position.
• 🔑 Eviction always targets the node just before tail, guaranteed by the maintained invariant.
• 🔑 This problem is a favorite in interviews because it tests system design thinking at a small scale — recognizing which data structure combination satisfies strict time-complexity constraints.

🎯 Final tip: When solving this in an interview, always narrate your reasoning — explain why brute force fails, why HashMap alone fails, and how combining it with a Doubly Linked List solves every bottleneck. This is what separates a "correct" answer from a great answer.

video reference:

code link:

https://leetcode.com/problems/lru-cache/description/