LRU cache implementation in Python

In this article

1. Before you start
2. Why interviewers ask this
3. LRU cache from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

The LRU cache is asked because it forces two data structures to cooperate under a constant-time rule. A weak answer uses a list and scans it, which makes each operation linear. A strong answer explains why neither structure alone works, writes the pointer moves without bugs, handles the update-existing-key and full-cache cases, and then says what changes for thread safety or a frequency-based policy.

The problem appears in industry coding and low-level design rounds, usually as "implement get and put in constant time with a capacity". The industry coding hub, the coding interviews hub and the low-level design questions page list the neighbouring problems.

LRU cache from first principles

LRU cache

An LRU cache is a bounded key-value store that, when it must make room, removes the entry whose last read or write is the oldest, on the assumption that recently used keys are the ones likely to be used again.

Cache hit

A cache hit is a lookup whose key is already in the cache, so the stored value is returned without recomputing or refetching it.

Sentinel node

A sentinel node is a dummy node placed at each end of a linked list so that inserting or removing a real node never needs a special case for an empty or end position.

In plain words

Picture a desk that holds three folders. Each time you use a folder, you put it on top of the pile. A fourth folder arrives and the desk is full. You remove the folder at the bottom, the one you touched longest ago. The analogy breaks in one place. On a real desk, finding a folder in the pile takes time. The whole difficulty of the problem is finding and moving an item in constant time.

Stated precisely, the cache needs lookup by key and a total order by recency. A hash map gives the first. A doubly linked list gives the second. Each node is reachable from the map. The Python documentation states the policy: an LRU cache "works best when the most recent calls are the best predictors of upcoming calls" (Python 3.15 documentation, functools, October 2026).

Step 1: Choose a hash map and a doubly linked list

The first step picks the structures. The input is the requirement of constant-time get and put; the output is a design with two parts. A dictionary, Python's hash map, maps each key to its list node, so a lookup is one step. A doubly linked list holds the nodes in recency order, most recent next to the head, least recent next to the tail.

The list must be doubly linked because removing a node from the middle needs its predecessor, and the map hands you the node, not its predecessor. (A pointer is a node's reference to its neighbour; a pointer write changes one.) Two sentinel nodes at the ends remove edge cases. What you now know: the map finds, the list orders.

Text description of the diagram

• The hash map maps each key to its node.
• Each node links to both neighbours, so it can be unlinked in two writes.
• The most recent node sits next to the head and the least recent next to the tail.

Step 2: Refresh the entry on every get

The second step implements get. The input is a key; the output is its value, or minus one on a miss. On a hit the node is unlinked from where it is and pushed to the front, because reading an entry makes it the most recently used. Unlinking is two pointer writes and pushing to the front is four, so a hit costs six writes and one dictionary lookup, all constant.

Skipping the refresh is the classic bug: the cache then evicts by the order of the last put, which for keys that are never updated is first-in first-out, and the worked example shows the wrong answer it gives. A miss changes nothing. What you now know: a read is also a use.

Step 3: Insert or update on put

The third step implements put. The input is a key and a value; the output is the changed cache. If the key exists, update the node's value and refresh it as in step two, rather than adding a second node. If it does not, create a node, store it in the map and push it to the front. The update path matters because a duplicate node would leave a stale entry in the list that the map no longer points to, and a later eviction would delete the wrong key. A put never returns a value, so the function returns nothing. What you now know: an existing key is updated, not duplicated.

Step 4: Evict from the back when full

The fourth step handles capacity. The input is a put of a new key into a full cache; the output is the cache with one entry removed first. The least recently used node is the one just before the tail sentinel. Unlink it and delete its key from the map, using the key stored inside the node, then insert the new entry. Storing the key in each node is what makes this step constant: without it you could not find the map entry to delete. Do the eviction before the insert so the size never exceeds the capacity. What you now know: the node before the tail is always the eviction candidate.

1 · Structures2 · Get3 · Put4 · EvictReplay

Step-by-step description

1. Map finds, list orders.
2. Unlink and push to the front.
3. Update or insert at the front.
4. Remove the node before the tail.

• Choose a hash map and a doubly linked list.
• Refresh the entry on every get.
• Evict the node before the tail when the cache is full.

Worked example

The class below is the full solution, run in assets/data/lru-cache.py. The explanation of each part is in the four steps above, so the code carries only short comments.¹

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value, self.prev, self.next = key, value, None, None

class LRUCache:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        self.capacity = capacity
        self.map = {}                                  # key -> node
        self.head, self.tail = Node(), Node()          # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

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

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

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)                             # a hit makes the key most recent
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.map.get(key)
        if node is not None:                           # update in place and refresh
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.capacity:             # evict the node before the tail
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

Now trace a capacity of 3. After put(1), put(2) and put(3) the order, most recent first, is 3, 2, 1. get(1) returns its value and moves key 1 to the front, giving 1, 3, 2. put(4) finds the cache full, evicts key 2 from the back and gives 4, 1, 3. So get(2) returns minus one. get(3) hits and gives 3, 4, 1.

put(5) evicts key 1 and gives 5, 3, 4, so the final get(1) is a miss.¹ Each eviction removed the key at the back, which was the one touched longest ago. Remove the refresh from get and the same nine operations go wrong at put(4): it evicts key 1, which was just read, instead of key 2, so get(2) returns b where the specification expects minus one.¹

