LRU cache: hash map plus doubly linked list

LeetCode 146 prints two characters that scare interview candidates more than the rest of the problem combined: O(1). Both get and put must run in constant time. Read the constraint twice. The cache holds up to 3,000 entries, the LRU policy demands you find and evict the least-recently-touched item on every overflow, and the only way through the contract at the time bound asked is a structure that almost no candidate has built before they encountered this problem.

The reason it scares people is that the obvious answers all almost work. A hash map gets get to O(1) average and has no idea what "least recently used" means. Reach instead for a doubly linked list, and eviction-from-the-tail is O(1), but now there is no way to find the node for a given key without walking the list. Sort by access timestamp? O(n) on every touch. Min-heap by access time? O(log n). Each single-structure attempt fails at exactly one of the two operations, and the failure is at the worst possible spot in the API. The fix is to wire two structures together so each handles the operation the other cannot.

The contract#

Three operations, all expected O(1):

• LRUCache(capacity) — create a cache that holds at most capacity key-value pairs.
• get(key) — return the value if the key is present, -1 otherwise. A hit counts as a use.
• put(key, value) — insert or update. If the cache is at capacity and the key is new, evict the entry not touched for the longest time. An update counts as a use.^[1]

Three subtleties make the problem harder than its API suggests. The first: an update on an existing key promotes the entry to most-recently-used. put(k, v) is not "write a value"; it is "write a value AND mark this entry as touched". The LC test suite enforces this; miss it, and you fail tests around capacity 1.^[1:1] The second: eviction picks the entry at the tail of the recency order, never an entry the caller just operated on, even if the operation was an update. The third: hits never mutate the value, but they always mutate the recency order. A get is a write to the structure even though it looks like a read to the caller.

Why one structure is never enough#

Walk through what each single structure costs.

Hash map only. get is O(1) average. put to write is O(1) average. But "evict the least-recently-touched key" requires you to know which key that is, and a hash map has no order. You'd have to scan all n entries to find the oldest timestamp. Eviction is O(n).

Doubly linked list only. Splice the most-recently-touched node to the head; pop the tail when you evict. Both are O(1) given a pointer to the node. But get(key) has to find the node first, and a linked list does not index by key. Walk the list: O(n). The hit path is O(n).

Sorted array by timestamp. Eviction is O(1) at one end. get(key) is O(n) without an index, or O(log n) with binary search by key (and now you have to maintain that index too). Worse: every hit shifts the touched entry to one end, displacing every entry in between. O(n) on each access.

Min-heap keyed on access time. get is still O(n) without a side hash map. Eviction is O(log n). The structure is closer than the others, but it pays log time for the get you wanted constant-time.

Each attempt fails at exactly one operation. The dual-structure trick cures this by giving each operation to the structure that handles it natively.

Each single structure has one operation it cannot do in O(1). The dual structure assigns each operation to the half that handles it natively.

The dual structure#

Two pieces, bound by one rule.

A doubly linked list holds the entries in recency order. The node closest to the head is the most-recently-used; the node closest to the tail is the least-recently-used. Splicing a node to the head is four pointer assignments. Removing a node from anywhere in the list is two pointer assignments, given a pointer to the node. The doubly linked variant matters: a singly linked list cannot delete x in O(1) because it has no way to reach x.prev to rewrite its next pointer.^[2]

A hash map maps each key to the linked-list node that holds it. Not to the value, but to the node. This is the load-bearing detail. When get(key) runs the map lookup, it gets back the exact node it needs to splice to the head, with no list walk required. Both halves of the LRU contract collapse to O(1) average: the map handles "find by key", the list handles "splice and evict by recency".

Two invariants tie the structures together:

1. The map and the list always hold the same set of keys. Every map insert pairs with a list add_to_front. Every map delete pairs with a list remove.
2. The map's value type is the node pointer, never the user-facing value. The user-facing value lives inside the node.

Every key in the map points to a node in the list. Left-to-right order in the list encodes recency, MRU on the left and LRU on the right. The map handles lookup; the list handles ordering.

Doubly linked lists introduced the prev/next mechanics this chapter assumes. Linked-list fundamentals introduced sentinels, and they earn their place again here. The list always holds two dummy nodes the algorithm never touches: a head sentinel before the MRU, a tail sentinel after the LRU. With sentinels, every splice and every remove becomes four pointer assignments with no branching for "is this the head?" or "is this the tail?". Without sentinels, those edge cases multiply, and one of them is always wrong.^[2:1]

