LRU Cache

A cache is a bet on the near future: keep the entries you are likely to need again in fast memory, and let slow storage handle the rest. Memory is bounded, so every arrival can force a departure, and the cache needs a rule for choosing who leaves. The least-recently-used rule answers with a ranking. Keep the entries ordered by how recently each was used, and when room is needed, evict the one at the bottom.

The figure above runs a cache of four slots with single-letter keys. The most recently used entry sits at the front on the left, the least recent at the tail on the right, and the hash map below points into the list. Press play and the cache runs get(A): one lookup, a hit, and a move to the front. Then read on, because the interesting part is not the policy. It is how the lookup and the reorder both stay constant time.

The policy is a ranking

Every operation restates the ranking. A get that hits moves its key to the front, because the key was just used. A put does the same, whether the key is new or refreshed. Nothing else moves. So the entry at the tail is always the one whose last use lies furthest in the past, and it is always the next eviction candidate.

Recency is a heuristic, not knowledge of the future. It pays off because real workloads have temporal locality: data used recently is more likely than average to be used again soon. Web traffic repeats hot keys, databases reread hot pages, and loops re-execute hot code. When that structure holds, the tail really is the least useful entry to keep. The workload section below shows where the bet breaks.

One structure alone is too slow

The policy asks for two things at once: look up any key in constant time, and maintain the recency ranking, also in constant time. Maintaining the ranking means two operations. Move any entry to the front. Remove the entry at the tail.

A hash map alone gives the lookup and nothing else. It keeps keys unordered, so finding the least recently used entry means comparing a timestamp on every entry: O(n) on every eviction. A linked list alone keeps the ranking at its two ends, but a get has to walk the list to find its key: O(n) on every lookup. A heap ordered by timestamp evicts in O(log n) and still cannot find an arbitrary key without a scan. Each candidate moves the cost around. None removes it.

A map plus a list

The design that works runs both structures at once, pointed at the same entries. A doubly-linked list holds the entries in recency order, most recent at the front. A hash map records, for each key, the node that holds it in the list. The map answers where. The list answers in what order.

get(key) asks the map for the node, one hash lookup. On a hit, the node leaves its place and re-links at the front: point the node's two neighbors past each other, then thread the node in behind the head. That is a fixed handful of pointer writes, with no walking. On a miss, return -1 and change nothing.

put(key, value) runs the same lookup. A hit refreshes the value and moves the node to the front. A miss creates a node at the front, and when the cache was full, first unlinks the tail node and deletes its map entry. The tail is one pointer hop away, because the list keeps both ends.

The list is doubly linked because removal needs the predecessor. Unlinking a node rewrites node.prev.next and node.next.prev, and with a singly-linked list there is no way back from a node to the one before it. Removal turns into a walk from the front. The second pointer per node is the price of constant-time removal.

Watch a hit in the figure. The map chip flashes, a connector lands on the node, and the node glides to the front while the others shift one slot toward the tail. The map entry itself never moves. It points at the node, wherever the node sits.

A walkthrough: miss, evict, insert

The figure below starts from the same four entries, C, A, D, B from front to tail, and runs put(E, 5). Press play and it runs exactly these steps:

1. The map has no entry for E, so E is new, and the cache is full.

2. The tail, B, is the least recently used key. Its node unlinks, and its map entry goes with it.

3. E enters at the front as the most recent, and C, A, and D each shift one slot toward the tail.

Two more cases fit the same machinery. In either figure, type Z and press Get: the map has no entry, the lookup returns -1, and the list stays exactly as it was. A miss teaches the cache nothing. Then press Put with a key that is already in, say C: the put refreshes the value and moves the key to the front, and nothing evicts.

The code is two small helpers

Most of the class is two helpers. _unlink splices a node out of the list, and _push_front threads a node in behind the head. get and put are thin wrappers that call them in the right order. Two sentinel nodes, a dummy head and a dummy tail, bracket the list and remove the edge cases: every real node always has a prev and a next, so the helpers never branch on null.

class Node:
	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.prev = None
		self.next = None

class LRUCache:
	def __init__(self, capacity):
		self.capacity = capacity
		self.map = {}                 # key -> node
		self.head = Node(None, None)  # sentinels bracket the list
		self.tail = Node(None, None)
		self.head.next = self.tail
		self.tail.prev = self.head

	def _unlink(self, node):
		node.prev.next = node.next
		node.next.prev = node.prev

	def _push_front(self, node):
		node.prev = self.head
		node.next = self.head.next
		self.head.next.prev = node
		self.head.next = node

	def get(self, key):
		node = self.map.get(key)
		if node is None:
			return -1
		self._unlink(node)
		self._push_front(node)
		return node.value

	def put(self, key, value):
		if key in self.map:
			self._unlink(self.map[key])
		elif len(self.map) == self.capacity:
			tail = self.tail.prev
			self._unlink(tail)
			del self.map[tail.key]
		node = Node(key, value)
		self.map[key] = node
		self._push_front(node)

The implementation panel below carries the same class in Python and JavaScript. Both languages ship a shortcut: Python's OrderedDict has move_to_end, and JavaScript's Map keeps insertion order, so delete plus set refreshes recency. The list version shows the machinery the shortcuts hide, and it is the version interviews ask for.

Constant time, bounded space

Every step of every operation is one hash lookup or a fixed count of pointer writes:

Space is O(capacity): one list node and one map entry per cached key, and the cache never holds more than capacity entries.

Where the bet wins and loses

The policy pays off when requests cluster in time, and the figure below makes that concrete. It plays three request streams through the same cache. The loop stream asks for A, B, C, D over and over. With capacity 4 the whole loop fits, so after one warm-up cycle every request hits: 20 hits in 24 requests. Drag the capacity down to 3 and the same loop hits zero. Every request evicts exactly the key it will need three steps later. One slot short, and no policy can help.

The scan stream is the honest failure. Eight keys requested in order, repeated: with any capacity below 8, every request misses, because the key evicted to make room is always the next one the scan needs. Worse, the scan flushes genuinely hot entries out of the cache on its way through. Operators call this cache pollution. This is why production systems approximate the policy rather than run it textbook-pure. Redis samples a few entries and evicts the coldest of the sample, and the clock sweep in operating-system page tables tracks recency with one reference bit per page. CDNs go further and screen one-hit wonders with a Bloom filter so a scan never enters the cache at all.

When frequency matters more than recency, the cousin policy LFU evicts the least frequently used instead. Picture a key used fifty times last hour against one used a minute ago: recency keeps the second, frequency keeps the first. LFU costs more bookkeeping and has its own failure mode, stale hot keys that never leave, which is why recency remains the default.

Where it earns its keep

The same two structures show up wherever a fast layer sits in front of a slow one:

• CPU and memory paging. Hardware and kernels evict pages by recency approximations. The working set is the set of pages that must fit to avoid thrashing.

• Database buffer pools. PostgreSQL and InnoDB keep hot pages in memory and evict cold ones, with scan resistance bolted on.

• Object caches. Memcached and Redis evict by LRU variants when memory fills. Distributed caches pair the policy with consistent hashing to decide which node holds a key at all.

• Memoization. Python's functools.lru_cache turns any pure function into a bounded cache with one decorator.

The practice problems below are the same machinery in different costumes. Build the map and the list by hand once, in the linked LRU Cache problem, and every variant after it reads as a small change to one of the two helpers.