LRU Cache: Hash Map + Doubly Linked List

July 2026 · 22 min read

The LRU cache is the single most asked "design a data structure" question, and for good reason: it is the smallest problem that forces you to compose two structures because neither one alone can meet the requirements. Solve it properly and you have the template for every hybrid structure that follows. This is LeetCode 146 — but we will derive the answer, not memorise it.

Start From the Requirements

The specification is three lines, and every design decision falls out of them:

• get(key) returns the value or -1, and counts as a use — in O(1).
• put(key, value) inserts or updates, also a use — in O(1).
• When inserting past capacity, evict the least-recently-used entry first.

Two demands are in tension. "O(1) lookup by key" screams hash map. "Evict the least-recently-used" screams an ordering by recency — which a hash map does not have. No single textbook structure gives you both O(1) keyed access and O(1) maintenance of a recency order. So you compose.

Why Two Structures, and How They Fit

Look at each half honestly:

The list can hold entries in recency order — most-recently-used at the front, least at the back — and move any node it already holds to the front in O(1). Its only weakness is finding a node by key. But that is exactly the hash map's strength. So the combination is:

A doubly linked list ordered by recency, and a hash map from key to the node pointer in that list. The map answers "where is this key's node?" in O(1); the list answers "reorder this node" and "who is least-recently-used?" in O(1). Neither stores the data twice — the map stores a pointer to the one node the list owns.

This is the payoff of a point made back in the memory model: a linked list is at its best precisely when you already hold a pointer to the node you want to move, because then the reorder is a couple of pointer writes and the O(n) walk never happens. The hash map exists to guarantee that precondition — every operation starts by looking up the node it needs, so the list is only ever asked to do the O(1) thing it is good at.

Why a Singly Linked List Cannot Work

This is the most important sentence in the whole problem, and the one interviewers probe. Both get and eviction must remove a node from the middle or back of the list in O(1). To unlink a node n you must connect n's predecessor to n's successor — which means you need a pointer to the predecessor. A singly linked list only stores next, so finding the predecessor of an arbitrary node requires walking from the head: O(n). Every promotion would be linear, and the whole O(1) guarantee collapses.

From Scratch: Two Sentinels, No Branches

Build the doubly linked list with two dummy nodes — a head sentinel and a tail sentinel that never hold data. Their entire purpose is to remove edge cases: with sentinels, every real node always has a non-null prev and next, so addFront and remove are branch-free — no "is this the first node?" or "is this the last node?" checks ever.

class LRUCache {
    struct Node {
        int key, val;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };

    int cap;
    std::unordered_map<int, Node*> table;   // key -> node in the list
    Node* head;   // sentinel; head->next is the MRU node
    Node* tail;   // sentinel; tail->prev is the LRU node

    void remove(Node* n) {                  // O(1), branch-free
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    void addFront(Node* n) {                // O(1), becomes MRU
        n->next = head->next;
        n->prev = head;
        head->next->prev = n;
        head->next = n;
    }

public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    ~LRUCache() {                           // own the nodes: free them all
        Node* p = head;
        while (p) { Node* nx = p->next; delete p; p = nx; }
    }

    int get(int key) {
        auto it = table.find(key);
        if (it == table.end()) return -1;   // miss -> -1
        Node* n = it->second;
        remove(n);
        addFront(n);                        // a read is a use: promote
        return n->val;
    }

    void put(int key, int value) {
        if (cap == 0) return;               // capacity-0 stores nothing
        auto it = table.find(key);
        if (it != table.end()) {
            Node* n = it->second;
            n->val = value;
            remove(n);
            addFront(n);                    // update is also a use: promote
            return;
        }
        if ((int)table.size() == cap) {     // full: evict LRU BEFORE inserting
            Node* lru = tail->prev;
            remove(lru);
            table.erase(lru->key);
            delete lru;
        }
        Node* n = new Node(key, value);
        table[key] = n;
        addFront(n);
    }
};

Every operation is a constant number of pointer writes plus one hash lookup: O(1) time for both get and put. The destructor walks the chain once and deletes every node including the sentinels — the cache owns its nodes, so it must free them.

Dry Run: Capacity 2

Trace put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4), writing the list most-recently-used first:

