# LRU Cache
Every use moves its key to the front of a recency list, and eviction takes the tail. A hash map plus a doubly-linked list keeps both steps O(1).
**Time:** O(1)
**Space:** O(capacity)
**Difficulty:** MEDIUM
*[Interactive widget: lru-cache-visualizer (LRU Cache Visualizer) — open the HTML page]*
Canonical: https://scaleengineer.com/algorithms/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\.

*[Interactive widget: lru-cache-visualizer — open the HTML page]*

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\.

```python
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:

| Operation | Cost | Why |
| --- | --- | --- |
| `get` hit | `O(1)` | One map lookup, then unlink and push\-front\. |
| `get` miss | `O(1)` | One map lookup\. Nothing moves\. |
| `put` | `O(1)` | One map lookup, at most two unlinks and one push\-front\. |

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](/algorithms/bloom-filter) so a scan never enters the cache at all\.

*[Interactive widget: lru-cache-workload — open the HTML page]*

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](/algorithms/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\.

## Code examples

### LRU cache (Python)

```python
class Node:
    """One entry in the recency list: a key, its value, and two links."""

    def __init__(self, key: int, value: int) -> None:
        self.key = key
        self.value = value
        self.prev: "Node | None" = None
        self.next: "Node | None" = None

class LRUCache:
    """Map + doubly-linked list: O(1) get and put, evict the tail."""

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

    def _unlink(self, node: Node) -> None:
        node.prev.next = node.next  # type: ignore[union-attr]
        node.next.prev = node.prev  # type: ignore[union-attr]

    def _push_front(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node  # type: ignore[union-attr]
        self.head.next = node

    def get(self, key: int) -> int:
        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: int, value: int) -> None:
        if key in self.map:
            self._unlink(self.map[key])
        elif len(self.map) == self.capacity:
            tail = self.tail.prev
            self._unlink(tail)  # type: ignore[arg-type]
            del self.map[tail.key]  # type: ignore[union-attr]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)
```

### LRU cache (JavaScript)

```javascript
/** Map + doubly-linked list: O(1) get and put, evict the tail. */
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> node
    this.head = { key: null, value: null, prev: null, next: null };
    this.tail = { key: null, value: null, prev: null, next: null };
    this.head.next = this.tail; // sentinels bracket the list
    this.tail.prev = this.head;
  }

  _unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _pushFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;
    this._unlink(node);
    this._pushFront(node);
    return node.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this._unlink(this.map.get(key));
    } else if (this.map.size === this.capacity) {
      const tail = this.tail.prev;
      this._unlink(tail);
      this.map.delete(tail.key);
    }
    const node = { key, value, prev: null, next: null };
    this.map.set(key, node);
    this._pushFront(node);
  }
}

```

### LRU cache (Java)

```java
import java.util.HashMap;
import java.util.Map;

public class LRUCache<K, V> {
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);  // MRU side
    private final Node<K, V> tail = new Node<>(null, null);  // LRU side

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void unlink(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void pushFront(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;

        unlink(node);            // a read reorders the list
        pushFront(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            unlink(existing);
            pushFront(existing);
            return;
        }

        if (map.size() == capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);   // node carries its key
        }

        Node<K, V> node = new Node<>(key, value);
        pushFront(node);
        map.put(key, node);
    }

    public int size() { return map.size(); }
}
```

### LRU cache (C)

```c
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *key;
    int   value;
    struct Node *prev, *next;   /* recency list */
    struct Node *hnext;         /* hash bucket chain */
} Node;

typedef struct {
    Node  **buckets;
    size_t  nbuckets;           /* power of two */
    size_t  size, capacity;
    Node   *head, *tail;        /* sentinels: head->next is MRU */
} LRUCache;

static char *dup_str(const char *s) {
    size_t n = strlen(s) + 1;
    char *p = malloc(n);
    if (p) memcpy(p, s, n);
    return p;
}

static uint32_t fnv1a(const char *s) {
    uint32_t h = 0x811C9DC5u;
    for (const unsigned char *p = (const unsigned char *)s; *p; ++p) {
        h ^= *p;
        h *= 0x01000193u;
    }
    return h;
}

static size_t bucket_of(const LRUCache *c, const char *key) {
    return fnv1a(key) & (c->nbuckets - 1);
}

/* ---- recency list ---- */

static void list_unlink(Node *n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
}

static void list_push_front(LRUCache *c, Node *n) {
    n->next = c->head->next;
    n->prev = c->head;
    c->head->next->prev = n;
    c->head->next = n;
}

/* ---- hash chain ---- */

static Node *hash_find(const LRUCache *c, const char *key) {
    for (Node *n = c->buckets[bucket_of(c, key)]; n; n = n->hnext)
        if (strcmp(n->key, key) == 0) return n;
    return NULL;
}

static void hash_insert(LRUCache *c, Node *n) {
    size_t b = bucket_of(c, n->key);
    n->hnext = c->buckets[b];
    c->buckets[b] = n;
}

