AlgoScope

LRU Cache

A cache that must forget something should forget what was used longest ago. Keep the entries in a list ordered by recency, most recent at the head: every hit moves its node to the head, every insert goes to the head, and when the cache is full the tail is the victim. The list alone would make lookups O(n), so a hash map from key to node finds the entry at once, and because each node knows its neighbours it can be unlinked from the middle without a scan. That pairing is why every operation is O(1). LFU is the other classic policy: count how often each entry is used and evict the entry with the smallest count, breaking ties by recency. A real implementation keeps one list per count and the smallest count in hand, so it stays O(1). It protects entries that have earned their place, at the cost of never forgetting an entry that was popular long ago.

The player

Empty LRU cache of capacity 3.

An LRU cache of capacity 3. The list is ordered by recency, most recent at the head. A hash map from key to node finds any entry at once. Moving it to the head or dropping the tail is a matter of relinking neighbours.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

  1. put 1 with keys nothing cached, capacity 3. What happens?

    • Added, there is room
    • Updated and moved to the front
    • Added, and the tail is evicted

    Answer: Added, there is room. Fewer than 3 entries, so nothing has to go.

  2. put 2 with keys 1 cached, capacity 3. What happens?

    • Added, there is room
    • Updated and moved to the front
    • Added, and the tail is evicted

    Answer: Added, there is room. Fewer than 3 entries, so nothing has to go.

  3. put 3 with keys 2 1 cached, capacity 3. What happens?

    • Added, there is room
    • Updated and moved to the front
    • Added, and the tail is evicted

    Answer: Added, there is room. Fewer than 3 entries, so nothing has to go.

  4. get 1 with keys 1 2 3 cached. Hit or miss?

    • Hit, move it to the front
    • Miss

    Answer: Hit, move it to the front. 1 is in the map, so it is served and becomes the most recent.

  5. put 4 with keys 1 3 2 cached, capacity 3. What happens?

    • Added, there is room
    • Updated and moved to the front
    • Added, and the tail is evicted

    Answer: Added, and the tail is evicted. Full, so the least recently used entry makes room.

  6. get 2 with keys 1 3 4 cached. Hit or miss?

    • Hit, move it to the front
    • Miss

    Answer: Miss. 2 is not in the map.

How it runs, step by step

  1. An LRU cache of capacity 3. The list is ordered by recency, most recent at the head. A hash map from key to node finds any entry at once. Moving it to the head or dropping the tail is a matter of relinking neighbours.

    Empty LRU cache of capacity 3.

  2. put 1 10: a new key with room to spare. It becomes the head, the most recently used.

    put 1.

  3. put 2 20: a new key with room to spare. It becomes the head, the most recently used.

    put 2.

  4. put 3 30: a new key with room to spare. It becomes the head, the most recently used.

    put 3.

  5. get 1: the map points straight at its node, value 10. It sat at position 2. Unlink it there, which its prev and next pointers make O(1), and link it back in at the head as the most recently used.

    get 1 hits, value 10, moved to the front.

  6. put 4 40: a new key, but the cache holds 3 already. The tail, key 2, is the least recently used, so it is dropped from both the list and the map, and 4:40 becomes the head.

    put 4. Evicted 2.

  7. get 2: the map has no such key, so it is a miss. Nothing moves.

    get 2 misses.

  8. 3 entries cached, most recent first: 1, 3, 4. Every get and put was O(1): the map found the node and the linked list moved it without a scan.

    3 entries cached.

The code

LRU Cache, in Python

class LruCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                                      # key -> its node, O(1)
        self.list = DoublyLinkedList()                     # head = most recent, tail = least

    def get(self, key):
        node = self.map.get(key)                           # miss
        if node is None: return None
        self.list.unlink(node); self.list.add_first(node)  # O(1) thanks to node.prev and node.next
        return node.value

    def put(self, key, value):
        if key in self.map:                                # an update is a move to the front
            self.list.unlink(self.map[key]); del self.map[key]
        node = Node(key, value)
        self.list.add_first(node); self.map[key] = node
        if len(self.map) > self.capacity:                  # over capacity: drop the tail
            victim = self.list.remove_last()
            del self.map[victim.key]