Note get(1) at step 3 is what saves key 1 from eviction at step 4 — had it not been touched, 2 would have survived instead. Recency is entirely about order of last touch.

The std::list::splice One-Liner

In production C++ you rarely hand-roll the list. std::list is a doubly linked list, and splice moves a node between positions without allocating, copying, or invalidating iterators. Store key → iterator and promotion becomes one line:

class LRUCache {
    int cap;
    std::list<std::pair<int, int>> items;   // front = MRU, back = LRU
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> table;

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

    int get(int key) {
        auto it = table.find(key);
        if (it == table.end()) return -1;
        items.splice(items.begin(), items, it->second);  // move node to front, O(1)
        return it->second->second;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        auto it = table.find(key);
        if (it != table.end()) {
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }
        if ((int)items.size() == cap) {
            table.erase(items.back().first);   // evict LRU
            items.pop_back();
        }
        items.push_front({key, value});
        table[key] = items.begin();
    }
};

The reason this works — and the reason you cannot swap in a std::vector — is iterator stability. The map stores iterators into the list. std::list::splice only relinks pointers, so the iterator to a moved element stays valid and keeps pointing at the same element. A std::vector stores elements contiguously; any insert or growth can reallocate the buffer and invalidate every iterator, pointer, and reference — so the map's stored positions would rot the moment the vector resized. Stability under structural change is precisely why the list is the correct container here.

Correctness Details People Miss

• Updating an existing key must promote it. A write is a use. If put on an existing key changes the value but forgets to move the node to the front, a freshly written key looks stale and may be evicted next — a subtle, test-passing-then-failing bug.
• Evict after deciding to insert, and only on a miss. Eviction happens when a new key arrives at full capacity, before the insert. Updating an existing key never evicts, because the size does not grow.
• Capacity 0. A zero-capacity cache stores nothing; put must return early, or the eviction step would try to remove tail->prev — which is the head sentinel — and corrupt the list.
• A miss returns -1, never 0 and never an exception.

What Production Caches Actually Do

The textbook LRU is rarely shipped verbatim. Real systems bend it:

• Thread safety. Every get mutates the list, so concurrent reads conflict. A single mutex serialises everything and becomes the bottleneck; the usual fix is sharding — N independent caches keyed by hash(key) % N, each with its own lock, so contention drops by roughly N.
• TTL. Attach an expiry timestamp per entry and treat expired entries as misses, lazily evicting them on access or via a background sweep.
• LRU-K. Evict based on the K-th most recent access rather than the last one, which resists a single scan blowing away a hot working set.
• CLOCK / second-chance. OS page replacement cannot afford a pointer move on every memory access, so it approximates LRU with a circular buffer and one reference bit per entry: on eviction it sweeps the "clock hand," giving referenced entries a second chance by clearing the bit instead of evicting. Redis's allkeys-lru is similarly approximate — it samples a handful of random keys and evicts the oldest of the sample rather than maintaining an exact global order.

The theme: exact LRU needs O(1) bookkeeping on every access, and at scale that bookkeeping — the pointer writes, the lock, the cache-line bouncing — costs more than the small hit-rate gain over a good approximation. So production trades exactness for cheaper, contention-free updates.

Complexity and Memory

Check Yourself

Six situations. Pick the statement that is actually true.

Practice

• LeetCode 146 — LRU Cache core build it from scratch with sentinels, then again with std::list::splice.
• LeetCode 460 — LFU Cache next the frequency-bucket sequel; keep both operations O(1).
• LeetCode 707 — Design Linked List warm-up nail the doubly linked pointer surgery in isolation.
• LeetCode 380 — Insert Delete GetRandom O(1) hybrid another hash-map-plus-container composition.
• LeetCode 1756 — Design Most Recently Used Queue variant move-to-end under a different access pattern.
• LeetCode 1429 — First Unique Number order a queue plus a map maintaining insertion order under removals.