The LRU cache idea in Python

Why it matters

A cache is a small, fast store that keeps recent answers so the program does not have to compute or fetch them again. Your web browser caches images, a database keeps hot rows in memory, and a phone keeps recently used apps ready to open. The question every cache must answer is simple: when the store is full and a new item arrives, which old item should leave?

The LRU policy has a clear answer. It removes the item that was used least recently. LRU caches are a favourite interview design question because the naive versions are slow, and the fast version needs two data structures working together in a precise way. This lesson builds that version from first principles. You will see why a dict alone is not enough, why a linked list alone is not enough, and how the two fit. Then you will see the shortcuts Python gives you, and when each one is good enough.

The problem in plain words

Imagine a desk with room for three books. You are reading several books at once. When you pick up a book you have not used in a while, you put it on the desk. When the desk is full and you want a fourth book, you must put one back. A sensible rule is to put back the book you have not touched for the longest time. That is the LRU rule: least recently used.

Turn the desk into a cache with a fixed capacity. The cache has two operations, and both must run in O(1) time, which means the cost does not grow with the number of items.

• get(key) returns the value for the key, or -1 if the key is missing. A successful get counts as a use, so the key becomes the most recently used. The -1 is the rule for this lesson. Python code often returns None instead, and you can make that choice in your own cache.
• put(key, value) stores the pair. If the key already exists, it updates the value and counts as a use. If the key is new and the cache is full, it first removes the least recently used key, then stores the new pair as the most recent.

A concrete run makes the rule clear. Use a cache with capacity 2.

put(1, 10)    cache holds 1 (oldest) and nothing else
put(2, 20)    cache holds 1, 2   (2 is the most recent)
get(1)        returns 10, and 1 becomes the most recent, so 2 is now the oldest
put(3, 30)    the cache is full, so remove the oldest, key 2, then add 3
get(2)        returns -1, because 2 was removed

The key question is the one in the get(1) line. A cache that only remembers insertion order would evict key 1 at the put(3, 30) step, because 1 was inserted first. But key 1 was used more recently than key 2, so LRU evicts key 2. Keeping track of use, not insertion, is the whole difference.

Why one structure is not enough

Start with the requirements. You need to find a key quickly, and you need to know which key is the least recently used. Those two needs point to two different structures.

A dict finds a key in average O(1) time. But it knows nothing about recency. It can tell you the value for 1, but it cannot tell you whether 1 is older than 2. You would have to scan every entry to find the oldest one, which is O(n).

A list can keep the keys in order of use. The front holds the most recent key and the back holds the least recent. Finding the least recent key is O(1), because it is at the back. But finding a particular key in the list is O(n), because you must walk the list to find it. And moving a key to the front needs its neighbours, which you cannot reach without walking.

The solution combines them. Use the dict to find a key's position in the list in O(1). Use a list, specifically a doubly linked list, to keep the order of use and to move any node in O(1). The dict gives you the node. The list gives you the order.

The doubly linked list

A linked list is a chain of nodes. Each node holds a value and a link to the next node. A doubly linked list gives each node two links: one to the previous node and one to the next. With both links, you can remove a node from the middle in constant time, because you can reach both neighbours directly and join them to each other.

The cache list runs from most recent at the front to least recent at the back. Each node holds a key and a value, because the eviction step needs the key to remove the entry from the dict.

front (most recent)                  back (least recent)
  head <-> [C] <-> [A] <-> [B] <-> tail
dict: A -> node A,  B -> node B,  C -> node C

Two details make the code much simpler. The first is the dummy head and dummy tail nodes. They are placeholder nodes that hold no real data. They sit at the two ends of the list, so every real node always has a neighbour on each side. You never have to check whether the list is empty or whether a node is at an end. The second detail is that the dict holds nodes, not values. Once the dict gives you a node, you can change its position in the list, and the dict still finds it next time.

The operations, step by step

Work through each operation with the picture above in mind.

Moving a node to the front is needed for both get and an update to an existing key. First, unlink the node from its neighbours. The previous node's next link now points to the node's next node, and the next node's prev link points back. Then link the node in between the head and the old first real node. Counting both steps, that is about six pointer writes, and the cost is constant.

get(key) asks the dict for the node. If there is no node, it returns -1. If there is one, it moves the node to the front, because this is a use, and returns its value. The dict is not changed, because the node object is the same. Only its links change.

