LRU Cache

The problem that bites you first

Here is the concrete scenario. You're building a thumbnail service. Generating a thumbnail is expensive — 200ms of CPU per image. You want to cache the last 1000 results so repeated requests are instant. The rules:

1. get(key) — return the cached thumbnail if it exists, else return -1 (miss).
2. put(key, value) — store a new thumbnail. If the cache is at capacity, evict the item that was accessed least recently to make room.

Both operations must be O(1). Honest aside: at 10,000 requests per second and capacity 1000, O(log n) is ~10 comparisons per operation — a single core would shrug it off. The O(1) requirement comes from elsewhere: the interview problem demands it, real cache libraries deliver it, and at millions of entries with per-request latency budgets the gap stops being academic. The structure that achieves it is worth knowing cold.

This is LeetCode 146 — one of the most common system-design interview openers, and for good reason. It tests whether you understand that the right data structure isn't just one thing.

Why one structure isn't enough

Work through why each solo approach fails:

Hash map only. Lookup is O(1), great. But when you need to evict, you don't know which key was used least recently. You'd have to scan all keys and compare timestamps — O(n).

Array with timestamps. Store (key, value, last_access_time) tuples. On eviction, scan for the minimum timestamp — O(n). Even with a min-heap tracking recency, promoting an item on access is O(log n) because you have to update its position in the heap. Not O(1).

Linked list only. The list maintains recency order perfectly — head is most recent, tail is LRU. Eviction is O(1): chop the tail. Access is O(n): scan for the key. Not O(1).

The breakthrough: the linked list handles ordering and eviction in O(1), but only once you have a pointer to the node. The hash map handles finding that node in O(1). Map stores key → node, not key → value. Then every operation is O(1):

• get: hash map lookup → get node pointer → move node to head → return node's value.
• put: create node → insert at head → store in hash map → if over capacity, remove tail node → delete tail's key from hash map.

flowchart LR
    subgraph "doubly linked list (recency order)"
        direction LR
        H["HEAD\n(dummy)"] <--> N1["thumb_99\nval=..."]
        N1 <--> N2["thumb_42\nval=..."]
        N2 <--> N3["thumb_07\nval=..."]
        N3 <--> T["TAIL\n(dummy)"]
    end
    subgraph "hash map"
        K1["key: 'thumb_99'"]
        K2["key: 'thumb_42'"]
        K3["key: 'thumb_07'"]
    end
    K1 --> N1
    K2 --> N2
    K3 --> N3
    style H fill:#00e5ff,color:#111
    style T fill:#ff2e88,color:#111
    style N1 fill:#a855f7,color:#fff

The hash map arrows all point into the list. The list maintains order. They share the same node objects — nothing is duplicated.

The sentinel trick that eliminates all edge cases

Before writing code, take one design decision seriously: use dummy head and tail sentinel nodes.

Without sentinels, every insert and delete has to handle "what if the list is empty?" and "what if I'm removing the only node?" Those are four extra if-checks scattered through your code, each one a potential bug under pressure. With sentinels:

dummy_head <-> [real nodes...] <-> dummy_tail

Real content always lives between the sentinels. Removing the true head means removing the node right after dummy_head. Removing the true tail means removing the node right before dummy_tail. The sentinels are never themselves removed. Your add-to-head and remove-from-tail functions are now unconditional — no null checks, no special cases.

This is a technique worth burning into muscle memory. Not just for LRU caches — any doubly linked list that needs to handle arbitrary insertions and deletions benefits from it.

The full implementation

class Node:
    """A doubly linked list node that holds both key and value.
    We store the key so that when we evict the tail, we know which
    key to delete from the hash map."""
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}                     # key → Node

        # Sentinel nodes: real content lives between these two.
        self.head = Node()                # dummy head (most recent side)
        self.tail = Node()                # dummy tail (eviction side)
        self.head.next = self.tail
        self.tail.prev = self.head

    # ── private helpers ──────────────────────────────────────────────

    def _remove(self, node: Node) -> None:
        """Splice a node out of the list — O(1)."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_at_head(self, node: Node) -> None:
        """Insert a node right after the dummy head — O(1)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    # ── public API ───────────────────────────────────────────────────

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)           # pull it out of its current position
        self._insert_at_head(node)   # put it at the front (most recent)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            # Update existing — just change value and promote.
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._insert_at_head(node)
        else:
            if len(self.map) == self.capacity:
                # Evict the LRU node — it's right before the dummy tail.
                lru = self.tail.prev
                self._remove(lru)
                del self.map[lru.key]   # lru.key is why we store key in Node
            node = Node(key, value)
            self.map[key] = node
            self._insert_at_head(node)

