LRU Cache — build the one behind functools.lru_cache

An LRU (least recently used) cache holds a fixed number of key–value pairs and, when it runs out of room, evicts the entry that has gone unused the longest. Building one from scratch is LeetCode 146, and it remains one of the most reliably asked medium interview questions because it tests two skills at once: composing data structures, and rewiring pointers without breaking anything. This tutorial implements a working LRU cache twice — first with collections.OrderedDict in about fifteen lines, then from first principles with a hash map and a doubly-linked list, which is the version interviewers actually want to see. Every snippet is complete and runnable in plain Python.

What LRU eviction is, and where it runs in production

Any cache with bounded memory needs an eviction policy: when the cache is full and a new item arrives, something has to go. LRU evicts the item that was accessed longest ago. The bet behind it is temporal locality — things used recently tend to be used again soon, so the least recently used entry is the safest one to sacrifice.

That bet pays off often enough that LRU (or an approximation of it) is everywhere. CPU caches use pseudo-LRU replacement within cache sets. Redis offers maxmemory-policy allkeys-lru and volatile-lru, which approximate LRU by sampling a handful of keys rather than tracking exact order, because exact tracking costs memory. CDN edge nodes and operating system page caches lean on the same idea. When an interviewer asks you to build one, they are asking about a mechanism you will genuinely meet in production systems.

The interview contract

The canonical problem statement (LeetCode 146) fixes the API:

• LRUCache(capacity) — construct with a positive capacity.
• get(key) — return the value if the key exists, otherwise -1. This counts as a use: the key becomes the most recently used.
• put(key, value) — insert the pair, or update the value if the key exists. This also counts as a use. If inserting a new key pushes the cache over capacity, evict the least recently used key first.
• Both operations must run in O(1) average time.

The two bolded clauses are where most bugs live. A cache that only tracks insertion recency, not access recency, will pass a surprising number of casual tests and still be wrong.

Why a plain dict is not enough

A tempting first answer is "Python dicts are ordered, so just use a dict". Since Python 3.7, dicts do preserve insertion order — but insertion order is not recency order, and the gap between the two is exactly the problem.

Two things break the naive approach. First, get does not move a key: reading d[k] leaves k wherever it was, so a key you hit constantly can still sit at the "oldest" end. Second, assigning to an existing key updates the value in place — the key keeps its original position rather than jumping to the fresh end.

What is missing, then, is not ordering but two operations on top of it: promote this key to most-recent on every access, and pop the oldest key cheaply. You can fake both on a plain dict — delete and reinsert to promote, next(iter(d)) to find the oldest — but at that point you are hand-rolling OrderedDict, which ships those exact operations with clear names.

Solution 1: OrderedDict

collections.OrderedDict keeps its entries in a doubly-linked list internally, which is why move_to_end and popitem are O(1). That gives a short, correct implementation:

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)      # this access counts as a use
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)  # updating counts as a use too
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # pop the least recently used

The convention here is that the right end of the OrderedDict is most recent and the left end is least recent. move_to_end(key) promotes on every access, and popitem(last=False) pops from the left — the LRU entry. Note the order inside put: move the key first if it exists, assign, then check the length. Checking len > capacity after insertion means an update to an existing key can never trigger a spurious eviction, because updates do not grow the dict.

Walking through a sequence

Take capacity = 2 and read each state left to right, least recent to most recent:

1. put(1, 1) → [1]
2. put(2, 2) → [1, 2]
3. get(1) returns 1 → order becomes [2, 1] (key 1 was just used)
4. put(3, 3) → over capacity, evict key 2 (leftmost) → [1, 3]
5. get(2) returns -1 — key 2 is gone
6. put(4, 4) → evict key 1 → [3, 4]
7. get(1) returns -1, get(3) returns 3, get(4) returns 4

Step 3 is the one to internalise: without the move_to_end in get, step 4 would have evicted key 1 instead of key 2, and steps 5–7 would return the wrong values. You can paste any snippet on this page into the free browser editor and run it — it is real CPython, no installs.

Solution 2: hash map + doubly-linked list

The OrderedDict version is legitimate production Python, but in an interview it can read as "I used the thing I was asked to build". Interviewers push for the manual version because it proves you understand why the operations are O(1): a hash map gives O(1) lookup from key to node, and a doubly-linked list gives O(1) unlink and O(1) insert-at-front once you hold a node reference. Neither structure can do the job alone; the composition is the answer.

Start with the node. It must store the key, not just the value — on eviction you reach the LRU node through the list, and you need its key to delete the matching hash map entry:

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

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

