~/data-structures/lru-cache

LRU cache

A fixed-size cache that throws out whatever was used longest ago. A hash map plus a doubly linked list make get and put O(1).

what

A hash map from key to node, and a doubly linked list of those nodes in order of use. The front is the most recent; evict from the back.

use when

You must keep only the N most recently used items, with constant-time lookups, inserts and evictions.

time

O(1) per get or put

space

O(capacity)

You’ll recognise it when

The problem says “design a cache” with a fixed capacity and asks for O(1) get and put.
When the cache is full, the item to throw out is the one used longest ago.
Reading an item counts as using it, so every access changes the order.
You need a hash map’s fast lookup and a queue’s sense of order, and neither alone is enough.

It’s often confused with an LFU cache, which evicts the item used the fewest times rather than the one used longest ago. The structure is similar but needs more bookkeeping (see Variations).

Think of a stack of papers on your desk. Whenever you read a sheet, you put it back on top. New sheets also go on top. When the desk is full, you throw away the sheet at the very bottom: the one nobody has touched for longest. You never sort anything; the pile’s order is the history of use.

To do that in O(1), you need two things at once. A hash map finds any key’s sheet instantly. A doubly linked list keeps the pile’s order and lets you pull a sheet out of the middle and put it on top in O(1), because each node knows both its neighbours. The map stores pointers to list nodes, so a lookup lands you right on the node you need to move.

How it works

cache maps each key to its node. The list has two dummy nodes, a sentinel head and tail, so there is always a node before and after every real one and no None checks are needed. head.next is the most recent key, tail.prev the least recent.

Scroll through the steps and the graphic follows along. It runs a cache with capacity = 3. You can also press play, step with the arrow keys, or edit the operations.

Start with an empty cache and the two sentinels pointing at each other. Every real node will be linked in between them.
put a new key: make a node holding the key and value, point cache[key] at it, and link it right after head. The newest key is the most recent.
get(key) starts with one map lookup. The map is the only way in: you never walk the list looking for a key.
A hit gives you the node directly. Unlink it by pointing its two neighbours at each other. The prev pointer is what makes this O(1).
Move it to the front by linking it back in after head, then return its value. Key 1 was the oldest key; now it’s the newest.
put when full: key 4 is new and cache already holds capacity keys, so one must go.
Evict tail.prev, the least recently used key. It’s 2, not 1: 1 was read a moment ago. Unlink the node and delete its map entry, using the key stored in the node.
A miss returns -1 and changes nothing. Key 2 was evicted, so it isn’t in cache any more.
put an existing key updates the value and counts as a use. Key 3 was next in line for eviction.
So it moves to the front too. When key 5 arrives, key 1 is evicted instead of 3.
At the end, the list order is the full story: most recent on the left, next victim on the right.

loading lru-cache…

Why it’s correct: the list always holds exactly the keys in cache, ordered by their last use. Every get hit and every put moves its key to the front, and nothing else reorders the list, so the node just before tail is always the one used longest ago. The map and list change together in every operation, so they never disagree.

class Node:
    def __init__(self, key=0, value=0):
        self.key = key            # kept so eviction can delete the map entry
        self.value = value
        self.prev = None
        self.next = None


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

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

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

    def get(self, key):
        node = self.cache.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.cache.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.cache) == self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.cache[lru.key]
        node = Node(key, value)
        self.cache[key] = node
        self._push_front(node)

#include <unordered_map>
using namespace std;

struct Node {
    int key = 0, value = 0;       // key kept so eviction can delete the map entry
    Node* prev = nullptr;
    Node* next = nullptr;
};

class LRUCache {
    int capacity;
    unordered_map<int, Node*> cache;   // key -> node
    Node head, tail;                   // sentinels: head.next is the most recent

    void unlink(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void push_front(Node* node) {
        node->prev = &head;
        node->next = head.next;
        head.next->prev = node;
        head.next = node;
    }

public:
    explicit LRUCache(int capacity) : capacity(capacity) {
        head.next = &tail;
        tail.prev = &head;
    }

    ~LRUCache() {
        for (auto& [key, node] : cache) delete node;
    }

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        Node* node = it->second;
        unlink(node);
        push_front(node);
        return node->value;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            Node* node = it->second;
            node->value = value;
            unlink(node);
            push_front(node);
            return;
        }
        if ((int)cache.size() == capacity) {
            Node* lru = tail.prev;
            unlink(lru);
            cache.erase(lru->key);
            delete lru;
        }
        Node* node = new Node{key, value};
        cache[key] = node;
        push_front(node);
    }
};

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    private static class Node {
        int key, value;          // key kept so eviction can delete the map entry
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> cache = new HashMap<>();   // key -> node
    private final Node head = new Node(0, 0);   // sentinel: head.next is the most recent
    private final Node tail = new Node(0, 0);   // sentinel: tail.prev is the least recent

    LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void pushFront(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    int get(int key) {
        Node node = cache.get(key);
        if (node == null) return -1;
        unlink(node);
        pushFront(node);
        return node.value;
    }

    void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            unlink(node);
            pushFront(node);
            return;
        }
        if (cache.size() == capacity) {
            Node lru = tail.prev;
            unlink(lru);
            cache.remove(lru.key);
        }
        node = new Node(key, value);
        cache.put(key, node);
        pushFront(node);
    }
}

