LRU Cache (Hash Map + Doubly Linked List) Visualization

The problem: a cache that forgets the right things

A cache keeps a small number of recently needed results close at hand, so that asking for them again is fast. It has a fixed capacity: when it is full and a new entry arrives, some old entry has to go. The least recently used (LRU) policy throws out the entry that has gone the longest without being used. The bet is that what you used a moment ago you are likely to use again soon, and what you haven't touched for a while you probably won't.

An LRU cache supports two operations, and both should take O(1) time:

• get(key): return the value stored for key, or -1 if it is not in the cache. A successful get counts as a use.
• put(key, value): store the value. If the key is already there, overwrite its value (this also counts as a use). If it is new and the cache is full, first evict the least recently used entry.

The idea: two structures that point at the same nodes

We need two things fast: find an entry by its key, and know which entry is the least recently used. No single simple structure does both, so an LRU cache combines two:

• A doubly linked list holds the entries in order of use. The head (drawn on the left) is the most recently used node, the tail (on the right) the least recently used. Each node stores its key, its value and two pointers, prev and next. With both pointers, a node can be cut out of the middle of the list in constant time, because it knows its neighbours on both sides.
• A hash map from each key to its node in the list (not to the value). This lets us jump straight to any node without walking the list.

Using an entry means: find its node through the map, unlink it from where it is, and relink it at the head. Evicting means: remove the tail node, and remove its key from the map. That is why each node stores its key as well as its value: when the tail is evicted, we need its key to delete the map entry.

The algorithm

get(key):
    if key not in map:
        return -1                       // miss: nothing changes
    node = map[key]                     // hit: O(1) lookup, no search
    moveToFront(node)                   // it is now the most recently used
    return node.value

put(key, value):
    if key in map:                      // existing key: update and use it
        node = map[key]
        node.value = value
        moveToFront(node)
        return
    if size == capacity:                // full: make room first
        lru = tail
        unlink(lru)
        delete map[lru.key]
        size = size - 1
    node = new Node(key, value)
    linkAtFront(node)
    map[key] = node
    size = size + 1

moveToFront(node):
    if node is head: return
    unlink(node)
    linkAtFront(node)

unlink(node):                           // cut node out, fixing both neighbours
    if node.prev != null: node.prev.next = node.next  else: head = node.next
    if node.next != null: node.next.prev = node.prev  else: tail = node.prev

linkAtFront(node):
    node.prev = null
    node.next = head
    if head != null: head.prev = node  else: tail = node   // list was empty
    head = node

Many implementations add two dummy sentinel nodes, one before the head and one after the tail. Then every real node always has a prev and a next, and the null checks in unlink and linkAtFront disappear. The animation draws the list without sentinels: a / in a pointer cell means null, and the blue head and tail labels are the two list pointers.

A worked example

Take capacity 3 and this sequence. The list is written head (most recent) to tail (least recent), as key:value; the map is written as the set of keys it holds (each pointing at its node).

Operation	What happens	Returns	List (head → tail)	Map keys
put(1, 10)	new key, list was empty: head = tail = 1:10		1:10	{1}
put(2, 20)	new key, linked at the head		2:20, 1:10	{1, 2}
put(3, 30)	new key, linked at the head; now full		3:30, 2:20, 1:10	{1, 2, 3}
get(1)	hit: 1:10 is the tail; unlink it (tail = 2:20) and link it at the head	10	1:10, 3:30, 2:20	{1, 2, 3}
put(4, 40)	new key, full: evict the tail 2:20 and delete map[2], then link 4:40 at the head		4:40, 1:10, 3:30	{1, 3, 4}
get(2)	miss: 2 was evicted	-1	4:40, 1:10, 3:30	{1, 3, 4}
put(3, 33)	existing key: value 30 → 33, then move 3 to the head		3:33, 4:40, 1:10	{1, 3, 4}
put(5, 50)	new key, full: evict the tail 1:10, then link 5:50 at the head		5:50, 3:33, 4:40	{3, 4, 5}

Notice the fourth step. Key 1 was the first key put in, so a first-in first-out cache would have evicted it at put(4, 40). Because get(1) used it, LRU evicted 2 instead. You can replay this sequence in the animation with capacity 3.

Why it is correct

The cache keeps three facts true (its invariants) before and after every operation:

1. The list holds exactly the cached entries, one node per key, ordered by the time of their last use, most recent at the head.
2. The map holds exactly the same keys as the list, and map[k] is the node for k.
3. size ≤ capacity.

Each step is there to keep one of them. A use moves the node to the head, and every other node keeps its relative order, so invariant 1 holds: the node now has the latest use time, and the others' times didn't change. By invariant 1, the tail is always the least recently used entry, so evicting the tail is exactly the LRU rule. Unlinking the evicted node and deleting its map entry together keep invariant 2; forgetting either one leaves the two structures out of step. Evicting before adding a new key (only when the cache is full) keeps invariant 3. An update of an existing key never changes the size, so it never evicts.

Time and space

Every operation does one hash map lookup, at most one insert or delete in the map, and a fixed number of pointer assignments (unlink changes two pointers, linkAtFront about four). None of them loops over the list. A hash map lookup, insert or delete takes O(1) expected time, so get and put both take O(1) expected time, however big the capacity. The space is O(capacity): one node and one map entry per cached key.

Compare the simpler alternatives. A plain list or array kept in order of use needs O(n) time to find a key. A map from keys to "last use time" finds keys quickly but needs O(n) time to find the oldest entry (or O(log n) with a heap, plus the trouble of updating times inside it). A singly linked list is not enough either: to unlink a node you need its predecessor, and finding that means walking from the head.

Common mistakes, edge cases and variants

• Forgetting that get is a use. A hit must move the node to the head; otherwise the cache degrades to first-in first-out.
• Putting an existing key as a new node. That leaves two nodes for one key and makes the map point at only one of them. Check the map first and update in place.
• Evicting on update. put of a key that is already present never evicts, even when the cache is full.
• Deleting the map entry but not the node (or the reverse). Store the key in the node so eviction can find the map entry.
• The ends of the list. Moving the head, moving or evicting the tail, a list with one node, and capacity 1 all touch head or tail directly. Sentinel nodes remove these special cases.
• Variants. Some libraries let the map's own entry order do the work: Java's LinkedHashMap with access order and removeEldestEntry, or Python's OrderedDict with move_to_end and popitem(last=False) (and functools.lru_cache for memoizing functions). Related policies include LFU (evict the least frequently used), CLOCK (an LRU approximation with one "used" bit per entry, common in operating systems), and LRU-K and 2Q, which resist one-time scans that would otherwise flush a plain LRU cache.

Where LRU caches are used

LRU and close approximations of it are everywhere: operating systems choosing which memory pages to swap out, database buffer pools, CPU caches (in hardware, usually approximate LRU within each set), web browsers and CDNs caching pages and images, in-memory caches such as Redis and Memcached when they are full, DNS resolvers, and memoization of expensive function calls. It is also one of the most common data structure design questions in programming interviews, precisely because it needs two structures working together.

Eviction decides what stays in a cache; Cache Strategies shows how an application reads and writes through one (cache-aside, write-through, write-behind, refresh-ahead).

References

Cache replacement policies: Least recently used (LRU)

Doubly linked list

Hash table

Page replacement algorithm