LRU cache

What this chapter covers

A cache holds a limited number of items and, when full, must decide which to throw away. The least-recently-used (LRU) policy makes the natural choice: evict whatever hasn't been touched for the longest time, betting that recently-used data will be used again soon. It's the eviction policy behind CPU caches, page caches, web and CDN caches, database buffer pools, and application caches everywhere. This chapter is about how to build one efficiently, because it's a beautiful lesson in composition: a cache needs O(1) lookup and O(1) tracking of access order, and no single data structure gives both — but a hash map (fast lookup, no order) plus a doubly-linked list (fast reordering, no fast lookup) combine to give exactly the interface a cache needs. This chapter builds that composition, watches the recency list reorder on every access and evict from the back, and shows why LRU beats simpler policies on realistic access patterns.

A bit of history

Caching and the LRU idea are as old as memory hierarchies. The insight that makes LRU work — temporal locality, the tendency of programs to reuse recently-accessed data and code — was formalized in the 1960s alongside the development of virtual memory and paging. Les Belady's 1966 paper studied page-replacement algorithms and proved that the optimal policy (evict the item that won't be needed for the longest time into the future) is unachievable in practice because it requires knowing the future — so real systems approximate it, and LRU, which uses the recent past as a predictor of the near future, became the standard approximation. Belady also discovered the counterintuitive "Belady's anomaly," where FIFO replacement can get worse with more cache — a bug LRU doesn't have (LRU is a "stack algorithm," provably monotone in cache size). The efficient hash-map-plus-linked- list implementation became a programming staple, and today it's so common that Python ships it as the functools.lru_cache decorator and collections.OrderedDict, and "implement an LRU cache" is one of the most frequently asked coding-interview questions — precisely because it tests whether you can compose two structures to meet a two-part requirement.

The intuition

The requirement has two halves that pull in different directions. On every access you must (1) find the item by key, fast, and (2) mark it as most-recently-used, fast; and when the cache overflows you must (3) find and remove the least-recently-used item, fast. A hash map nails (1) — O(1) lookup by key — but has no notion of order, so it can't answer (2) or (3). A doubly-linked list nails (2) and (3) — you can move a node to the front or remove the back node in O(1) if you have a pointer to it — but finding a node by key means walking the list, O(n). Neither alone works. The trick is to use both, pointing at the same nodes: the hash map maps each key to its node in the linked list, and the linked list keeps the nodes ordered by recency.

Now all three operations are O(1). To get a key: look it up in the hash map (O(1)) to get its node, then unlink that node from wherever it is and splice it to the front of the list (O(1), because a doubly-linked list lets you remove a node given only a pointer to it). The front of the list is thus always the most-recently-used item, and the back is the least-recently-used. To put a new key when the cache is full: the eviction victim is simply the node just before the tail — the back of the list — so remove it from both the list and the hash map (O(1)), then add the new node at the front. That's the whole structure: the hash map provides random access, the doubly-linked list provides recency order, and they share nodes so that touching an item updates both views at once. Two simple structures, each O(1) at what it does, composed into one that's O(1) at everything the cache needs.

Complexity: how it scales

Every operation — get, put, and eviction — is O(1), independent of the cache size, using O(capacity) space. There are no loops: a hash-map lookup and a constant number of pointer splices. That efficiency is the how; the why — why LRU rather than a simpler policy — is about hit rate on real workloads, which the face-off measures. Real access patterns are skewed: a few items are hot, most are cold (a Zipf/power-law distribution, as seen in web traffic, database rows, and file access). The face-off runs such a workload through three eviction policies — LRU, FIFO (evict oldest-inserted), and random — and measures the cache hit rate:

LRU wins at every capacity. At a capacity of 50 (out of 500 keys), LRU achieved a 71% hit rate against FIFO's and random's 65% — a 6-point edge, which in caching terms is large: it means noticeably fewer trips to the slow backing store. The reason is that LRU keeps hot items resident: every access to a popular key moves it back to the front, so it survives eviction, while FIFO evicts it on a fixed schedule regardless of how often it's used and random evicts it by luck. The margin depends on the workload — with stronger temporal locality (recently-used items reused soon, as in real programs) LRU's advantage grows; with uniform random access (no locality) all policies converge, because there's nothing to predict. On the skewed, locality-rich patterns that real caches actually see, LRU's recency-based prediction consistently pays for the small bookkeeping cost of maintaining the list.