Walk through a concrete sequence to cement this. Capacity = 3.

put(1, "a")  →  list: [1]
put(2, "b")  →  list: [2, 1]
put(3, "c")  →  list: [3, 2, 1]
get(1)       →  list: [1, 3, 2]   (1 promoted to head)
put(4, "d")  →  list: [4, 1, 3]   (2 evicted — LRU was at tail)
get(2)       →  -1                 (2 is gone)
get(3)       →  list: [3, 4, 1]   (3 promoted)

The key moment is put(4, "d"). The cache is full. The tail's predecessor is node 2, which hasn't been touched since it was inserted first. It gets removed from the list, deleted from the map, done. Node 4 goes in at the head.

What the visualizer is showing you

{ "type": "linked-list", "title": "recency queue — head=most recent, tail=evict next", "data": [1, 3, 2] }

Imagine this list after get(1) in the sequence above. Node 1 is at the head because it was just accessed. Node 2 is at the tail and will be the eviction victim on the next put that exceeds capacity. One honest caveat about the widget: it renders a singly linked list, so its delete operation walks O(n) to find a predecessor. The real LRU list carries prev pointers, and that's exactly what makes the splice constant time. Only the spliced node and its immediate neighbors change — the rest of the list is untouched.

This is the O(1) moment. _remove splices the accessed node out with two pointer writes (close the gap on each side). _insert_at_head splices it back in with four (the node's own prev and next, plus the two neighbors it lands between). Six pointer writes, one hash map lookup — the map is what told you where the node lives without scanning. Constant time regardless of cache size.

The one-liner Python cheat (and when to use it)

Python's collections.OrderedDict is a dict plus a doubly linked list internally — the exact same design. So you can implement LRU in a handful of lines:

from collections import OrderedDict

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # promote to most-recent position
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        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 (the "first" item)

move_to_end(key) is O(1). popitem(last=False) removes the oldest entry in O(1). This is correct and production-worthy for single-threaded use — the concurrency caveat below applies to it just as much as to the from-scratch version.

Know when to use which version. In an interview where the question is explicitly "design an LRU cache" or "implement from scratch," write the explicit Node + doubly linked list version. It proves you understand the mechanics. If you're using an LRU cache as a component inside a larger solution, OrderedDict is the right call — it's faster to write, less likely to have bugs, and clearly communicates intent.

What about threads?

The thumbnail service from the opening serves 10,000 requests per second, which means concurrent get and put — and neither implementation on this page is thread-safe. A promotion is six pointer writes; interleave two promotions and you can end up with a node whose prev and next disagree about where it lives. The list is now silently corrupted, and the bug surfaces later as a lost node or an infinite loop during eviction. dict operations won't save you either — the race is in the list rewiring.

The boring fix works: one threading.Lock around the body of get and put. The critical section is a handful of pointer writes and a dict operation — well under a microsecond — so at 10k req/s a single lock is nowhere near a bottleneck. This is what functools.lru_cache does: the pure-Python version guards its bookkeeping with a lock (the C version gets the equivalent guarantee from the interpreter's own locking). When one lock does become the bottleneck — hundreds of threads, millions of ops per second — the standard move is sharding: run N independent LRU caches and route each key by hash(key) % N. Contention drops by roughly N; the price is that eviction is per-shard, so a globally cold key can survive in a lucky shard while a warmer key dies in a busy one. Most systems accept that trade without noticing.

This is also part of why Redis doesn't maintain an exact recency list at all — approximate sampled LRU keeps the hot path short and lock-free-ish, which matters more than eviction precision. More on that below.

Beyond LRU: LFU, and how real caches think about this

LRU is the right policy when recency predicts future access — which is true for most workloads. But it has a known failure mode: cache pollution from one-time scans. If you iterate through a 10GB dataset once, that scan evicts your hot working set entirely. Your cache goes cold on data that was being genuinely reused. This is called the "scan resistance" problem.

LFU (Least Frequently Used) evicts the item accessed the fewest times total. It resists pollution from one-time scans because newly loaded scan data has a count of one and gets evicted first. The downside: an item that was hot six hours ago but hasn't been touched since will still have a high count and won't get evicted. It takes longer to adapt to changing workloads.

The O(1) LFU implementation is more complex than LRU — it requires a hash map of frequency buckets, each bucket being a linked list of items at that frequency. Worth knowing exists; rarely asked to implement from scratch in interviews.

Redis eviction policies illustrate the spectrum real systems navigate:

Policy	What it evicts
noeviction	Returns errors when full — you decide what to do
allkeys-lru	LRU across all keys (the most common choice)
volatile-lru	LRU only among keys with a TTL set
allkeys-lfu	LFU across all keys (Redis 4.0+)
allkeys-random	Random eviction — fast but usually wrong

Redis's LRU is approximate — it samples a small number of keys and evicts the least-recently-used among the sample. This trades accuracy for speed and keeps the implementation simple. For most production use cases, the approximation is close enough and the performance is better.

Complexity summary

Operation	Average	Worst	Space
get(key)	O(1)	O(n) — hash collisions	—
put(key, value)	O(1)	O(n) — hash collisions	—
Eviction	O(1)	O(n) — hash collisions	—
Total space	—	—	O(capacity)

The list work is unconditionally constant: _remove writes 2 pointers, _insert_at_head writes 4 — six pointer writes plus one dictionary operation per promotion, no matter how large the cache is. The dictionary is the only asterisk: under pathological collisions a lookup degrades to O(n), the same caveat as any hash table. With Python's built-in dict you will not see it in practice, which is why everyone (including LeetCode) calls the whole thing O(1).

Common mistakes people make

Storing value in the map instead of node. If your map is key → value instead of key → node, you can't move the node to the front without first searching the list for it. You need the node pointer. Store key → node, and let node.val hold the value.

Forgetting to store key in the node. When evicting the tail, you need to remove that key from the hash map too. If your node only stores val, you have to walk the map to find which key to delete — O(n). Store both key and val in the node. This specific detail is easy to miss in the heat of an interview.

Not handling the update case in put. If you call put(key, new_value) on a key that already exists, two things must happen: update the value, AND promote the node to the head (it was just accessed). Forgetting the promotion is a bug — the old recency order is now wrong.

Using a singly linked list. The O(1) node removal only works with a doubly linked list. A singly linked list can delete the tail in O(1), but deleting an arbitrary interior node requires finding its predecessor — O(n). The moment you need to promote an arbitrary node on get, singly linked falls apart. If you need a refresher on the difference, the linked list article covers singly vs. doubly in detail.

Leaving stale keys in the map after eviction. Evict the tail from the list, fine. But if you don't call del self.map[lru.key], the map keeps growing indefinitely — the evicted values stay in memory and subsequent lookups on evicted keys return wrong results. The sentinel node design makes it easy to get at tail.prev.key before removal.

When NOT to use an LRU cache

Not every caching problem calls for LRU, and it's worth being explicit.

• Access patterns are uniform random. LRU is only better than random eviction when recency predicts future access. If every key is equally likely to be requested next, LRU's overhead (maintaining order) is pure cost. A simple bounded hash map with random eviction is faster.

• Your dataset fits in memory entirely. If there's no capacity pressure, there's nothing to evict. Use a plain hash table with no eviction machinery.

• Write-heavy workloads with few reads. LRU caches are most valuable when reads dominate — you want to serve cached values repeatedly. If you're mostly writing and each key is touched once, you're paying the maintenance cost with no benefit.

• You need TTL-based expiry, not recency-based eviction. LRU says "evict what was accessed longest ago." If you want "evict what has been here longest regardless of access," that's FIFO, not LRU — and a deque with a hash map is simpler and cheaper.

• You need both recency AND frequency signals. Some access patterns are better served by LFU or a hybrid policy like TinyLFU (used by Caffeine, the Java caching library, and by Twitter's cache systems). If your hot-set changes slowly but has genuine long-term regulars, LFU resists churn better.

The LRU cache is one of those designs that becomes a lens. Once you understand how combining a hash map with a doubly linked list achieves O(1) on all three axes — lookup, promotion, eviction — you start seeing the pattern elsewhere. Browser back/forward navigation. OS page replacement. CPU L1 caches. Database buffer pools. They are all, at their core, a recency queue backed by fast lookup. Different constraints, same shape.