How an LRU Cache Works

An LRU cache has to answer two questions quickly: "is this key in the cache?" and "which key was used least recently?". No single classic data structure answers both in constant time, so the standard design combines two: a hash map for lookup and a doubly linked list for recency order. This chapter walks through that design and traces it on a small example.

Two structures working together

• The hash map maps each key to its node in the list, so finding an entry is O(1) on average.
• The doubly linked list keeps the entries in recency order. The front (next to head) is the most recently used entry; the back (next to tail) is the least recently used.
• Each node stores its key as well as its value. On eviction we only have the node at the back, and we need its key to delete it from the map.
• The list is doubly linked because removing a node from the middle needs its predecessor. With prev and next pointers, unlinking takes O(1).
• Two sentinel nodes, head and tail, never hold data. They remove every special case for an empty list or for the first and last node.

head <-> [C] <-> [B] <-> [A] <-> tail
         most recent      least recent

map: { A: node A, B: node B, C: node C }

The operations

A get(key) looks the key up in the map. On a miss it returns a sentinel value such as -1 or None. On a hit it unlinks the node and inserts it right after head, then returns the value.

A put(key, value) first checks the map. If the key exists, it updates the value and moves the node to the front, exactly like a hit. Otherwise, if the cache is full, it removes the node just before tail and deletes that node's key from the map; then it creates a new node, inserts it after head and stores it in the map.

All pointer work reduces to two helpers. Each touches a constant number of pointers, which is why both operations are O(1).

def unlink(node):
    # A <-> node <-> B  becomes  A <-> B
    node.prev.next = node.next
    node.next.prev = node.prev

def push_front(head, node):
    # head <-> X  becomes  head <-> node <-> X
    node.prev = head
    node.next = head.next
    head.next.prev = node
    head.next = node

Moving a node to the front is simply unlink(node) followed by push_front(head, node). Evicting is unlink(tail.prev) plus a map deletion.

A trace with capacity 3

The list is written from most recent to least recent.