1 · Fill2 · Get 13 · Put 44 · Get 25 · Get 36 · Put 5Replay

Step-by-step description

1. Most recent first.
2. A hit moves 1 to the front.
3. Full: evict 2 from the back.
4. Key 2 was evicted.
5. A hit moves 3 to the front.
6. Full: evict 1 from the back.

• After put 1, 2 and 3 the order is 3, 2, 1.
• put 5 evicts key 1 and gives the order 5, 3, 4.

The refresh rule changes the result. On an illustrative access trace of 12 keys with a capacity of 3, LRU gets 5 hits and first-in first-out gets 4, because first-in first-out never promotes a re-used key. On a cyclic scan that visits four keys in turn, 20 accesses with a capacity of 3, both policies get 0 hits. Neither policy wins on every trace: on the nine-operation trace above, the version without the refresh answers three of the four gets and LRU two, so the refresh is what the specification requires, and LRU pays off only when recently used keys come back.¹

Text description of the diagram

• On the 12-access trace LRU has 5 hits and first-in first-out has 4.
• On the cyclic scan both policies have 0 hits.

Trade-offs and edge cases

Complexity is constant expected time for get and put, and linear space in the capacity. The word expected matters: a hash map is constant on average, and a pathological set of colliding keys can degrade a lookup. Python's built-in tools do the same job more briefly. The OrderedDict documentation says its algorithm "can handle frequent reordering operations better than dict", and that this "makes it suitable for implementing various kinds of LRU caches" (Python 3.15 documentation, collections, October 2026); a reference built from move_to_end and popitem(last=False) is what the random check above compared against.

The decorator functools.lru_cache defaults to a maxsize of 128, requires hashable arguments (usable as a dictionary key), and is described as threadsafe in the sense that its data structure stays coherent, though the wrapped function can still run more than once for the same arguments (Python documentation, functools).

Interviews often ban the built-ins, because using OrderedDict skips the point. Thread safety is the second edge: this class is not safe to share across threads, and the simplest fix is one lock around get and put. A sequential scan is the third: a scan over more keys than the cache holds evicts every useful entry, as the cyclic trace showed, so a cache that must survive scans needs a policy that is not plain LRU. The wider design view is in design a distributed cache, and the idea of caching in model serving is in the key-value (KV) cache page.

How to answer it in an interview

The spoken structure is: name the two structures, say what each does, walk get and put, then give the eviction detail and the caveat.

Common mistakes

1. Using a list and scanning. (wrong) "Keep a list and move the item to the end." (right) "A scan is linear; the map gives the node directly, and the linked list moves it in constant time."
2. Not refreshing on get. (wrong) "Only put changes the order." (right) "A read is a use, so get moves the key to the front."
3. Adding a duplicate on put. (wrong) "Always create a new node." (right) "If the key exists, update its value and refresh the existing node."
4. Forgetting the key inside the node. (wrong) "Evict the tail node." (right) "Store the key in the node so eviction can delete the map entry."
5. Singly linked list. (wrong) "A next pointer is enough." (right) "With the map holding the node, removing it needs its predecessor, so each node needs a prev pointer."

Follow-up questions

How do you implement an LRU cache in Python?

Use the hash map and doubly linked list above for an interview, or OrderedDict with move_to_end on every hit and popitem(last=False) when over capacity for production code (Python documentation, collections). For caching function results, functools.lru_cache is the standard tool.

How would you extend it to an LFU cache?

A least frequently used (LFU) cache evicts the key with the fewest accesses. Matani, Shah and Mitra give an algorithm that does insertion, access and eviction in constant time, noting that LFU is used less than LRU largely because it was seen as taking O(log n) (Matani et al., 2021). The usual design keeps a map from key to value and count, a map from each count to the keys with that count in recency order (an OrderedDict works), and the current minimum count; an access moves the key from count c to c + 1, and an eviction removes the least recently used key at the minimum count, so ties go to LRU. Related practice is in coding interviews.

Can you use OrderedDict or functools.lru_cache instead?

In production, yes, and they are shorter. In an interview, ask first, because the point of the exercise is the data structure. lru_cache caches function calls, not an arbitrary key-value store with your own put.

How do you make it thread safe?

Wrap get and put in one lock, because each does several pointer writes that must not interleave; a read-write lock does not help, because get also writes. To cut contention, split the cache into shards by a hash of the key, each with its own lock, at the cost of a recency order kept per shard rather than for the whole cache. The concurrency interview questions page covers locks, races and deadlock.

Why a doubly linked list and not a singly linked list?

Because unlinking a node needs its predecessor, and in a singly linked list finding the predecessor is a linear walk. The doubly linked version removes a node in two writes. A singly linked list can work if the map stores each key's predecessor instead of its node, at the cost of updating the next key's map entry on every move. The Python interview questions page covers the language side.

Sources

1. functools - Higher-order functions and operations on callable objects (lru_cache) — Python Software Foundation, Python 3.15 documentation (last updated 2026-10-24), 24 Oct 2026
2. collections - Container datatypes (OrderedDict) — Python Software Foundation, Python 3.15 documentation (last updated 2026-10-24), 24 Oct 2026
3. An O(1) algorithm for implementing the LFU cache eviction scheme — arXiv (Matani, Shah and Mitra), v1, 22 Oct 2021