LRU Cache Design

Description

An LRU (least recently used) cache keeps a fixed number of entries and, when it's full, throws away the one that hasn't been used for the longest time. It's the most common eviction policy - in-process caches, database buffer pools and CDN edges all use it or a close relative - and "design an LRU cache with O(1) operations" is one of the most frequent object-oriented design interview questions. This skill covers the classic hash map plus doubly linked list design, the library shortcuts, and the bugs to avoid.

A cache with no eviction strategy either grows without bound, or evicts using a scan that gets slower exactly as the cache gets more useful:

class NaiveLRUCache {
    private Map<Integer, Integer> map = new HashMap<>();
    private List<Integer> usageOrder = new ArrayList<>();
    private int capacity;

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        usageOrder.remove((Integer) key);   // O(n) - scans the whole list to find key
        usageOrder.add(key);
        return map.get(key);
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            usageOrder.remove((Integer) key);   // O(n) again
        } else if (map.size() == capacity) {
            int oldest = usageOrder.remove(0);    // O(n) - shifts every remaining element down
            map.remove(oldest);
        }
        map.put(key, value);
        usageOrder.add(key);
    }
}

class NaiveLRUCache:
    def __init__(self, capacity: int):
        self._map: dict[int, int] = {}
        self._usage_order: list[int] = []
        self._capacity = capacity

    def get(self, key: int) -> int:
        if key not in self._map:
            return -1
        self._usage_order.remove(key)           # O(n) - scans the whole list to find key
        self._usage_order.append(key)
        return self._map[key]

    def put(self, key: int, value: int) -> None:
        if key in self._map:
            self._usage_order.remove(key)       # O(n) again
        elif len(self._map) == self._capacity:
            oldest = self._usage_order.pop(0)   # O(n) - shifts every remaining element down
            del self._map[oldest]
        self._map[key] = value
        self._usage_order.append(key)

At a handful of entries this is invisible. Under real load - thousands of get/put calls per second against a cache holding thousands of entries - every single operation re-scans (and often re-shifts) the entire usage-order list, and the cache's own bookkeeping becomes slower than just not caching at all.

We'll go from simple to more technical:

1. The design: a hash map for lookup, a doubly linked list for recency.
2. The two list operations every method uses, with sentinel nodes.
3. The library versions: LinkedHashMap, OrderedDict and functools.lru_cache.
4. The bugs that break it, and what changes with threads.

The pattern

Keep a doubly linked list ordered from most-recently-used (right after a dummy head) to least-recently-used (right before a dummy tail), plus a HashMap<Integer, Node> for O(1) key lookup into that list.

get(key):
    if key is not in the map: return -1
    unlink its node, re-insert it right after head
    return its value

put(key, value):
    if key is in the map:
        update its node's value, then unlink it and re-insert it right after head
    else:
        create a node, insert it right after head, add it to the map
        if the cache is now over capacity:
            remove the node just before tail, and its map entry

Dummy head/tail sentinel nodes (rather than tracking null specially) are what keep the insert/remove code free of edge-case branches for "list is empty" or "removing the only node."

The pieces in code

With sentinels, the two list operations every method needs are a few lines each, with no null checks anywhere:

private void remove(Node n) {            // unlink n from wherever it is
    n.prev.next = n.next;
    n.next.prev = n.prev;
}

private void insertFront(Node n) {       // link n in right after head (most recent)
    n.next = head.next;
    n.prev = head;
    head.next.prev = n;
    head.next = n;
}

def _remove(self, n: Node) -> None:          # unlink n from wherever it is
    n.prev.next = n.next
    n.next.prev = n.prev

def _insert_front(self, n: Node) -> None:    # link n in right after head (most recent)
    n.next = self._head.next
    n.prev = self._head
    self._head.next.prev = n
    self._head.next = n

get is a lookup plus remove plus insertFront; eviction is remove(tail.prev) plus deleting that key from the map - which is why each node stores its own key.

In production Java you rarely write this by hand: LinkedHashMap already threads a doubly linked list through its entries. Python's twin is collections.OrderedDict: move_to_end(key) marks a key as the newest and popitem(last=False) evicts the oldest - and @functools.lru_cache(maxsize=...) wraps a whole function in an LRU cache.

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }   // true = access order
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;                                                  // checked after each put
    }
}

from collections import OrderedDict


class LruCache:
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._data: OrderedDict[int, int] = OrderedDict()   # oldest first, newest last

    def get(self, key: int) -> int:
        if key not in self._data:
            return -1
        self._data.move_to_end(key)                         # a read makes it the newest
        return self._data[key]

    def put(self, key: int, value: int) -> None:
        self._data[key] = value
        self._data.move_to_end(key)                         # an update must move it too
        if len(self._data) > self._capacity:
            self._data.popitem(last=False)                  # evict the oldest

Without the true flag the map keeps insertion order and this becomes a FIFO cache; with size() >= capacity it quietly holds one entry fewer than intended.

The Python trap is the mirror image: a plain dict remembers insertion order too, but assigning to an existing key does not move it. Forget move_to_end on an update and a key that was just rewritten is still the first to be evicted.

Where you'll see it

This is the actual data structure behind an in-process LRU cache (e.g. a bounded LinkedHashMap in accessOrder mode in Java, or an application-level cache in front of a slower store like a database or a remote API) — anywhere you need to bound memory use by evicting the coldest entries first, without a full memory-usage scan on every access.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does removing the O(n) usageOrder.remove((Integer) key) scan matter in practice, if the cache never grows past a few dozen entries?

2. A get(key) is called for a key that doesn't exist in the cache. Should this affect the linked list at all?

3. Why can't a single synchronized keyword around get/put alone make this design both safe and fast for a read-heavy workload?

Key takeaways

• O(1) get/put needs both a hashmap (for lookup) and a doubly linked list (for O(1) reordering and eviction) - neither alone is enough.
• Sentinel head/tail nodes remove every "is the list empty?" special case from insert/remove.
• get must move a node to the front too, not just put - otherwise frequently-read keys look cold and get evicted.
• The map and list must be updated together on every operation, or they'll disagree about what's actually in the cache.
• This design isn't thread-safe by default; making it safe for concurrent access (synchronized, ConcurrentHashMap, ReadWriteLock) is a separate decision with its own tradeoffs.