put(key, value) has three cases. If the key exists, update the node's value and move the node to the front. If the key is new and the cache has room, create a node, add it to the dict, and place it at the front. If the key is new and the cache is full, take the node just before the dummy tail, which is the least recently used. Unlink it, remove its key from the dict, and then add the new node at the front. The removal from the dict uses the key stored in the node, which is why the node needs a key field.

Trace a put on a full cache of capacity 2 that holds C at the front and A behind it. The list is head <-> C <-> A <-> tail. Now call put(D, 40). The cache is full, so the least recent node is the one before the tail, which is A. Unlink A, remove A from the dict, and create a node for D. Add D at the front. The list becomes head <-> D <-> C <-> tail, and the dict holds C and D.

Each step touches a fixed number of pointers and one dict entry, so every operation is O(1). There is no loop over the cache. That is the reason this design is fast.

Step through the visualizer above and follow the links as nodes move. Watch what happens to the neighbours of a node when you remove it from the middle. Then watch the node that moves to the front, and check that the back of the list is always the node that will be evicted next. If you can say, for any moment, which node would be removed by the next put, you understand the structure.

A hand-built LRU cache

The program below is a complete LRU cache with the dict and the doubly linked list. It has the two operations, the dummy nodes and a method that prints the order from most to least recent. The code at the bottom runs a sequence of calls and prints each result, so you can trace it against the rules above.

get 1 -> 10
get 2 -> -1
get 1 -> -1
get 3 -> 30
get 4 -> 40
order (most recent first): [4=40, 3=30]

Trace the list after each call. Start with put(1, 10): the list is head <-> 1 <-> tail. put(2, 20) adds 2 at the front, so the list is 2, 1. The cache now holds two keys and is full.

get(1) finds node 1 through the dict. It moves that node to the front, giving 1, 2, and prints 10. Node 2 is now the least recent.

put(3, 30) is a new key, and the cache is full. The least recent node is the one before the tail, which is 2. It is unlinked, removed from the dict, and node 3 goes to the front. The list is 3, 1. The line get 2 -> -1 confirms that 2 is gone.

put(4, 40) evicts the least recent node, which is now 1. The list becomes 4, 3. That is why get 1 -> -1 prints next. The two get calls after that move 3 and then 4 to the front. The final order, most recent first, is 4=40, 3=30.

The order method walks from the front to the back, which is most recent first. Keep that direction in mind, because the shortcut below keeps its oldest entry at the front.

Python details in this code: self.index.get(key) returns None for a missing key, and is None is the right check, as lesson 2 explained. del self.index[lru.key] removes the entry, and it raises KeyError if the key is not there, which would show a bug in the list and the dict falling out of step.

Why the design is O(1)

Count the work in each operation. Finding a node uses the dict, which is average O(1). Unlinking a node changes at most four pointers, because the node's two neighbours are reachable directly. Adding at the front changes a fixed number of pointers. Evicting the least recent node uses tail.prev, which is a direct reference, and removing its key from the dict is also O(1). None of these steps loops over the cache.

The space is O(capacity), because the cache holds at most capacity nodes, and each node has one dict entry. A cache of 1,000 items uses memory for about 1,000 nodes and 1,000 dict entries, plus the two dummy nodes.

Be ready to explain why a singly linked list fails. In a singly linked list each node has only a next link. To remove a node from the middle you must change the next link of the node before it, and you can reach that node only by walking from the head. That walk is O(n). The doubly linked list gives you the prev link, so the walk is never needed. This is the one detail that makes the design work, and interviewers often ask about it.

The shortcut: OrderedDict

Python has a dict subclass that already keeps its keys in order of use. It is collections.OrderedDict. It has two methods the cache needs. move_to_end(key) moves an entry to the end of the order in O(1), and popitem(last=False) removes and returns the first entry, which is the oldest. Put the most recent key at the end, and the first key is the least recent one.

In a plain dict, the order is insertion order, and there is no move_to_end. You can still move a key to the end with d[key] = d.pop(key). The next program shows that trick and also shows OrderedDict used as a cache.

The program below runs the same sequence twice. The first run moves a key on every use, which is LRU. The second run never moves a key, which is FIFO, first in and first out. The output shows that the two policies keep different keys.

use_access=True keys=['a', 'c']
use_access=False keys=['b', 'c']
plain dict move to end: ['y', 'x']