What it's good at, what it isn't

The LRU cache — and its efficient composition — is the right tool for any bounded cache over a workload with temporal locality, which is almost all of them. Memoization (caching function results — functools.lru_cache is exactly this), CPU and memory caches, OS page caches, database buffer pools and query caches, web browser and CDN caches, DNS caches, and application-level object caches all use LRU or a close variant. It's also the standard answer whenever you need a key-value store with O(1) access that also tracks usage order for any reason. The composition technique generalizes beyond caching: any time you need two O(1) operations that no single structure provides, combining structures that share nodes is the move (LRU is the canonical example, but the pattern recurs).

Where plain LRU struggles is scan-heavy workloads (a large sequential pass pollutes the cache with never-reused items, evicting hot data), workloads better predicted by frequency than recency (where LFU wins), and adversarial access patterns designed to defeat it. It also uses more memory per entry than a bare hash map (the two linked-list pointers per node) and more than a simpler policy like FIFO or random — which is why, when the hit-rate gain doesn't justify the bookkeeping (uniform access, tiny caches), a simpler policy suffices. Distributed caches add further complications (consistency, sharding) beyond the single-machine structure. For the common case — a bounded local cache over locality-rich accesses — LRU's O(1) operations and good hit rate make it the default, but production systems often reach for scan-resistant variants (ARC, 2Q, LRU-K) when the workload demands.

The data, or the inputs

The face-off runs a Zipf-distributed (power-law) access workload — a few hot keys, many cold ones, like real cache traffic — through LRU, FIFO, and random eviction policies at several capacities, measuring the hit rate of each. Correctness is checked by running hundreds of random get/put sequences through the hand-built hash-map-plus-linked- list cache in lockstep with a collections.OrderedDict reference, asserting identical return values and, crucially, identical recency order after every operation. The animation runs a capacity-4 cache through a sequence of gets and puts, drawing the recency list from most- to least-recently-used and showing a get promote a key to the front and a full put evict the back.

Build it, one function at a time

The LRU cache — a hash map and a doubly-linked list sharing nodes, all operations O(1):

class LRUCache:
    """Capacity-bounded LRU cache. `store` maps key → node for O(1) lookup; a doubly-linked list
    with head/tail sentinels keeps nodes in recency order — front (head.next) is most-recently-used,
    back (tail.prev) is least-recently-used and the eviction victim."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.head = _Node()                       # sentinel: MRU side
        self.tail = _Node()                       # sentinel: LRU side
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _push_front(self, node):
        node.next = self.head.next                # splice just after the head sentinel (MRU)
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        """Return the value and mark the key most-recently-used (move its node to the front). Returns
        None on a miss. O(1): a dict lookup plus two pointer splices."""
        node = self.store.get(key)
        if node is None:
            return None                           # miss
        self._unlink(node)
        self._push_front(node)                    # touch → becomes most recently used
        return node.val

    def put(self, key, val):
        """Insert or update a key as most-recently-used. If the cache is full and the key is new,
        evict the least-recently-used node (the one just before the tail sentinel) first. O(1)."""
        node = self.store.get(key)
        if node is not None:
            node.val = val
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.store) >= self.capacity:
            lru = self.tail.prev                  # the least-recently-used node
            self._unlink(lru)
            del self.store[lru.key]               # evict it
        node = _Node(key, val)
        self.store[key] = node
        self._push_front(node)

    def order(self):
        """The keys from most- to least-recently-used — for inspection and the animation."""
        out, cur = [], self.head.next
        while cur is not self.tail:
            out.append(cur.key)
            cur = cur.next
        return out

Watch it work

Here's a capacity-4 LRU cache. The cells show the recency list, most-recently-used on the left (MRU) and least on the right (LRU). Watch the two kinds of operation. A put of a new key inserts it at the front, and if the cache is full, first evicts the key at the back — the least-recently-used — to make room; watch E arrive and evict B, the item untouched the longest. A get is the subtler one: get A finds A and moves it to the front (green), marking it most-recently-used, which changes who gets evicted next — because A was just touched, it's now safe, and something else becomes the eviction victim. Follow the list reorder on every access: the front fills with what you're using, the back accumulates what you've neglected, and eviction always takes from the neglected end. That constant reshuffling is what keeps hot data resident:

The complete code

The from-scratch tab is the LRU cache built from a hash map and a doubly-linked list; the library tab is the collections.OrderedDict version (the standard-library way and the correctness reference) plus the FIFO and random policies from the hit-rate face-off, with a note on functools.lru_cache. Flip between them — the OrderedDict version is shorter because it hides the linked list inside a battery-included structure, but it's the same algorithm, which is exactly what building it by hand reveals.

"""LRU cache — a fixed-capacity key-value store that, when full, evicts the LEAST RECENTLY USED
item to make room. It's the eviction policy behind CPU caches, page caches, web and CDN caches,
database buffer pools, and application caches everywhere, because it captures a simple truth about
access patterns: recently-used data tends to be used again soon (temporal locality), so the thing
untouched the longest is the safest to discard.

