LRU Cache

LRU Cache is the classic "design a data structure" interview question. It looks intimidating, but it is really two familiar tools — a hash map and a doubly linked list — clicked together so that every operation is O(1).

The slow way first

You could store everything in a plain list and, on each access, scan the list to find the item and move it to the front. Finding and reordering is O(n) per operation — and the whole point of a cache is to be fast. We need every operation in O(1).

The question to ask: what two things do I need to do instantly? (1) Find a key's value, and (2) know which item is the least-recently-used so I can evict it. A hash map nails the first; an ordered linked list nails the second.

The idea: hash map + doubly linked list

Keep a doubly linked list of nodes ordered from most-recently-used (front) to least-recently-used (tail). Keep a hash map from each key to its node.

• get(key): look the node up in the map (O(1)), then move it to the front because we just used it.
• put(key, value): insert (or update) at the front. If that pushes size past capacity, drop the tail — the least-recently-used node — and delete it from the map too.

Because the map gives instant lookup and the linked list lets us splice a node out and re-link it in O(1), nothing ever requires a scan.

In Python you get both for free from OrderedDict: it is a dict (O(1) lookup) that also remembers insertion order, with move_to_end and popitem(last=False) doing the linked-list splicing for you.

Walk through it

Step through the animation. The list runs front (MRU) on the left to tail (LRU) on the right, and the map panel shows the keys below. Watch put(1,1) and put(2,2) fill the cache; get(1) promotes 1 to the front so 2 becomes the LRU; then put(3,3) overflows and the tail 2 is evicted — so the final get(2) misses and returns -1.

Pseudocode

map: key -> node          # O(1) lookup
list: doubly linked, front = most recent, tail = least recent
 
get(key):
    if key not in map: return -1
    move node to front          # just used it
    return its value
 
put(key, value):
    if key in map: move node to front and update value
    else: insert new node at front, add to map
    if size > capacity:
        remove tail node from list AND from map   # evict LRU

The Python solution

from collections import OrderedDict
 
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()
 
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
 
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

• OrderedDict is a dict that remembers order — it is the hash map plus the linked list in one object.
• move_to_end(key) (line 11) splices a node to the back of the order, which we treat as most-recently-used, in O(1).
• On put, we set the value then check len > cap; popitem(last=False) (line 19) removes the oldest entry — the LRU — and returns it, in O(1).
• The order convention (front vs back) is arbitrary as long as you are consistent. Here "end" = most recent, so we evict from the front with last=False.

Complexity

Every operation is constant time, and the cache never holds more than capacity entries, so space is O(capacity). The whole trick is pairing two structures so each covers the other's weakness: the map can't track recency, and the list can't look up by key.

When this pattern shows up

Practice