The four operations#

Two helpers do the pointer surgery; get and put compose them.

def _remove(self, node):
    node.prev.next = node.next
    node.next.prev = node.prev

def _add_to_front(self, node):
    node.next = self.head.next
    node.prev = self.head
    self.head.next.prev = node
    self.head.next = node

_remove unlinks an arbitrary node from anywhere in the list: middle, end, doesn't matter. Two writes. _add_to_front splices a node in just after the head sentinel. Four writes. Neither helper checks for null, neither special-cases the empty list. The sentinels guarantee node.prev and node.next are always real nodes, even when the list logically holds zero entries (because then head.next == tail and tail.prev == head).

get(key) is one map lookup, one detach, one splice:

def get(self, key):
    node = self.map.get(key)
    if node is None:
        return -1
    self._remove(node)
    self._add_to_front(node)
    return node.value

The hit path runs three O(1) operations. By the sum rule, the total is O(1).^[2:2][3] The miss path is one O(1) lookup and an early return.

put(key, value) has three branches, and the order matters:

def put(self, key, value):
    node = self.map.get(key)
    if node is not None:
        node.value = value
        self._remove(node)
        self._add_to_front(node)
        return
    if len(self.map) == self.capacity:
        lru = self.tail.prev
        self._remove(lru)
        del self.map[lru.key]
    new_node = _Node(key, value)
    self.map[key] = new_node
    self._add_to_front(new_node)

Read the branches in order. The update branch handles put on an existing key: write the new value, then splice to head, because update counts as a use. The eviction branch handles put on a new key when the cache is full: read tail.prev (always a real node thanks to the tail sentinel), unlink it from the list, and delete its key from the map. Both halves of that paired delete must run, or the next get(evicted_key) returns a stale node. The insert branch then creates the new node and splices it after the head.

The eviction branch runs before the insert branch, never after. Insert-then-evict can pick the just-inserted node as the LRU when capacity equals 1, evicting the entry the caller wanted. The bug is rare and silent everywhere except the capacity-1 thrash test, which is exactly why LC includes that test.

The full hand-rolled implementation:

# LC 146. LRU Cache
from typing import Optional


class _Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key: int, value: int) -> None:
        self.key = key
        self.value = value
        self.prev: Optional["_Node"] = None
        self.next: Optional["_Node"] = None


class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.map: dict[int, _Node] = {}
        # Sentinel head and tail. head.next is most recently used; tail.prev is LRU.
        self.head = _Node(0, 0)
        self.tail = _Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: _Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        new_node = _Node(key, value)
        self.map[key] = new_node
        self._add_to_front(new_node)

// LC 146. LRU Cache
import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private static final class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head;   // sentinel; head.next = MRU
    private final Node tail;   // sentinel; tail.prev = LRU

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        remove(node);
        addToFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            addToFront(node);
            return;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToFront(newNode);
    }
}

// LC 146. LRU Cache
#include <list>
#include <unordered_map>
#include <utility>

class LRUCache {
public:
    explicit LRUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) {
            return -1;
        }
        // splice moves the node to the front of order_ in O(1) without
        // invalidating the iterator stored in map_; this is why std::list
        // is the right C++ idiom.
        order_.splice(order_.begin(), order_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = value;
            order_.splice(order_.begin(), order_, it->second);
            return;
        }
        if (static_cast<int>(map_.size()) == capacity_) {
            map_.erase(order_.back().first);
            order_.pop_back();
        }
        order_.emplace_front(key, value);
        map_[key] = order_.begin();
    }

private:
    int capacity_;
    std::list<std::pair<int, int>> order_;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map_;
};

// LC 146. LRU Cache
package main

type lruNode struct {
	key, value int
	prev, next *lruNode
}

type LRUCache struct {
	capacity   int
	cache      map[int]*lruNode
	head, tail *lruNode // sentinels: head.next = MRU; tail.prev = LRU
}

func Constructor(capacity int) LRUCache {
	head := &lruNode{}
	tail := &lruNode{}
	head.next = tail
	tail.prev = head
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*lruNode, capacity),
		head:     head,
		tail:     tail,
	}
}

