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.

Step 5 is the key moment. A was inserted first, so a FIFO cache would have evicted it. Because step 4 read A, LRU evicts B instead. Step 6 shows that a miss changes nothing, and step 7 shows that an update counts as a use.

Reproducing the trace

The quickest way to check a trace is a short simulation with OrderedDict, which already provides the two primitives we need: move_to_end and popitem(last=False).

from collections import OrderedDict

def run(capacity, ops):
    cache = OrderedDict()            # first = least recent, last = most recent
    for op, key, *value in ops:
        result = "-"
        if op == "get":
            if key in cache:
                cache.move_to_end(key)
                result = cache[key]
            else:
                result = -1
        else:
            if key in cache:
                cache.move_to_end(key)
            elif len(cache) >= capacity:
                cache.popitem(last=False)
            cache[key] = value[0]
        order = ", ".join(reversed(cache))  # most recent first
        print(f"{op}({key}) -> {result}: {order}")

run(3, [("put", "A", 1), ("put", "B", 2), ("put", "C", 3), ("get", "A"),
        ("put", "D", 4), ("get", "B"), ("put", "C", 30), ("put", "E", 5), ("get", "D")])

The last printed line is get(D) -> 4: D, E, C, matching the table.

Common mistakes in the walkthrough

• Forgetting to move the node on a get. The cache then behaves like FIFO.
• Forgetting to move the node when put updates an existing key.
• Evicting before checking whether the key already exists. Updating a key in a full cache must not evict anything.
• Removing the node from the list but not from the map (or the reverse). The two structures must always describe the same set of keys.

Summary

• The map gives O(1) lookup; the doubly linked list gives O(1) reordering and eviction.
• Sentinels head and tail remove edge cases; nodes keep their key so eviction can clean up the map.
• Hits and updates move an entry to the front; misses change nothing; eviction removes the node before tail.