Step through the first run. After put("a") and put("b") the order is a, b. The get("a") call moves a to the end, so the order becomes b, a. Then put("c") makes the size 3, which is above the capacity of 2, so the code removes the first entry with popitem(last=False), which is b. The keys that remain are a and c.

The second run is the FIFO policy. Without the move_to_end call, get("a") does nothing, so a is still the oldest insertion, and it is the one removed. The same calls give different answers because the policy is different.

The last two lines show the dict trick. d.pop("x") removes the key and returns its value, and assigning it again puts the key at the end of the insertion order. Use OrderedDict when you want the move_to_end and popitem methods, because the code says what it means.

The OrderedDict version is short and correct, and it is what many real Python programs use. Interviewers usually want the hand-built version, because it shows you understand the two structures. Practise both, and say which one you would ship. For production code the shortcut is the better choice, because it has been tested by many people and it has fewer lines to get wrong.

Using functools.lru_cache for functions

Python has a ready-made LRU cache for a common case: remembering the answers of a function. The decorator functools.lru_cache(maxsize=...) wraps a function. When the function is called again with the same arguments, the wrapper returns the stored answer and does not run the function again. This is called memoization. The wrapper keeps the arguments as its keys, so the arguments must be hashable.

computing 2
computing 3
computing 4
4 9 4 16 4
CacheInfo(hits=2, misses=3, maxsize=2, currsize=2)

The print lines run after all five calls, because Python evaluates the arguments first. Trace the calls. square(2) is a miss, so it prints computing 2. square(3) is a miss, so it prints computing 3. square(2) is a hit, which makes 2 the most recent entry. square(4) is a miss. The cache is full, so it removes the least recent entry, which is 3, and prints computing 4. square(2) is a hit again. The totals are 2 hits and 3 misses.

Use lru_cache when you have a pure function, meaning one that gives the same answer for the same arguments and does not change anything else. A function that reads a file or the clock is not a good match, because its answer can change between calls. You cannot choose a different eviction rule with lru_cache, and you cannot inspect its order. For a cache that you must control, use the class from this lesson.

Choosing between the hand-built and the shortcut

The two versions behave the same for get and put with a fixed capacity. The differences are in what you control and how much code you write. The table below summarises them.

In an interview, build the hand-built version. Say the two structures out loud, explain why each is needed, and then write the code. If the interviewer asks for a shorter version, mention OrderedDict and show move_to_end and popitem(last=False). In a real codebase, use the shortcut, and add a test that checks the eviction order.

What happens inside

A few facts make the design easier to reason about. Each node in the hand-built cache is an object with four attributes, so each cached entry costs more memory than the key and value alone. The dict holds one entry per key, and each entry points to a node object. Two objects per cached pair is the price of constant-time operations.

OrderedDict stores the same kind of structure internally. CPython implements it in C. It keeps a hash table for lookup and a doubly linked list of keys for the order. A move_to_end call unlinks the entry and links it at the end, which is the same work as the hand-built version. The class is faster than the Python version of the hand-built cache, because the work runs in C.

The plain dict you saw in the shortcut section also keeps its entries in insertion order, but it does not have a way to move an entry in place. The pop and reinsert trick works because it removes the entry and adds it again, which costs O(1) on average.

Walk a longer trace

Two calls is not enough to be sure of the rules, so follow a longer run with capacity 3. The table lists the order of the cache after each call, most recent first. Each row says what changed, so you can check your own trace against it.

After the last call, get(C) returns 30, and get(A) returns -1. Notice the row for put(C, 30). The key already existed, so nothing was evicted, and the size stayed at 3. The row for get(B) shows a miss, which changes nothing. A miss is not a use, because there is no node to move.

Look at the two evictions. Before put(D, 4) the order was A, C, B, so B was at the back and was evicted. Before put(E, 5) the order was C, D, A, so A was at the back and was evicted, because A had not been used since the get(A) call. The eviction always takes the back of the list, and the back is always the least recently used key.

Testing the hand-built cache

A cache is easy to get almost right and hard to get fully right, so write tests before you trust one. Start with the cases in the table above, because each row is a test: a miss, an update of an existing key, an eviction after a read and an eviction after a write. Then add the edge cases from this lesson. Test a capacity of 1, where every new key evicts the only key. Test a put on an existing key when the cache is full, which must not evict. Test a long run of random operations with a fixed seed, and compare the results with a second, simple implementation, such as an OrderedDict with move_to_end. Matching results on many random runs are strong evidence that the rules are right.