The node stores its key as well as its value. That looks redundant, but eviction starts from the list: you know which node is tail.prev, and you need its key to delete the right entry from cache.

Why it’s O(1)

Each operation does a fixed amount of work: one hash map lookup, then a constant number of pointer changes.

Step	Cost	Why
find the key	O(1) average	hash map lookup
unlink a node	O(1)	its `prev` and `next` are right there
link after `head`	O(1)	four pointer writes
evict	O(1)	the victim is always `tail.prev`

Space is O(capacity): one map entry and one node per stored key, plus two sentinels. The hash map’s O(1) is on average; a bad hash function could make lookups slower, as with any hash map.

Common mistakes

Updating a key without moving it

A put on a key that’s already cached is a use. If you only change the value, that key keeps its old place and may be evicted next, even though it was just written.

node.value = value                  # ✗ key keeps its old, stale position
node.value = value                  # ✓ then move it to the front
self._unlink(node); self._push_front(node)

Evicting from the list but not the map

Unlinking tail.prev is only half of an eviction. If the map entry stays, get finds a node that isn’t in the list any more, and the map grows forever.

self._unlink(self.tail.prev)        # ✗ cache still points at it
lru = self.tail.prev                # ✓ remove from both
self._unlink(lru); del self.cache[lru.key]

Moving a node on a miss, or not on a hit

Only a hit moves a node. A common slip is to return the value on a hit without touching the list, which turns the cache into first-in, first-out.

return self.cache[key].value        # ✗ read, but recency not updated
self._unlink(node); self._push_front(node)   # ✓ then return node.value

Keeping the order in a plain list

A Python list or array of keys looks simpler, but moving a key to the front means finding and removing it first, which is O(n) per operation.

self.order.remove(key); self.order.append(key)   # ✗ O(n) scan and shift
self._unlink(node); self._push_front(node)       # ✓ O(1) with the node in hand

Variations

OrderedDict and LinkedHashMap. Python’s OrderedDict has move_to_end(key) and popitem(last=False), which is the whole cache in a few lines. Java’s LinkedHashMap(capacity, 0.75f, true) keeps access order, and overriding removeEldestEntry to return size() > capacity evicts for you. Fine in real code; interviewers usually want the list by hand.
LFU cache. Evict the key used the fewest times, breaking ties by recency. Keep a map from use count to its own LRU list, plus the current minimum count. A new key resets the minimum to 1.
Expiry (TTL). Store a timestamp in each node and treat an expired node as a miss, deleting it lazily when you meet it. To also free memory eagerly, keep a second list or a heap ordered by expiry time.
Thread safety. Even get rewrites pointers, so concurrent calls can corrupt the list. The simple fix is one lock around each operation; busy caches split keys across several independently locked shards.
Weighted capacity. When items have sizes, evict from the back in a loop until the new item fits, and decide what to do with an item bigger than the whole cache.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
You must build a cache with O(1) get and put that evicts the least recently used key when full. Which pair of structures does it?
The map finds a key’s node in O(1), and the doubly linked list unlinks it and puts it at the front in O(1). A heap makes every access O(log n), a plain list needs an O(n) remove to move a key, and a singly linked list can’t unlink a node without first walking to its predecessor.

An LRU cache built on OrderedDict, with capacity 2. What does this print?

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d:
            return -1
        self.d.move_to_end(k)
        return self.d[k]
    def put(self, k, v):
        if k in self.d:
            self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap:
            self.d.popitem(last=False)

c, out = LRU(2), []
c.put(1, 1); c.put(2, 2)
out.append(c.get(1))
c.put(3, 3)
out.append(c.get(2))
c.put(4, 4)
out += [c.get(1), c.get(3), c.get(4)]
print(out)

This put changes an existing key’s value but never refreshes its position. What does it print?

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d:
            return -1
        self.d.move_to_end(k)
        return self.d[k]
    def put(self, k, v):
        if k not in self.d and len(self.d) == self.cap:
            self.d.popitem(last=False)
        self.d[k] = v

c = LRU(2)
c.put(1, 1); c.put(2, 2)
c.put(1, 10)          # update: should make 1 most recent
c.put(3, 3)
print(c.get(1), c.get(2))

4
Why does each list node store its key, and not only its value?
Eviction starts from the list: you know which node is least recent, but the map is indexed by key. Without the key in the node you can’t delete the map entry, and the map would keep pointing at nodes that were unlinked. The map lookup itself already guarantees get found the right node.
5
Why must the recency list be doubly linked?
A hit jumps straight to a node somewhere in the middle. Splicing it out means rewriting node.prev.next; with only next pointers you’d walk from the head to find the predecessor, which is O(n). Sentinels and garbage collection work either way.