func (c *LRUCache) remove(node *lruNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (c *LRUCache) addToFront(node *lruNode) {
	node.next = c.head.next
	node.prev = c.head
	c.head.next.prev = node
	c.head.next = node
}

func (c *LRUCache) Get(key int) int {
	node, ok := c.cache[key]
	if !ok {
		return -1
	}
	c.remove(node)
	c.addToFront(node)
	return node.value
}

func (c *LRUCache) Put(key, value int) {
	if node, ok := c.cache[key]; ok {
		node.value = value
		c.remove(node)
		c.addToFront(node)
		return
	}
	if len(c.cache) == c.capacity {
		lru := c.tail.prev
		c.remove(lru)
		delete(c.cache, lru.key)
	}
	node := &lruNode{key: key, value: value}
	c.cache[key] = node
	c.addToFront(node)
}

The __slots__ declaration on _Node saves about 56 bytes per node on CPython 3.11 by suppressing the per-instance __dict__; it is the standard idiom for hot-path internal classes. The C++ version uses std::list::splice, which is constant-time and explicitly preserves iterator validity for the moved element; that preservation is what lets the unordered_map store list iterators without rebuilding them on every hit. The Go version stores *lruNode pointers in the map, not values, because Go map values are copied on access; storing values would break the identity binding between map entries and list nodes. The Java version mirrors the Python structure directly with a private inner Node class.

What the production-grade shortcut hides#

Every standard library has the same data structure ready to use. Python's collections.OrderedDict keeps entries in insertion order and exposes move_to_end(key, last=True) and popitem(last=False), both O(1).^[4] Java has LinkedHashMap with the accessOrder = true constructor flag and an overridable removeEldestEntry callback that wires the eviction policy directly into the map. C++ has nothing built in; std::list plus std::unordered_map is the canonical idiom. Go's container/list plus a map[K]*list.Element is the parallel.

A production engineer writes the OrderedDict version. An interviewer hearing "I'd use OrderedDict" has heard nothing about whether you understand the underlying structure. The hand-rolled version above is the answer for the interview because the interviewer is testing whether you can compose the two structures yourself; it is also the answer for any production system where the OrderedDict layer is too high-level (a non-Python service, a custom invariant the stdlib doesn't expose, a memory layout you control). The shortcut is fine for production code in Python or Java; the mechanic underneath is what gets you past LC 146 and the senior loops at Meta, Amazon, and Google that ask the same question.

Walking the canonical sequence#

Take capacity 2 and the operation sequence put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4). This is the LC 146 example. The widget below scrubs through all ten steps; the prose narrates only the moments where the answer changes.

The build is uneventful: put(1,1) then put(2,2) puts node 2 at the head and node 1 at the tail. The first interesting moment is step 3, the get(1) hit. Node 1 detaches from the tail position and splices to the head. Node 2 slides to the tail. The hit changed the eviction order.

That promotion is what determines step 4. put(3,3) finds the cache full. The tail-prev sentinel hands back the LRU, which is now node 2 because of the step-3 promotion, and step 4 evicts node 2, not node 1. Run the same sequence without step 3, and node 1 evicts instead. The rest of the trace is mechanical: misses on the evicted keys, hits on the live keys, each hit shuffling the recency order one position.

Static fallback: ten keyframes showing the hash-map row and the doubly-linked-list row side by side. Each step highlights the active node, the about-to-evict node when applicable, and the post-op MRU and LRU.

State machine for put#

put has three distinct paths through the code, and which one fires depends on the state of the map and the size:

Update-and-promote, insert-no-evict, and insert-with-evict are the three paths. Eviction always runs before insert when both fire; the order is what makes the capacity-1 case correct.

What it actually costs#

Every operation hits O(1) average, given simple uniform hashing on the map.

CLRS Chapter 10 §10.2 establishes that LIST-DELETE and LIST-INSERT on a doubly linked list each run in O(1) given a pointer to the node, and the §10.2 sentinel argument removes the empty-list edge case from every splice.^[2:4] CLRS §11.2 Theorem 11.1 establishes that an unsuccessful chained-hash search runs in expected Theta(1 + alpha) time under simple uniform hashing, and Theorem 11.2 gives the same bound for successful searches. With load factor alpha bounded by a constant (Java's HashMap keeps it below 0.75 by resizing, Python's dict does similar), both bounds collapse to O(1) average.^[3:3] The composition is the key step: an LRU get is one map lookup plus one DLL detach plus one DLL splice, three O(1) steps, total O(1).

The "average" qualifier matters at staff level. An attacker who controls the keys and knows the hash function can drive every key into the same bucket; the chained-hash chain becomes a linked list, and lookups degrade to O(n) per call. Klink and Walde demonstrated this against Python and Ruby web frameworks in 2011; CPython responded with PEP 456 and SipHash, and Java responded by treeifying long chains beyond a threshold. An LRU cache backing a public API inherits this exposure, and the mitigation is the hash function, not the cache structure.

How LFU and the cursor variants extend the shape#

The dual-structure idea generalizes. Two close cousins appear on the ladder.

LFU (LC 460). The eviction axis is access frequency, ties broken by recency. The naive solution keeps a min-heap keyed on access count, paying O(log n) per operation. Matani, Shah, and Mitra showed in 2010 that you can keep all operations at O(1) average by replacing the heap with a doubly linked list of frequency buckets, where each bucket is itself a doubly linked list of entries at that frequency. The hash map maps key -> entry node and a side hash map maps frequency -> bucket node. On a hit, the entry detaches from its current frequency bucket and splices into the bucket for frequency + 1; eviction pops the tail entry of the smallest-frequency bucket.^[5] LRU is the special case where every entry has frequency 1.

Browser history (LC 1472). Two access modes again, but the secondary axis is position not recency. The structure is the doubly linked list itself plus a current pointer field. back(n) walks current n steps backward, forward(n) walks it n steps forward, and visit(url) severs the forward chain (current.next = new Node(url)). No hash map this time, because there is no key-based lookup, just cursor walks. Same dual-structure mental shape, different secondary axis.

The shared lesson: any time a problem demands O(1) for two distinct access modes on the same collection, the answer is two structures with bound state. LRU's two modes are key-lookup and recency-eviction. LFU's are key-lookup and frequency-bucket-walk. Browser history's are positional walk forward and backward. The pattern outlives the specific problem.

Where readers go wrong#

Problem ladder#

CORE (solve all three to claim chapter mastery)#

• LC 146 — LRU Cache [Medium] • hash-map-plus-doubly-linked-list-cache ★
• LC 460 — LFU Cache [Hard] • hash-map-plus-frequency-bucketed-dll
• LC 1472 — Design Browser History [Medium] • doubly-linked-list-with-current-cursor

STRETCH (optional)#

• LC 1206 — Design Skiplist [Hard] • probabilistic-multilevel-linked-list

The dual-data-structure pattern admits no canonical Easy LC; LC 705 and LC 706 (Design HashSet, Design HashMap) drop the linked-list half, and LC 707 (Design Linked List) is itself Medium. The CORE+STRETCH set spans Medium / Hard / Medium / Hard, and the ladder carries the core-emh-via-stretch curation flag to record the absent Easy band. LC 432 (All O`one Data Structure) is a fourth dual-structure problem with the same shape, registry-locked to Hash collisions and the load factor; cite it there for the frequency-bucket variant if you want a second pass at the LFU mechanic.

Where this leads#

The eviction policy is one decision in a family. LRU evicts by recency. LFU evicts by frequency. ARC (Adaptive Replacement Cache, used in ZFS) keeps two LRU lists and shifts entries between them based on observed access patterns. W-TinyLFU (the policy behind Caffeine, the JVM cache library) uses a small admission filter plus a sketch of frequency to keep the hit rate high under skewed workloads. Redis offers maxmemory-policy allkeys-lru and allkeys-lfu as configuration knobs; Memcached uses a slab-LRU hybrid; the Linux page cache approximates LRU with two lists (active and inactive). Designing the data structure walks the trade-offs at scale, where the question is no longer "implement LRU in O(1)" but "which eviction policy does this workload want, and why".

The pointer surgery you ran here (sentinels, _remove, _add_to_front, the four pointer assignments per splice) is the same surgery Reverse linked list used in a different shape. Linked-list mechanics are the substrate; the disciplines (LRU, LFU, cycle detection, in-place reversal) are different ways to compose them. Once the substrate clicks, the disciplines stop looking like separate algorithms and start looking like applications of the same primitive.

References#