A bounded cache must find key k and choose a victim when no free slot remains. Keeping entries only in recency order makes the victim obvious, but finding an arbitrary key still requires a scan.

LRU (Least Recently Used) stores each entry in a map and a doubly-linked list. The map finds the node. The list orders nodes from most recently used at the head to least recently used at the tail. A get promotes its node to the head. A put that exceeds capacity removes the tail and deletes the same key from the map. The structure retains neither insertion order nor access frequency. It records only the recency of entries still resident.

Core shape: key → map → list node → recency-ordered doubly-linked list → head is MRU, tail is the eviction victim

Visualization

The cache below has capacity four. The map stores node addresses, while the linked chain orders the same nodes from MRU on the left to LRU on the right. Get promotes a hit; Put updates or inserts at MRU and evicts the tail when full.

Representation and Invariants

Two structures hold the same set of entries, indexed differently:

The map stores key → node and provides expected $O (1)$ lookup. It never scans the list.
The doubly-linked list orders those nodes by recency. Each node stores key, value, and both prev/next pointers. The key is duplicated into the node deliberately: eviction starts from a node (the tail) and must delete the corresponding map entry, which requires recovering the key without a reverse lookup.
Sentinel head and tail nodes bracket the list. Every real node always has a non-null neighbour on each side, so splicing and unlinking are branch-free pointer rewrites with no empty-list or single-element special cases.

Three invariants define a valid state:

The map and the list contain exactly the same set of keys. Every map value points at a live list node, and every non-sentinel node’s key is present in the map.
A node’s position encodes recency: the node just after head is the most-recently-used entry, the node just before tail is the eviction victim.
The number of resident entries never exceeds capacity. A put that would exceed it evicts first.

get(k) reads the map, unlinks the node from between its current neighbours, and splices it after head. Its value and key are unchanged; the move uses a fixed six pointer assignments. put(k, v) updates the same node in place and moves it to the head when k is resident; otherwise, if the cache is full, it first unlinks the node before tail and removes that node’s key from the map, then creates the new node in both structures. The recency order is an internal artifact: two caches that received the same accesses in the same order hold identical contents, but the pointer layout is not a domain value.

Complexity

capacity: maximum number of entries the cache may retain
n: number of resident cache entries

When the Composite Breaks

Every failure starts with the map and list disagreeing about the resident entries.

That is only possible because the list is doubly linked: the node reached through the map exposes both neighbours, so node.prev.next = node.next and node.next.prev = node.prev splice it out directly. This is why a circular buffer or a plain queue does not suffice for LRU: neither can promote an arbitrary interior entry without first finding its predecessor.

An eviction that unlinks the tail but leaves its key in the map creates a stale lookup. The exact symptom depends on the list implementation: promotion may throw because the node no longer belongs to the list, or custom pointer code may reinsert a logically evicted entry. The inverse, deleting the map entry while leaving the node linked, creates an orphan that consumes a recency slot but can never be found or promoted.

Capacity is what forces an eviction policy to exist at all. An unbounded hash map never evicts and needs neither the list nor a victim rule. The moment a size bound is imposed, some entry must be chosen to leave, and LRU’s choice is “the tail.” That choice has a known weakness: a single large scan touches many keys once, marching each to the head and pushing the genuinely hot working set toward the tail until it is evicted — cache pollution. LRU trades that vulnerability for its simplicity.

The composite is not atomic. A get performs a map read followed by several pointer writes. A concurrent put interleaving between them can splice against neighbours the get already moved, corrupting the list. LRU needs external locking (or a sharded/striped design) — neither the map nor the list provides safe concurrent mutation on its own.

Diagram and C# Implementation

Map into a recency-ordered list

flowchart LR
  subgraph Map["HashMap: key -> node"]
    K1["k=A"]
    K2["k=B"]
    K3["k=C"]
  end
  H["head (sentinel)"] --> A["A (MRU)"] --> B["B"] --> C["C (LRU / next evicted)"] --> T["tail (sentinel)"]
  K1 -.-> A
  K2 -.-> B
  K3 -.-> C

C# implementation

public sealed class LruCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _map = new();
    private readonly LinkedList<(TKey Key, TValue Value)> _order = new(); // head = MRU, tail = LRU
 
    public LruCache(int capacity)
    {
        if (capacity <= 0)
        {
            throw new ArgumentOutOfRangeException(nameof(capacity));
        }
 
        _capacity = capacity;
    }
 
    public bool TryGet(TKey key, out TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            _order.Remove(node);        // unlink directly from the middle
            _order.AddFirst(node);      // promote to most-recently-used
            value = node.Value.Value;
            return true;
        }
 
        value = default!;
        return false;
    }
 
    public void Put(TKey key, TValue value)
    {
        if (_map.TryGetValue(key, out var existing))
        {
            existing.Value = (key, value);
            _order.Remove(existing);
            _order.AddFirst(existing);
            return;
        }
 
        if (_map.Count >= _capacity)
        {
            var victim = _order.Last!;  // tail = least-recently-used
            _order.RemoveLast();
            _map.Remove(victim.Value.Key); // delete BOTH views together
        }
 
        var node = _order.AddFirst((key, value));
        _map[key] = node;
    }
}

The tuple carries the Key so eviction can delete the map entry starting from the tail node alone, with no reverse lookup.

Comparison

Cache	Eviction victim	Stronger case	Weaker case
LRU cache	Least recently used (tail)	Recent access predicts reuse (temporal locality)	A single large scan flushes the hot set
LFU cache	Least frequently used	Popularity is stable and frequency predicts reuse	Cold-start bias. Slow to drop a once-popular key. More bookkeeping
FIFO / circular buffer cache	Insertion order only	Insertion order is an acceptable eviction proxy and reuse is irrelevant	Ignores reuse entirely. Evicts hot entries that were inserted early
Plain hash map	None	Eviction is unnecessary because the working set is externally bounded and fits memory	No eviction, so it grows without limit
.NET `MemoryCache`	Size / time / priority policies	Absolute size limits, expirations, and eviction callbacks are needed	Not strict LRU. Recency is one signal among several

An LFU cache becomes stronger when frequency predicts reuse better than recency — a stable set of popular keys that a one-off scan should not dislodge. A FIFO or circular buffer cache is simpler still but blind to reuse, fitting only insertion-order eviction. A plain hash map is the right structure when an external bound keeps the working set within its allocated capacity and no eviction policy is needed.

Topics

DEVBOOK

LRU Cache

Representation and Invariants

When the Composite Breaks

Diagram and C# Implementation

Comparison

References

Graph View

Table of Contents

Backlinks