What Is an LRU Cache?

An LRU cache (least recently used cache) is a fixed-size cache that, when full, evicts whichever item hasn’t been accessed for the longest time to make room for a new one. It’s one of the most common caching strategies in practice because the underlying assumption — data accessed recently is more likely to be accessed again soon — holds up well for a huge range of real workloads, from database query results to CPU memory pages.

Why eviction policy matters

Any bounded cache eventually fills up, and at that point it has to decide what to throw away to make room for new entries. The naive options are bad: evicting randomly wastes useful data for no reason, and evicting whatever was inserted first (FIFO) ignores whether that item is still being used heavily. LRU tracks actual usage recency and evicts based on that, which tends to keep “hot” data in the cache and let genuinely stale data fall out — closer to what you’d want intuitively, and cheap enough to implement that it’s rarely worth reaching for something fancier unless you’ve measured a specific reason to.

The data structure: hash map plus doubly linked list

The classic LRU cache implementation combines two structures to get O(1) time for both reads and writes:

• A hash map from key to a node, giving O(1) lookup — see our piece on hash tables for why that lookup is constant time.
• A doubly linked list ordering entries by recency, with the most recently used at one end and the least recently used at the other.

The hash map’s values aren’t the cached data directly — they’re pointers to nodes in the linked list, so a lookup can jump straight to a node and then move it in the list without scanning anything.

get(key):
  if key not in map: return miss
  node = map[key]
  move node to the front of the list   # it's now the most recently used
  return node.value

put(key, value):
  if key in map:
    update node.value; move node to front
  else:
    if list is full:
      evict the node at the back of the list (the least recently used)
      remove it from the map too
    insert a new node at the front; add it to the map

Both operations are O(1) because a doubly linked list lets you remove and reinsert a node without traversing the list — you just need pointers to its neighbors, which the node already holds. This is exactly the kind of problem that’s easy to get to O(n) by accident (searching a plain array for “the oldest entry” every eviction) and the linked list is what avoids that.

LRU vs other eviction policies

Policy	Evicts	Good for	Downside
LRU	Least recently accessed	General-purpose, recency-biased workloads	Vulnerable to a single large scan flushing useful entries
LFU (least frequently used)	Lowest access count	Workloads with a stable set of “hot” items	Slow to adapt when access patterns shift
FIFO	Oldest inserted	Simple, predictable	Ignores whether an item is still being used
Random	Arbitrary	Very cheap to implement	No relationship to actual usage

The “vulnerable to a scan” problem is real: if something iterates over a huge range of keys just once, a pure LRU cache will treat all of them as “just used” and evict genuinely hot data to make room, even though the scanned items will likely never be touched again. Production caches (Redis included) often use LRU approximations or hybrid policies specifically to blunt this failure mode, trading a small amount of eviction accuracy for resistance to that pathological case.

Where LRU shows up

LRU and its approximations are everywhere once you start looking: Redis supports LRU-based eviction when it hits a memory limit, CPU cache hardware uses LRU-like policies to decide what to evict from L1/L2/L3, operating systems use it for page replacement in virtual memory, and application-level caches — an in-memory cache in front of a slow database query, for instance — reach for it as the default because it requires no tuning and performs well without knowing anything about the specific access pattern in advance.

Implementing one yourself

Most languages have a built-in or standard-library structure that gets you most of the way there without hand-rolling the linked list — JavaScript’s Map, for instance, preserves insertion order and lets you re-insert a key to move it to the end, which is enough to build a serviceable LRU cache in a few lines. See our piece on Map and Set for the mechanics of why that works. For high-throughput production use, though, reach for a tested library or your cache layer’s built-in eviction policy rather than a hand-rolled version — the edge cases (concurrent access, exact eviction-order guarantees) are easy to get subtly wrong.

The takeaway

An LRU cache evicts the least recently used entry when it’s full, on the assumption that recently accessed data is the most likely to be accessed again. The standard implementation pairs a hash map for O(1) lookup with a doubly linked list for O(1) reordering, giving constant-time reads and writes regardless of cache size. It’s the default eviction policy for good reason — cheap, requires no tuning, and matches real access patterns well enough that it’s rarely worth reaching for something more complex without a measured reason to.