One more check is useful for the list itself. Write a method that walks the list from the head to the tail and counts the real nodes, and compare that count with the length of the dict. The two must always be equal. If they differ after some call, the list and the dict have lost track of each other, and the bug is in the operation that changed one but not the other. This kind of invariant check finds bugs that a simple output test can miss.

The shortcut's limits

The OrderedDict shortcut is short, but it has limits you should know. Its eviction rule is whatever your put says. That is enough for a size limit. A rule based on time, memory or the value stored needs more code, and it is harder to see at a glance. The class is not thread-safe, so two threads that use the same cache at once need a lock around each call, or a different design.

There is also a trap with iteration. Changing an OrderedDict while you loop over it raises RuntimeError, the same as a plain dict. In a cache, get changes the order, so a loop over the keys that calls get inside it is a bug. Copy the keys into a list first if you need to look up values while you walk the keys.

Common mistakes

Using a singly linked list. Removing a node from the middle needs its previous node, and a singly linked list cannot reach it without walking from the head. That walk is O(n), and the design stops being constant time. Use a doubly linked list.

Forgetting to remove the evicted key from the dict. If you unlink the least recent node but leave its key in the dict, the next get for that key finds a node that is no longer in the list. The cache then behaves strangely. Remove the key from the dict in the same step as the unlink.

Forgetting that get counts as a use. A cache that only moves a node on put evicts items that were read recently, which is the wrong policy. Move the node on every successful get.

Not moving an existing key on put. When put updates a key that already exists, the node must also move to the front. Otherwise the cache keeps evicting it at the wrong time.

Creating a second node for an existing key. If put adds a new node for a key that is already in the dict, the old node stays in the list and the dict points to the new one. The list now holds the key twice, and the eviction count goes wrong. Check the dict first.

Forgetting move_to_end in the shortcut. Without it, the OrderedDict keeps insertion order, and the cache is FIFO, which is a different policy. The output of the two-run program above shows the difference.

Debugging walkthrough: the cache evicts the wrong key

Suppose your cache evicts a key that was used recently. The bug is almost always in the order of the list, not in the dict. Follow these steps.

1. Print the order after every call. Add a line that prints the cache's order() after each get and put. Compare each printed order with the rules: a use moves a key to the front, and an eviction removes from the back.
2. Check get. When a key is found, does the code unlink it and add it to the front? If the code returns the value before moving the node, the node stays where it was.
3. Check the eviction. The evicted node must be tail.prev, which is the least recent. If the code uses head.next by mistake, it evicts the most recent key.
4. Check the update path. When put updates an existing key, does it move the node to the front? If not, the key looks old and gets evicted early.
5. Check the dict removal. After an eviction, the key must be gone from the dict. If it is still there, get finds the old node and returns a value for a key that should be gone.

Each step checks one rule from the design. Most bugs are in the first two or three steps.

Edge cases

A capacity of 1 is a useful test. Every new key evicts the only existing key, so get after a put of a new key always returns -1 for the old key. Test it, because the dummy node logic is easy to get wrong with one node.

A put for an existing key does not change the size, so it must not evict anything. The check in the hand-built put happens after the existing-key branch, which handles this case. If you move the check to the top, you will evict an entry on every update, which is wrong.

A capacity of 0 is not a useful cache. Decide what the behaviour should be, and say so in the code. The program above rejects it in the constructor with a ValueError. The program never builds a cache of size 0, so its output does not show that message.

Interview angle: explain the two structures first

When an interviewer asks you to design an LRU cache, start by naming the requirements: fixed capacity, O(1) get and put, and eviction of the least recently used key. Then say that a dict gives O(1) lookup but no order, and a doubly linked list gives O(1) moves but slow lookup. The combination gives both.

Then draw the picture. Show the list with the dummy head and tail, the dict pointing to the nodes, and the eviction from the back. Walk through one get and one put with eviction, and say the cost of each. Only then start writing code. The drawing shows the interviewer that you have a plan, and it helps you catch mistakes early.

If time allows, mention extensions. A least frequently used cache counts uses instead of tracking recency, and it needs a different structure. A time-to-live cache removes entries after a fixed age, and it needs a clock. A thread-safe cache needs a lock around each operation. Naming these shows you understand where the design ends.

Real-world uses

