SpecializedData structureaka least recently used cache

LRU Cache

A fixed-capacity key-value store that evicts the least recently used entry, with O(1) get and put via a hash map plus a doubly linked list.

▶ Visualize Pattern: Hashing Practice (3)

Progress

Definition

An LRU cache holds at most capacity key-value pairs. get(key) returns the value (or a miss) and marks the key as most recently used; put(key, value) inserts or updates and, if the capacity is exceeded, evicts the entry that was used longest ago.

The classic implementation combines a Hash Map for O(1) key lookup with a Doubly Linked List ordered by recency: the head is the most recent, the tail is the least recent. The map stores pointers to list nodes, so any node can be unlinked and moved to the head in O(1); eviction pops the tail.

Python's OrderedDict and Java's LinkedHashMap(accessOrder=true) implement exactly this structure; JavaScript's Map preserves insertion order, so delete-and-reinsert gives the same effect. In interviews, though, you are expected to build the list by hand.

cache evictionhash map + linked listO(1) get/putdesignordered dict

Intuition

A mental model before the formal terms.

A stack of papers on a desk with limited space. Every time you read a paper you put it on top. When a new paper arrives and the desk is full, you throw away the one at the bottom — nobody has touched it in the longest time. The hash map is a sticky-note index telling you exactly where in the stack each paper is, so you can pull it out without rummaging.

How it works

Create two sentinel nodes head and tail linked together so the list is never empty; real nodes live between them. This removes every null check.
get(key): if key not in map → miss. Else node = map[key]; unlink node; insert it right after head; return node.value.
put(key, value): if key exists, update the value and move the node to the front. Otherwise create a node, insert after head, store in map. If map.size > capacity, remove the node before tail from both the list and the map.
unlink(node): node.prev.next = node.next; node.next.prev = node.prev.
insertFront(node): node.next = head.next; node.prev = head; head.next.prev = node; head.next = node.
Both operations touch a constant number of pointers and one hash-map operation, so they are O(1).

Why it works

The list order is an exact record of access recency: every access moves a node to the front, so the tail is always the least recently accessed.

A doubly linked list is needed (not singly) because unlinking an arbitrary node in O(1) requires access to its predecessor.

The map guarantees O(1) node lookup; without it, finding a key would take O(n) list traversal.

Operations

Operation	Description	Cost
get(key)	Lookup via map; move node to front.	O(1)
put(key, value)	Insert/update at front; evict tail if over capacity.	O(1)
evict()	Remove the node before the tail sentinel.	O(1)
remove(key)	Unlink node and delete from map.	O(1)
size()	Map size.	O(1)

Recognition

How to tell a problem wants this.

"Design a cache with capacity c", "evict the least recently used", "O(1) get and put".
Any "most recently used first" ordering with constant-time promotion: browser tabs, MRU lists, page replacement.
Follow-ups: LFU, TTL expiry, thread safety, and write-back policies.

“have you seen this before” → Hashing “reverse a linked list” → Linked List Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

Capacity | commands — Capacity, then a pipe, then comma separated "put K V" / "get K" — e.g. "2 | put 1 1, put 2 2, get 1, put 3 3, get 2"

empty list

map (key → node)

key	value

1/18LRU cache with capacity 2. A hash map gives O(1) lookup by key; a doubly linked list orders entries by recency — head is most recently used, tail is the eviction candidate.

Hit (moved to front)InsertedEvicted (least recent)Looked up

PseudocodeLearn LRU Cache →

1get(k): if k not in map: return -1
2  move node to front (most recent); return node.value
3put(k, v): if k in map: update value; move to front
4  else: insert new node at front; map[k] = node
5    if size > capacity: evict the tail node; delete map[tail.key]

Variables

size0

capacity2

Complexity

access O(1)

search O(1)

insert O(1)

delete O(1)

Speed

Pseudocode

1map = {}; head <-> tail sentinels
2get(k): if k not in map: return -1; n = map[k]; unlink(n); insert_front(n); return n.val
3put(k, v):
4  if k in map: map[k].val = v; move to front; return
5  n = Node(k, v); insert_front(n); map[k] = n
6  if len(map) > cap: lru = tail.prev; unlink(lru); del map[lru.key]

Implementation

1from collections import OrderedDict
2from typing import Generic, Hashable, Optional, TypeVar
3 
4K = TypeVar("K", bound=Hashable)
5V = TypeVar("V")
6 
7 
8class LRUCache(Generic[K, V]):
9    """collections.OrderedDict already implements exactly what LRU needs:
10    O(1) lookup plus O(1) move-to-end and pop-from-front."""
11 
121 · State — an insertion-ordered OrderedDict is both the index and the recency list
13    def __init__(self, capacity: int):
14        self.cap = capacity
15        self.od: OrderedDict[K, V] = OrderedDict()
16 
172 · get — look up, move to most-recent end, return value
18    def get(self, key: K) -> Optional[V]:
19        if key not in self.od:
20            return None
21        self.od.move_to_end(key)  # O(1): relinks the entry, no rehash
22        return self.od[key]
23 
243 · put — update existing (move to end) or insert new
25    def put(self, key: K, val: V) -> None:
26        self.od[key] = val
27        self.od.move_to_end(key)
284 · Evict least-recently-used (front of the OrderedDict) when over capacity
29        if len(self.od) > self.cap:
30            self.od.popitem(last=False)
31 
325 · Size
33    def __len__(self) -> int:
34        return len(self.od)

