LRU Cache: Evicting the Least Recently Used Item

Why Caches Need an Eviction Policy

A cache exists to keep a small, fast set of items close at hand so repeated requests don't have to pay the cost of fetching from a slower source, whether that's main memory, disk, a database, or a remote server. But fast storage is always scarce: a CPU cache is measured in megabytes, a database buffer pool in gigabytes, and a CDN edge node has a fraction of the space of the origin server it's shielding. Once that fixed capacity is full, adding a new item means something already inside has to leave. The rule that decides which item leaves is the eviction policy, and it matters enormously for performance. A poor policy evicts data that's about to be reused, forcing an expensive re-fetch and turning the cache into overhead rather than a speedup. A good policy keeps the items most likely to be reused and clears out the ones that have gone cold. Because real workloads tend to exhibit temporal locality — if something was accessed recently, it's disproportionately likely to be accessed again soon — eviction policies that track recency tend to perform very well in practice. This is the entire motivation for the Least Recently Used approach: rather than guessing randomly or evicting in arrival order, it uses each item's own access history as the signal for whether to keep it.

The LRU Principle

Least Recently Used eviction follows one rule: when the cache is full and a new item must be inserted, remove whichever item has gone the longest without being accessed. Every time an item is read or written, it's treated as freshly used and moved to the front of an imaginary queue ordered by recency. The item sitting at the back of that queue, the one that hasn't been touched in the longest stretch of time, is always the eviction candidate. This makes LRU a good approximation of the ideal (but practically impossible) strategy of evicting whatever will be needed furthest in the future, since recent usage is often the best available predictor of near-future usage. Two operations define the policy: get, which retrieves an item if present and marks it as just used, and put, which inserts or updates an item and, if the cache is already at capacity, triggers an eviction of the least recently used entry first. The elegance of LRU is that it needs no statistics, no counters, and no prediction model; it only needs to remember order. That simplicity is exactly what allows it to be implemented so efficiently, which is the subject of the next section.

Hash Map Plus Doubly Linked List

The classic LRU implementation combines two data structures so that every operation runs in constant time, regardless of how many items the cache holds. A hash map stores a key mapped directly to a node's location, giving constant-time lookup: given a key, you find the matching cache entry immediately with no scanning. A doubly linked list threads all the entries together in recency order, with the most recently used item at the head and the least recently used item at the tail. Because it's doubly linked, any node can be unlinked from its current position and relinked elsewhere in constant time, without walking the list. On a get, the hash map locates the node instantly, and the node is unlinked and reinserted at the head, since it's now the most recently used item — both are constant-time pointer operations. On a put for a new key, a node is created, added to the head, and registered in the hash map; if the cache was already full, the node at the tail is unlinked and its key removed from the map, which is exactly the eviction step. On a put that updates an existing key, the node is moved to the head just like a get. Neither structure alone would work this well: a hash map alone has no sense of order, and a plain array-based list would need linear-time shifting to reorder or remove entries. Together, they give O of 1 lookup and O of 1 reordering, the combination that makes LRU practical even at very large scale.

A Worked Example, Step by Step

Consider a cache with capacity 3, and a sequence of accesses to keys A, B, C, D, B, E. Start empty. Access A: not present, insert it; order from most to least recent is A. Access B: not present, insert it; order is B, A. Access C: not present, insert it; order is C, B, A, and the cache is now full. Access D: not present and the cache is full, so evict the least recently used item, which is A at the tail; insert D at the head; order is D, C, B, with A now gone. Access B: it's present, so this counts as a hit; move B to the head without evicting anything; order is B, D, C. Access E: not present and the cache is full, so evict the current tail, which is C; insert E at the head; order is E, B, D, with C now gone. Notice that B survived the first eviction round precisely because it was re-accessed before it aged all the way to the tail, while A and C were each evicted the moment they became the least recently used entry in a full cache. This trace shows the mechanics that a simulator makes visible in real time: every access either promotes an item to the front, or triggers exactly one eviction from the back, and the hash map plus linked list combination performs each of those steps without ever scanning the whole cache.

Comparing Policies and Real-World Use

LRU is one of several eviction strategies, and the right choice depends on the access pattern. FIFO (first in, first out) evicts whichever item was inserted earliest, ignoring how recently it was used; it's simpler to implement but performs worse when an old item is still being accessed frequently, since FIFO evicts it anyway once its turn comes. LFU (least frequently used) tracks how many times each item has been accessed and evicts the one with the lowest access count; this rewards items that are popular over the long run, but it can struggle to adapt when a previously popular item suddenly goes cold, since its high historical count keeps it in the cache long after it stops being useful. LRU sits in between: it reacts quickly to changing patterns because it only cares about recency, not accumulated history, which makes it a strong general-purpose default. These trade-offs matter well beyond textbooks. CPU caches use LRU-like policies (often approximated for speed in hardware) to decide which cache lines to keep as programs access memory. Database buffer pools use LRU or LRU variants to decide which disk pages stay resident in memory, since re-reading a page from disk is far slower than serving it from RAM. Web and CDN edge caches use LRU to decide which cached responses to keep at edge nodes close to users, evicting stale or rarely requested content to make room for what's currently popular. In every one of these systems, the same hash map plus doubly linked list pattern, or a close approximation of it, is doing the work behind the scenes.

Frequently asked questions

Try it live

Everything above runs in your browser — open LRU Cache: Evicting the Least Recently Used Item and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.