static void hash_unlink(LRUCache *c, Node *n) {
    /* pointer-to-pointer walk: removes without a special case for the head */
    Node **pp = &c->buckets[bucket_of(c, n->key)];
    while (*pp && *pp != n) pp = &(*pp)->hnext;
    if (*pp) *pp = n->hnext;
}

/* ---- public API ---- */

void lru_free(LRUCache *c) {
    if (!c) return;
    if (c->head) {
        Node *n = c->head->next;
        while (n && n != c->tail) {
            Node *next = n->next;
            free(n->key);
            free(n);
            n = next;
        }
    }
    free(c->head);
    free(c->tail);
    free(c->buckets);
    free(c);
}

LRUCache *lru_create(size_t capacity) {
    if (capacity == 0) return NULL;

    LRUCache *c = calloc(1, sizeof *c);
    if (!c) return NULL;

    size_t nb = 1;
    while (nb < capacity * 2) nb <<= 1;      /* keep the load factor near 0.5 */

    c->buckets = calloc(nb, sizeof *c->buckets);
    c->head    = calloc(1, sizeof *c->head);
    c->tail    = calloc(1, sizeof *c->tail);
    if (!c->buckets || !c->head || !c->tail) { lru_free(c); return NULL; }

    c->nbuckets = nb;
    c->capacity = capacity;
    c->head->next = c->tail;
    c->tail->prev = c->head;
    return c;
}

/* Returns 1 on a hit (value written to *out), 0 on a miss. */
int lru_get(LRUCache *c, const char *key, int *out) {
    Node *n = hash_find(c, key);
    if (!n) return 0;

    list_unlink(n);                 /* a read reorders the list */
    list_push_front(c, n);
    if (out) *out = n->value;
    return 1;
}

/* Returns 0 on success, -1 on allocation failure. */
int lru_put(LRUCache *c, const char *key, int value) {
    Node *n = hash_find(c, key);
    if (n) {
        n->value = value;
        list_unlink(n);
        list_push_front(c, n);
        return 0;
    }

    if (c->size == c->capacity) {
        Node *lru = c->tail->prev;  /* least recently used */
        list_unlink(lru);
        hash_unlink(c, lru);
        free(lru->key);
        free(lru);
        c->size--;
    }

    n = calloc(1, sizeof *n);
    if (!n) return -1;
    n->key = dup_str(key);
    if (!n->key) { free(n); return -1; }
    n->value = value;

    list_push_front(c, n);
    hash_insert(c, n);
    c->size++;
    return 0;
}
```

### LRU cache (CPP)

```cpp
#include <list>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>

template <typename K, typename V>
class LRUCache {
public:
    explicit LRUCache(std::size_t capacity) : capacity_(capacity) {
        if (capacity == 0) throw std::invalid_argument("capacity must be > 0");
    }

    // Returns nullptr on a miss; the pointer is valid until the entry is evicted.
    const V* get(const K& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return nullptr;

        // splice moves the node itself — iterators stay valid, nothing is copied
        items_.splice(items_.begin(), items_, it->second);
        return &it->second->second;
    }

    void put(const K& key, V value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = std::move(value);
            items_.splice(items_.begin(), items_, it->second);
            return;
        }

        if (map_.size() == capacity_) {
            map_.erase(items_.back().first);   // entry carries its key
            items_.pop_back();
        }

        items_.emplace_front(key, std::move(value));
        map_[key] = items_.begin();
    }

    std::size_t size() const { return map_.size(); }

private:
    using Item = std::pair<K, V>;

    std::size_t capacity_;
    std::list<Item> items_;                                        // front = MRU
    std::unordered_map<K, typename std::list<Item>::iterator> map_;
};
```

### LRU cache (CSharp)

```csharp
using System;
using System.Collections.Generic;

public class LRUCache<TKey, TValue>
{
    private readonly int capacity;
    private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> map;
    private readonly LinkedList<KeyValuePair<TKey, TValue>> items = new();  // First = MRU

    public LRUCache(int capacity)
    {
        if (capacity <= 0) throw new ArgumentOutOfRangeException(nameof(capacity));
        this.capacity = capacity;
        this.map = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>(capacity);
    }

    public bool TryGet(TKey key, out TValue value)
    {
        if (!map.TryGetValue(key, out var node))
        {
            value = default;
            return false;
        }

        items.Remove(node);          // O(1): we hold the node, not just the key
        items.AddFirst(node);        // a read reorders the list
        value = node.Value.Value;
        return true;
    }

    public void Put(TKey key, TValue value)
    {
        if (map.TryGetValue(key, out var existing))
        {
            items.Remove(existing);
            existing.Value = new KeyValuePair<TKey, TValue>(key, value);
            items.AddFirst(existing);
            return;
        }

        if (map.Count == capacity)
        {
            var lru = items.Last;
            items.RemoveLast();
            map.Remove(lru.Value.Key);   // entry carries its key
        }

        var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(
            new KeyValuePair<TKey, TValue>(key, value));
        items.AddFirst(node);
        map[key] = node;
    }

    public int Count => map.Count;
}
```