The interesting part is the engineering. A cache needs two O(1) operations at once: look up a key
instantly, AND update its recency instantly (mark it most-recently-used on every access, and find
the least-recently-used to evict). No single structure gives both — a hash map has O(1) lookup but
no order, a linked list has O(1) reordering but no fast lookup. The classic answer COMBINES them: a
hash map from key to a node, plus a doubly-linked list that keeps the nodes in recency order
(most-recent at the front, least-recent at the back). The hash map finds any node in O(1); the
doubly-linked list moves a node to the front or drops the back node in O(1). Together they are
exactly the interface a cache needs — two simple structures composing into one that neither could
be alone.
"""


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

    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


# region: lru
class LRUCache:
    """Capacity-bounded LRU cache. `store` maps key → node for O(1) lookup; a doubly-linked list
    with head/tail sentinels keeps nodes in recency order — front (head.next) is most-recently-used,
    back (tail.prev) is least-recently-used and the eviction victim."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.head = _Node()                       # sentinel: MRU side
        self.tail = _Node()                       # sentinel: LRU side
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _push_front(self, node):
        node.next = self.head.next                # splice just after the head sentinel (MRU)
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        """Return the value and mark the key most-recently-used (move its node to the front). Returns
        None on a miss. O(1): a dict lookup plus two pointer splices."""
        node = self.store.get(key)
        if node is None:
            return None                           # miss
        self._unlink(node)
        self._push_front(node)                    # touch → becomes most recently used
        return node.val

    def put(self, key, val):
        """Insert or update a key as most-recently-used. If the cache is full and the key is new,
        evict the least-recently-used node (the one just before the tail sentinel) first. O(1)."""
        node = self.store.get(key)
        if node is not None:
            node.val = val
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.store) >= self.capacity:
            lru = self.tail.prev                  # the least-recently-used node
            self._unlink(lru)
            del self.store[lru.key]               # evict it
        node = _Node(key, val)
        self.store[key] = node
        self._push_front(node)

    def order(self):
        """The keys from most- to least-recently-used — for inspection and the animation."""
        out, cur = [], self.head.next
        while cur is not self.tail:
            out.append(cur.key)
            cur = cur.next
        return out
# endregion

"""The library way and the policy contrasts. Three things:

- `OrderedDictLRU` is the standard-library way to write an LRU cache — `collections.OrderedDict`
  keeps insertion order and `move_to_end` / `popitem` give O(1) recency updates and eviction, so
  it's the same algorithm as impl.py's hash-map-plus-linked-list, just using a battery-included
  structure. It's the correctness reference. (Python's `functools.lru_cache` decorator memoizes
  function calls with exactly this policy.)
- `FIFOCache` and `RandomCache` are the OTHER eviction policies, for the hit-rate face-off: FIFO
  evicts the oldest-inserted item regardless of use, and Random evicts an arbitrary one. Comparing
  their hit rates against LRU shows WHY recency-based eviction is worth the extra bookkeeping.
"""
import random
from collections import OrderedDict