Walkthrough

collections.OrderedDict already implements the LRU structure — a hash map fused with a doubly linked list — so the cache is a thin wrapper; this is the version to use outside interviews.
get checks membership, then move_to_end(key) relinks the entry to the most-recent end in O(1) without rehashing.
put assigns the value and moves the key to the end, so updates and inserts both count as a use.
When the dict grows past cap, popitem(last=False) removes the entry at the front — the least recently used.
__len__ makes len(cache) work.

Complexity (this implementation)

time O(1) per get/put · space O(capacity)

Language notes

OrderedDict.move_to_end(key) and popitem(last=False) are the two operations plain dict lacks — plain dict preserves insertion order since 3.7 but can only emulate them with delete + reinsert.
functools.lru_cache is the decorator form for memoising a function — it is not a general key/value cache.
The generics (Generic[K, V], K bound to Hashable) are purely static; at runtime any hashable key works.
In an interview say "in production I would use OrderedDict", then write the dict + hand-rolled doubly-linked-list version (see alternative).

Common mistakes in this language

Reimplementing the linked list in production code where OrderedDict (or functools.lru_cache) already exists.
Forgetting move_to_end in get — lookups then stop refreshing recency and the eviction order is wrong.
Calling popitem() without last=False — that evicts the most recent entry instead of the least recent.

Language differences that matter here

C++ uses std::list + unordered_map of iterators because splice gives O(1) relinking with stable iterators — nothing in JS/TS/Python offers that combination directly.
JS/TS Map preserves insertion order, so delete + re-set is the idiomatic LRU trick; the explicit doubly linked list is what interviews usually ask you to write.
Python's OrderedDict implements the structure outright (move_to_end, popitem(last=False)); the hand-rolled list survives only as the interview exercise.
Miss signalling: C++ std::optional, TS V | undefined, Python None; the JS version returns -1 to match the classic LeetCode contract.
Object keys: JS/TS Map and Python dict accept any hashable/any value; C++ unordered_map needs std::hash<K> — custom key types require a hasher.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	By key via hash map.
Search	O(1)	O(n)	Hash-map worst case with collisions.
Insert	O(1)	O(1)
Delete	O(1)	O(1)	Eviction of the tail or explicit removal.
Update	O(1)	O(1)
Get	O(1)	O(1)
Put	O(1)	O(1)
Evict	O(1)	O(1)
Space	O(capacity)

Advantages & disadvantages

Advantages

O(1) for every operation.
Simple, well-known, and built into most standard libraries.
Good hit rates for workloads with temporal locality.

Disadvantages

Per-entry overhead of two pointers plus a map entry.
A single sequential scan larger than the cache flushes everything useful (scan pollution) — LFU Cache or ARC resist this better.
Not thread-safe without locking; the global list becomes a contention point.

Use cases

CPU/OS page replacement approximations, database buffer pools.
Memoization with bounded memory (functools.lru_cache).
HTTP and CDN caches, DNS resolvers.
Browser back/forward and recently-opened-files lists.

Use it when

Bounded caches where recent access predicts future access.
Interview "design" questions asking for O(1) get/put.
Memoization with a memory cap.

Avoid it when

Access frequency matters more than recency (hot keys hit rarely but often) — use an LFU Cache.
Workloads with large sequential scans that evict the working set — consider ARC or 2Q.
Entries need time-based expiry — add a TTL field or use a heap of expiry times.

Alternatives

LFU Cache Hash Map Doubly Linked List Deque

Common mistakes

Forgetting to move the node to the front on get, not just on put.
Updating an existing key's value without also refreshing its recency.
Evicting before inserting when the key already exists, shrinking the cache unnecessarily.
Using a singly linked list and paying O(n) to unlink.
Not deleting the evicted key from the map, leaking memory and returning stale nodes.
Skipping sentinel nodes and then mishandling empty-list or single-node edge cases.

Interview patterns

LRU Cache (LeetCode 146) — the canonical hash map + doubly linked list problem.
Follow-up: make it an LFU cache (frequency buckets, each an LRU list).
Follow-up: thread safety (lock striping) and distributed caches.
Design a browser history with back/forward — same list mechanics.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Hash map or array?Beginner
Array versus linked listBeginner

Mock interviews

Two SumBeginner
Longest Substring Without Repeating CharactersIntermediate
Subarray Sum Equals KIntermediate

Interview problems

Design HashMapeasy Insert Delete GetRandom O(1)medium LRU Cachemedium

Don't delegate understanding

The manifesto →

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related