class LfuCache:                                            # evict the least frequently used; ties by recency
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                                      # key -> node; node.freq counts its uses
        self.buckets = {}                                  # freq -> its nodes, most recent first
        self.min_freq = 0
    def touch(self, node):                                 # one bucket up, most recent in the new one
        self.buckets[node.freq].unlink(node)
        if self.buckets[node.freq].is_empty() and self.min_freq == node.freq: self.min_freq += 1
        node.freq += 1; self.buckets.setdefault(node.freq, DoublyLinkedList()).add_first(node)
    def get(self, key):
        node = self.map.get(key)
        if node is None: return None
        self.touch(node); return node.value
    def put(self, key, value):
        node = self.map.get(key)
        if node is not None: node.value = value; self.touch(node); return
        if len(self.map) == self.capacity:                 # full: the tail of the lowest bucket goes
            victim = self.buckets[self.min_freq].remove_last(); del self.map[victim.key]
        node = Node(key, value, freq=1); self.map[key] = node
        self.buckets.setdefault(1, DoublyLinkedList()).add_first(node); self.min_freq = 1

LRU Cache, in JavaScript

class LruCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();                                    // key -> its node, O(1)
    this.list = new DoublyLinkedList();                      // head = most recent, tail = least
  }

  get(key) {
    const node = this.map.get(key);                          // miss
    if (node === undefined) return null;
    this.list.unlink(node);                                  // O(1) thanks to node.prev and node.next
    this.list.addFirst(node);
    return node.value;
  }

  put(key, value) {
    if (this.map.has(key)) {                                 // an update is a move to the front
      this.list.unlink(this.map.get(key));
      this.map.delete(key);
    }
    const node = new Node(key, value);
    this.list.addFirst(node);
    this.map.set(key, node);
    if (this.map.size > this.capacity) {                     // over capacity: drop the tail
      const victim = this.list.removeLast();
      this.map.delete(victim.key);
    }
  }
}

class LfuCache {                                             // evict the least frequently used; ties by recency
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();                                    // key -> node; node.freq counts its uses
    this.buckets = new Map();                                // freq -> its nodes, most recent first
    this.minFreq = 0;
  }
  touch(node) {                                              // one bucket up, most recent in the new one
    this.buckets.get(node.freq).unlink(node);
    if (this.buckets.get(node.freq).isEmpty() && this.minFreq === node.freq) this.minFreq++;
    node.freq++;
    if (!this.buckets.has(node.freq)) this.buckets.set(node.freq, new DoublyLinkedList());
    this.buckets.get(node.freq).addFirst(node);
  }
  get(key) {
    const node = this.map.get(key);
    if (node === undefined) return null;
    this.touch(node);
    return node.value;
  }
  put(key, value) {
    const existing = this.map.get(key);
    if (existing !== undefined) {
      existing.value = value;
      this.touch(existing);
      return;
    }
    if (this.map.size === this.capacity) {                   // full: the tail of the lowest bucket goes
      const victim = this.buckets.get(this.minFreq).removeLast();
      this.map.delete(victim.key);
    }
    const node = new Node(key, value, 1);
    this.map.set(key, node);
    if (!this.buckets.has(1)) this.buckets.set(1, new DoublyLinkedList());
    this.buckets.get(1).addFirst(node);
    this.minFreq = 1;
  }
}

LRU Cache, in Kotlin

class LruCache(val capacity: Int) {
    private val map = HashMap<Int, Node>()                  // key -> its node, O(1)
    private val list = DoublyLinkedList()                    // head = most recent, tail = least

    fun get(key: Int): Int? {
        val node = map[key] ?: return null                   // miss
        list.unlink(node); list.addFirst(node)               // O(1) thanks to node.prev and node.next
        return node.value
    }

    fun put(key: Int, value: Int) {
        map[key]?.let { list.unlink(it); map.remove(key) }   // an update is a move to the front
        val node = Node(key, value)
        list.addFirst(node); map[key] = node
        if (map.size > capacity) {                           // over capacity: drop the tail
            val victim = list.removeLast()
            map.remove(victim.key)
        }
    }
}

