LRU Cache
A cache that must forget something should forget what was used longest ago. Keep the entries in a list ordered by recency, most recent at the head: every hit moves its node to the head, every insert goes to the head, and when the cache is full the tail is the victim. The list alone would make lookups O(n), so a hash map from key to node finds the entry at once, and because each node knows its neighbours it can be unlinked from the middle without a scan. That pairing is why every operation is O(1). LFU is the other classic policy: count how often each entry is used and evict the entry with the smallest count, breaking ties by recency. A real implementation keeps one list per count and the smallest count in hand, so it stays O(1); it protects entries that have earned their place, at the cost of never forgetting an entry that was popular long ago.
An LFU cache of capacity 3. Every entry counts how often it has been used, and when the cache is full the entry with the smallest count goes; among equal counts the least recently used goes. The list is drawn most frequent first, so the tail is always the next victim. A real LFU keeps one list per count and the smallest count in hand, so every step is O(1).
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
get 1 with 1 x2 cached. Hit or miss?
Answer: Hit, its count goes up. 1 is cached, so it is served and used one more time.
get 1 with 1 x3 cached. Hit or miss?
Answer: Hit, its count goes up. 1 is cached, so it is served and used one more time.
put 4 into a full cache holding 1 x3 4 x1 3 x1. Which key is evicted?
Answer: Key 2, used 1 time. The smallest count goes first; among equal counts, the one used least recently.
get 1 with 1 x4 4 x1 3 x1 cached. Hit or miss?
Answer: Hit, its count goes up. 1 is cached, so it is served and used one more time.
put 5 into a full cache holding 1 x4 5 x1 4 x1. Which key is evicted?
Answer: Key 3, used 1 time. The smallest count goes first; among equal counts, the one used least recently.
How it runs, step by step
An LFU cache of capacity 3. Every entry counts how often it has been used, and when the cache is full the entry with the smallest count goes; among equal counts the least recently used goes. The list is drawn most frequent first, so the tail is always the next victim. A real LFU keeps one list per count and the smallest count in hand, so every step is O(1).
Empty LFU cache of capacity 3.
put 1 10: a new key with room to spare. It enters with a count of 1, ahead of older count-1 entries and behind everything used more often.
put 1.
get 1: a hit, value 10. Its count goes from 1 to 2, which moves it up past every entry with a lower count and to the front of the entries that share its new count.
get 1 hits; count 2.
get 1: a hit, value 10. Its count goes from 2 to 3, which moves it up past every entry with a lower count and to the front of the entries that share its new count.
get 1 hits; count 3.
put 2 20: a new key with room to spare. It enters with a count of 1, ahead of older count-1 entries and behind everything used more often.
put 2.
put 3 30: a new key with room to spare. It enters with a count of 1, ahead of older count-1 entries and behind everything used more often.
put 3.
put 4 40: a new key, and the cache is full. The tail, key 2 used 1 time, has the lowest count and is the least recent among those, so it is evicted. 4 enters with a count of 1, at the front of the count-1 entries.
put 4. Evicted 2.
get 1: a hit, value 10. Its count goes from 3 to 4, which moves it up past every entry with a lower count and to the front of the entries that share its new count.
get 1 hits; count 4.
put 5 50: a new key, and the cache is full. The tail, key 3 used 1 time, has the lowest count and is the least recent among those, so it is evicted. 5 enters with a count of 1, at the front of the count-1 entries.
put 5. Evicted 3.
3 entries cached, most frequent first: 1 used 4, 5 used 1, 4 used 1. LFU protects entries that have earned their place, which LRU cannot: one burst of new keys flushes an LRU cache but leaves a frequently used LFU entry alone. The price is that an entry popular long ago keeps its count forever unless the counts are aged.
3 entries cached.
Remember
- Most recent at the head, least recent at the tail; the tail is what gets evicted.
- A hit or an update moves the node to the head; a new key is inserted at the head.
- The hash map finds the node in O(1) and the doubly linked list unlinks it in O(1): together, O(1) everything.
Topics covered
Where this is used
Caching serversmemcached item eviction
memcached is this exact pairing at production scale: a hash table for lookup and prev and next pointers inside each item header for the recency list, one list per slab class. Because moving an item to the head needs the list lock, it skips the bump if the item was already moved in the last minute. Newer versions split the list into HOT, WARM and COLD segments so a one-off read cannot push a long-lived item out.
DatabasesRedis maxmemory eviction
With maxmemory-policy allkeys-lru, Redis has to pick a victim without keeping a global recency list - the pointers per key would cost more memory than they save. Instead each object carries a small last-access clock, and on eviction Redis samples a handful of random keys (maxmemory-samples, 5 by default) and drops the oldest of those, keeping the best candidates across rounds in a pool. It is approximate LRU bought with a timestamp per key instead of a list.
Operating systemsThe Linux page cache
The kernel cannot touch a list on every page access, so it keeps two lists, inactive and active, and a referenced bit per page. A page reaches the active list only on a second reference, and reclaim always takes from the tail of the inactive list. It approximates recency with list moves that happen rarely rather than on every read, and the two-list split is what stops a single large file read from evicting everything.
Developer toolsCaffeine, the Java caching library
Caffeine backs Guava-style caches and Spring's cache abstraction, and it decides admission with W-TinyLFU: a compact frequency sketch estimates how often each key has been seen, and a new entry is only let in if its estimate beats the entry that would be evicted. So it uses recency for ordering and frequency as a filter, which is the practical answer to LRU losing to scans and LFU clinging to stale winners.
Why it works this way
Why a doubly linked list and not a singly linked one?
The map hands you the node itself, but unlinking a node from a singly linked list needs the node before it, and finding that means walking from the head. That is O(n) on every hit, which throws away the whole point. With prev and next a node detaches itself in two pointer writes. A permanent sentinel head and tail also help: with them, addFirst and unlink never have to ask whether this node is the first or last one.
Why every node stores its key as well as its value
The map goes key to node, so nothing in the node is needed to look it up, and storing the key looks redundant. Then capacity is exceeded, you pull the tail node off the list, and you have to delete its entry from the map with only the node in hand. Without node.key the only way to find that entry is to scan the whole map. Leaving the key out is a classic first attempt, and it turns eviction from O(1) into O(n).
A read counts as a use, and forgetting that makes it a FIFO
If get returns the value without moving the node to the head, eviction order becomes insertion order and the cache is a queue, not an LRU. It is easy to miss because a test that inserts each key once and reads it once passes either way. The case that separates them: capacity 3, put a, b, c, then get a, then put d. LRU evicts b, a queue evicts the key you just read.
One loop larger than the cache wipes it out
Scan capacity + 1 keys in a cycle and every single access misses: the key you are about to need next is always the oldest, so it was evicted one step ago. Pure LRU scores zero here while random eviction would still hit sometimes. The LFU in this lesson does no better on this exact pattern, because every key ends up with the same count and the tie falls back to recency. What LFU does survive is the other shape, a one-off burst of fresh keys washing past a working set that already has counts behind it. That is why production caches rarely run either policy unmodified.
Read more
- Cache replacement policiesWikipedia
- Key evictionRedis
- Segmented LRU in memcachedmemcached · github.com
- Cache efficiency and W-TinyLFUCaffeine · github.com
- LruCacheAndroid Developers · developer.android.com