Web servers cache rendered pages and database query results with an LRU policy, because recent requests are often repeated. Operating systems keep recently used disk blocks in memory. Image viewers keep decoded images for the photos you looked at last. Mobile apps keep recent network responses so the screen loads without waiting. In each case the cache is small, the lookup must be fast, and the policy must match how people use the data.

Practice

Try each exercise before you open its answer. Use paper for the traces, and check your answers with a short program.

1. Trace a capacity-2 cache with put(1), put(2), get(1), put(3), get(2). Write the order after each call. Hint: key 2 is evicted at the put(3) step.

Show the answer

After put(1) the order is 1. After put(2) it is 2, 1. After get(1) it is 1, 2. After put(3) the least recent, 2, is evicted, and the order is 3, 1. Then get(2) returns -1.

2. Why does an LRU cache need a doubly linked list and not a Python list? Hint: think about removing an item from the middle.

Show the answer

A doubly linked list lets you remove a node from the middle in constant time, because the node knows both neighbours. A Python list would need to shift every item after the removed one, which costs O(n). Removing from the end of a Python list is fast, but a cache needs to remove from the middle when a key is used.

3. What does the use_access flag change in the OrderedDict example? Hint: the program prints ['a', 'c'] with it and ['b', 'c'] without it.

Show the answer

With the flag on, get and put on an existing key call move_to_end, so the order follows use. With it off, the order follows insertion, the cache is FIFO, and it evicts the oldest insertion.

4. Write the order of the hand-built cache after put(1, 10), put(2, 20), put(1, 15), put(3, 30). Hint: an update counts as a use.

Show the answer

After put(1, 10) the order is 1. After put(2, 20) it is 2, 1. After put(1, 15) the update moves 1 to the front, giving 1, 2. After put(3, 30) the least recent, 2, is evicted, leaving 3, 1. The output is [3=30, 1=15].

5. Write a test for a capacity-1 cache that checks put, get and an update of the same key. Hint: an update must not evict.

Show the answer

2
-1 3

The update keeps the size at 1, so nothing is evicted. The new key b then evicts a.

The example uses the LruCache class from the hand-built section, so put the class above it when you run it.

6. Explain why get on a missing key must not change the list. Hint: there is no node to move.

Show the answer

A missing key has no node. The cache has nothing to move, and moving the list would change the order of other keys, which would break the LRU rule.

7. Change the OrderedDict shortcut so that put of an existing key does not count as a use, while get still does. Hint: think about what move_to_end does in put.

Show the answer

Remove the move_to_end call from the put path, and keep it in get. Then an update changes the value but leaves the key where it was. Check the result with a trace that updates the oldest key and then adds a new one.

8. Count the work for one put with an eviction in the hand-built cache. List each pointer change. Hint: there are about six.

Show the answer

Unlink the evicted node changes two pointers. Removing its key from the dict is one dict operation. Creating the node and adding it to the dict is one more dict operation. Linking the new node to the front changes four pointers. The total is about six pointer changes and two dict operations, which does not depend on the size of the cache.

9. A cache of capacity 3 receives requests a b c a d b. Predict the hits and misses. Hint: a is a hit, and d evicts b.

Show the answer

a misses and is stored. b misses. c misses, so the cache holds a, b, c. a is a hit, and the order becomes b, c, a. d misses and evicts b, leaving c, a, d. b misses and evicts c, leaving a, d, b. The result is one hit and five misses. Running the OrderedDict version of the cache on these requests gives the same totals.

10. Write the method evicted(self) for the hand-built cache. It returns the key that would be removed next, without removing it. Hint: self.tail.prev.key.

Show the answer

def evicted(self):
    if self.tail.prev is self.head:
        return None
    return self.tail.prev.key

The check for self.head handles the empty cache, where the only node before the tail is the dummy head.

What you now know

• An LRU cache removes the least recently used key when it is full, and both get and put count as a use.
• A dict gives fast lookup, and a doubly linked list gives fast reordering and eviction. The cache needs both.
• Dummy head and tail nodes remove the special cases for an empty list and for the two ends.
• Each operation touches a fixed number of pointers and dict entries, so it runs in O(1).
• OrderedDict with move_to_end and popitem(last=False) gives the same policy in about ten lines.
• functools.lru_cache is the ready-made cache for memoizing a pure function, and it does not let you control the eviction rule.
• Forgetting the move on use turns the cache into a FIFO cache, which evicts the wrong keys under real use.