class LfuCache(val capacity: Int) {                          // evict the least frequently used; ties by recency
    private val map = HashMap<Int, Node>()                   // key -> node; node.freq counts its uses
    private val buckets = HashMap<Int, DoublyLinkedList>()   // freq -> its nodes, most recent first
    private var minFreq = 0
    fun touch(node: Node) {                                  // one bucket up, most recent in the new one
        buckets[node.freq]!!.unlink(node)
        if (buckets[node.freq]!!.isEmpty() && minFreq == node.freq) minFreq++
        node.freq++; buckets.getOrPut(node.freq) { DoublyLinkedList() }.addFirst(node)
    }
    fun get(key: Int): Int? = map[key]?.also { touch(it) }?.value
    fun put(key: Int, value: Int) {
        map[key]?.let { it.value = value; touch(it); return }
        if (map.size == capacity) {                          // full: the tail of the lowest bucket goes
            val victim = buckets[minFreq]!!.removeLast(); map.remove(victim.key)
        }
        val node = Node(key, value, freq = 1); map[key] = node
        buckets.getOrPut(1) { DoublyLinkedList() }.addFirst(node); minFreq = 1
    }
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Most recent at the head, least recent at the tail. The tail is what gets evicted.
  • A hit or an update moves the node to the head. A new key is inserted at the head.
  • The hash map finds the node in O(1) and the doubly linked list unlinks it in O(1): together, O(1) everything.

Where this is used

memcached item evictionCaching servers

memcached is this exact pairing at production scale: a hash table for lookup and prev and next pointers inside each item header for the recency list, one list per slab class. Because moving an item to the head needs the list lock, it skips the bump if the item was already moved in the last minute. Newer versions split the list into HOT, WARM and COLD segments so a one-off read cannot push a long-lived item out.

Redis maxmemory evictionDatabases

With maxmemory-policy allkeys-lru, Redis has to pick a victim without keeping a global recency list - the pointers per key would cost more memory than they save. Instead each object carries a small last-access clock, and on eviction Redis samples a handful of random keys (maxmemory-samples, 5 by default) and drops the oldest of those, keeping the best candidates across rounds in a pool. It is approximate LRU bought with a timestamp per key instead of a list.

The Linux page cacheOperating systems

The kernel cannot touch a list on every page access, so it keeps two lists, inactive and active, and a referenced bit per page. A page reaches the active list only on a second reference, and reclaim always takes from the tail of the inactive list. It approximates recency with list moves that happen rarely rather than on every read, and the two-list split is what stops a single large file read from evicting everything.

Caffeine, the Java caching libraryDeveloper tools

Caffeine backs Guava-style caches and Spring's cache abstraction, and it decides admission with W-TinyLFU: a compact frequency sketch estimates how often each key has been seen, and a new entry is only let in if its estimate beats the entry that would be evicted. So it uses recency for ordering and frequency as a filter, which is the practical answer to LRU losing to scans and LFU clinging to stale winners.

Why it works this way

Why a doubly linked list and not a singly linked one?

The map hands you the node itself, but unlinking a node from a singly linked list needs the node before it, and finding that means walking from the head. That is O(n) on every hit, which throws away the whole point. With prev and next a node detaches itself in two pointer writes. A permanent sentinel head and tail also help: with them, addFirst and unlink never have to ask whether this node is the first or last one.

Why every node stores its key as well as its value

The map goes key to node, so nothing in the node is needed to look it up, and storing the key looks redundant. Then capacity is exceeded, you pull the tail node off the list, and you have to delete its entry from the map with only the node in hand. Without node.key the only way to find that entry is to scan the whole map. Leaving the key out is a classic first attempt, and it turns eviction from O(1) into O(n).

A read counts as a use, and forgetting that makes it a FIFO

If get returns the value without moving the node to the head, eviction order becomes insertion order and the cache is a queue, not an LRU. It is easy to miss because a test that inserts each key once and reads it once passes either way. The case that separates them: capacity 3, put a, b, c, then get a, then put d. LRU evicts b, a queue evicts the key you just read.

One loop larger than the cache wipes it out

Scan capacity + 1 keys in a cycle and every single access misses: the key you are about to need next is always the oldest, so it was evicted one step ago. Pure LRU scores zero here while random eviction would still hit sometimes. The LFU in this lesson does no better on this exact pattern, because every key ends up with the same count and the tie falls back to recency. What LFU does survive is the other shape, a one-off burst of fresh keys washing past a working set that already has counts behind it. That is why production caches rarely run either policy unmodified.

Read more

Next up

Queue

Enqueue, dequeue, peek

Next lesson: Queue