# region: ordereddict
class OrderedDictLRU:
    """An LRU cache in a few lines using collections.OrderedDict — the standard-library approach, and
    the correctness reference for the hand-built hash-map + doubly-linked-list version."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)                # mark most-recently-used
        return self.data[key]

    def put(self, key, val):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = val
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)         # evict least-recently-used (front)
# endregion


# region: policies
class FIFOCache:
    """Evicts the OLDEST-INSERTED item, ignoring how recently it was used — no recency tracking."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        return self.data.get(key)                 # a hit does NOT change eviction order

    def put(self, key, val):
        if key not in self.data and len(self.data) >= self.capacity:
            self.data.popitem(last=False)         # evict the oldest inserted
        self.data[key] = val


class RandomCache:
    """Evicts a RANDOM item when full — the simplest policy, no order at all."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}

    def get(self, key):
        return self.data.get(key)

    def put(self, key, val):
        if key not in self.data and len(self.data) >= self.capacity:
            del self.data[random.choice(list(self.data))]
        self.data[key] = val
# endregion

Scratch vs library

The LRU cache is the book's cleanest lesson in composition: a requirement that no single data structure satisfies, met by combining two that each satisfy half of it, sharing nodes so an update touches both views at once. That pattern — hash map for random access, linked structure for order — is worth recognizing because it recurs whenever you need two fast operations that pull in different directions. It also shows that the "battery-included" version (OrderedDict, functools.lru_cache) isn't magic: OrderedDict is a hash map plus a doubly-linked list under the hood, which is why building the cache by hand demystifies the library. And the face-off surfaces the why behind the ubiquitous policy — LRU beats FIFO and random on locality-rich workloads because recency predicts reuse, which is the same temporal-locality assumption that justifies caches existing at all. In production you'd use functools.lru_cache for memoization or a database's buffer manager for storage; building the structure yourself is what makes "hash map plus doubly-linked list equals O(1) cache" a composition you've assembled rather than a recipe you've memorized.

Where you'll actually meet it

LRU caches are everywhere in the memory hierarchy and beyond. CPU caches (L1/L2/L3) use LRU approximations in hardware to decide which cache lines to evict. Operating systems use LRU-family policies for page replacement in virtual memory and for the file-system page cache. Databases use it (and scan-resistant variants like ARC in PostgreSQL's descendants and 2Q) for buffer pools that cache disk pages, one of the biggest performance levers in a DBMS. Web browsers, CDNs (Cloudflare, Akamai), and reverse proxies (Varnish, nginx) cache content with LRU variants. Application caches (Redis with allkeys-lru, Memcached, Guava, Caffeine) offer LRU eviction. Memoization decorators (functools.lru_cache) cache function results with it. DNS resolvers, ORM query caches, and image/thumbnail caches all use it. And it's a perennial interview question because implementing it correctly tests the composition insight. Anywhere a bounded cache must decide what to keep, an LRU or its variant is very likely the policy.

Takeaways

An LRU cache evicts the least-recently-used item when full, and its efficient implementation composes a hash map (O(1) lookup by key) with a doubly-linked list (O(1) recency ordering, front = most recent, back = least), sharing nodes so get, put, and eviction are all O(1). The doubly-linked list is essential — it's what allows O(1) removal of a node from the middle. LRU beats FIFO and random on locality-rich workloads (a 6-point hit-rate edge here, larger with stronger locality) because recency predicts reuse, though it's vulnerable to scan-induced pollution, which production variants (ARC, 2Q, LRU-K) defend against. It's the canonical example of composing two structures to meet a two-part requirement.

The next chapter moves from one-dimensional keys to space. A k-d tree organizes points in multiple dimensions so that "which stored point is nearest to this query?" and "which points fall in this region?" can be answered far faster than checking every point — the structure behind nearest-neighbor search, spatial databases, and the geometry underlying much of machine learning. It's a binary search tree generalized to k dimensions, splitting space one axis at a time, and it shows both the power and the eventual limits of spatial partitioning as dimensions grow.