Data Structures

LRU Cache Explained: Design and Implementation with O(1) Operations

A cache with unlimited room is just a bigger, faster copy of your data store, which defeats the point. Once you cap the size, you need a rule for deciding what to throw away, and Least Recently Used is the rule that shows up more often than any other.

Published July 6, 2026

The Eviction Problem

A fixed-capacity cache eventually fills up, and the next insert has to make room by removing something. Which item you remove matters: get it wrong repeatedly and the cache thrashes, evicting data right before it would have been reused, which is worse than having no cache at all because you pay the cache's bookkeeping cost without its benefit. LRU eviction assumes temporal locality — that an item accessed recently is more likely to be accessed again soon than an item that has not been touched in a while — and evicts whatever has gone the longest without being accessed.

Why the Naive Approach Is Slow

A straightforward implementation keeps items in an array or list ordered by recency and moves an item to the front every time it is accessed. The problem is that moving an item requires first finding it (O(n) scan unless you also index it) and then shifting other elements to close the gap (another O(n) in an array). For a cache handling millions of lookups per second, an O(n) operation on every access is not acceptable.

The O(1) Design: Hash Map Plus Doubly Linked List

Doubly linked list ordered by recency: The list holds the actual key-value pairs, with the most recently used item at the head and the least recently used at the tail. Because it is doubly linked, any node can be unlinked and relinked in O(1) given a pointer to it, with no shifting.
Hash map from key to list node: This gives O(1) lookup of the node for any key, so you never scan the list to find an item.
get(key): Look up the node via the hash map. If found, unlink it from its current position and relink it at the head (it is now the most recently used), then return its value. Both steps are O(1).
put(key, value): If the key already has a node, update its value and move it to the head as in get. If it is new and the cache is at capacity, remove the tail node (least recently used) from both the list and the hash map, then insert the new node at the head and add it to the hash map. Every step touches a fixed number of pointers, so this is O(1) too.

The combination works because the two structures answer different questions cheaply: the hash map answers "where is this key" and the linked list answers "what is the recency order," and neither one needs to scan the other to stay in sync.

Where LRU Falls Short

LRU's assumption breaks down under a sequential scan: reading a huge dataset once, in order, touches every key exactly once and pushes genuinely hot data out of the cache to make room for data that will never be read again. Databases that rely on LRU for their buffer pool have hit this problem badly enough to motivate alternatives. Operating system page caches typically use a variant with active and inactive lists rather than a strict recency ordering, precisely to resist this kind of scan pollution. IBM's Adaptive Replacement Cache (ARC) and the simpler CLOCK (second-chance) algorithm are both attempts to keep LRU's good behavior on skewed access patterns while resisting one-off scans.

Where LRU Shows Up in Practice

Redis: The allkeys-lru and volatile-lru maxmemory policies approximate LRU eviction (using sampling rather than a strict linked list, for efficiency) when memory limits are hit.
CPU caches and OS page caches: Hardware and kernel-level caches use LRU or close approximations to decide which cache lines or pages to evict.
Application-level caches: In-process caches in web frameworks and client libraries commonly default to LRU because it requires no configuration and performs reasonably across a wide range of access patterns.

Conclusion

The LRU cache is a good case study in matching a data structure to the operations you actually need: a hash map alone gives fast lookup but no ordering, a linked list alone gives ordering but slow lookup, and combining them gives both for a constant additional pointer per entry. Understanding where LRU's temporal-locality assumption breaks — large sequential scans being the classic case — is just as important as knowing how to implement it, because production systems rarely use pure LRU once they have been burned by that failure mode once.

The Linux kernel's memory management documentation describes how the kernel's own page cache handles this trade-off with active and inactive list generations rather than a single strict LRU chain.