Next, the sentinel trick. Instead of letting head and tail point at real nodes (and being None when the cache is empty), create two permanent dummy nodes and link them together. Every real node then always has a real prev and a real next, so removing the first node, the last node, or the only node are all the same operation. No None checks, no special cases — this single decision removes most of the edge-case bugs in the problem.

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}              # key -> Node
        self.head = Node()           # sentinel: most-recent side
        self.tail = Node()           # sentinel: least-recent side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """Unlink a node from the list. O(1)."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        """Insert a node right after head (most recent). O(1)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)           # accessing = using:
        self._add_to_front(node)     # promote to most recent
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value       # update the value...
            self._remove(node)       # ...and refresh recency
            self._add_to_front(node)
            return
        if len(self.cache) == self.capacity:
            lru = self.tail.prev     # real LRU node, thanks to sentinels
            self._remove(lru)
            del self.cache[lru.key]  # this is why Node stores its key
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)

A few things worth saying out loud in an interview. The list order encodes recency: nodes near head are fresh, nodes near tail are stale, and the eviction victim is always self.tail.prev. The two helpers, _remove and _add_to_front, are the whole pointer surface — get them right once and get and put become plain bookkeeping. And notice the eviction branch checks == capacity before inserting a new key, the mirror image of the OrderedDict version's check-after-insert; either convention works, but mixing them does not.

Complexity of both solutions

Both implementations meet the contract. get is a dict lookup plus a constant number of pointer assignments; put is the same plus at most one eviction, which is itself constant work. That is O(1) average time per operation (dict operations are amortised O(1); the pathological hash-collision worst case is not something interviewers expect you to litigate, though mentioning it shows awareness). Space is O(capacity): one dict entry and one node per stored key, and never more than capacity of them. The OrderedDict version has the same bounds because it wraps the same structure — a hash map threaded onto a doubly-linked list — just implemented in C inside the standard library.

What functools.lru_cache does differently

Python ships an LRU cache in the standard library, but it solves a narrower problem. functools.lru_cache is a decorator that memoises one function: the cache key is derived from the call arguments, entries are added only when the function is called, and there is no put — you can never insert or update a value directly. It also adds thread-safety locking and cache_info() statistics. What we built here is a general cache object: you choose the keys, you control insertion and updates, and you can hold one instance shared across unrelated code. If all you want is to speed up a function you own, the decorator is the right tool, and we cover it in depth in functools.lru_cache explained. In an interview, though, answering "implement an LRU cache" with @lru_cache will be read as dodging the question — mention it exists, then build the real thing.

Common mistakes

These four account for most failed submissions and most failed whiteboard rounds:

1. Forgetting to promote on get. If get returns the value without moving the node (or without move_to_end), the cache degrades to FIFO eviction. It passes short tests and fails any sequence where a hot key is read repeatedly — exactly step 3 of the walkthrough above.
2. Updating a value without refreshing recency. put on an existing key must both overwrite the value and move the node to the front. Doing only the first leaves a freshly-written key eligible for immediate eviction.
3. Off-by-one on the capacity check. Check len == capacity before inserting, or len > capacity after inserting — commit to one. Doing both evicts an extra entry; checking >= capacity after an insert-or-update path can evict on a simple value update, which grows nothing.
4. Losing pointer order when unlinking. In _remove, rewire the neighbours (node.prev.next and node.next.prev) using the node's still-intact pointers; in _add_to_front, set the new node's prev and next before touching head.next. Overwrite head.next first and you have lost your only reference to the old front node, and the list silently splits.

Test it end to end

This snippet exercises the exact sequence from the walkthrough. It runs unchanged against either class above — paste one of them directly above it:

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # 1
cache.put(3, 3)       # evicts key 2
print(cache.get(2))   # -1
cache.put(4, 4)       # evicts key 1
print(cache.get(1))   # -1
print(cache.get(3))   # 3
print(cache.get(4))   # 4

print("expected: 1 -1 -1 3 4")

Expected output:

1
-1
-1
3
4
expected: 1 -1 -1 3 4

If your version prints anything else, the walkthrough section tells you which access mutated the order at each step — diff your cache's internal order against it after each call.

Where to go next

Reading an implementation and writing one under time pressure are different skills. The interactive lesson at the top of this page (Pro) has graded exercises for this exact topic — you implement each piece against hidden test sequences, in real CPython running in your browser. If you are new to the platform, the first lessons of the track are free and take a few minutes each. Either way, write the doubly-linked list version from a blank file at least once before your interview; the sentinel trick only becomes automatic after you have typed it.