Two structures, because neither alone gives you both operations in O(1). A hash map for lookup by key, and a doubly linked list for recency order — the map stores the node, so touching an entry unlinks and relinks it in constant time, and eviction is whatever sits at the tail.
Overview
The requirement
A cache holding at most capacity items, evicting the least recently used when full, with O(1)get and put.
That complexity requirement is what makes it a design question rather than a coding exercise. Two operations must both be constant time:
Find an item by key — a hash table. Reorder items by recency, and remove the oldest — a doubly linked list.
Neither structure alone suffices. A hash table has no order; a linked list has no lookup. The answer is to use both, with the hash table storing pointers into the list.
Structure alone
Problem
Dict only
No order — finding the oldest is O(n)
List only
No lookup — finding a key is O(n)
Sorted structure
Reordering is O(log n), not O(1)
Dict + doubly linked list
Both O(1)
Dicts, sets & hashingCoding problemHard
Step through it
What to watch
A get is not read-only — it changes the order.
Eviction always takes the oldest, which is why order must be maintained.
The map stores the node, which is what makes unlinking O(1).
Say this out loud
"Hash map plus doubly linked list. The map gives O(1) lookup and holds the node itself, so I can unlink it in O(1) without scanning. Most recent at the head, evict from the tail. In Python I'd reach for OrderedDict and move_to_end."
Design an LRU cache
Design a cache with O(1) get and put that evicts the least recently used entry.
Run it
The from-scratch version with sentinel nodes, the OrderedDict version, and both run through the same sequence of operations so their answers can be compared.
1Python
from collections import OrderedDict
ops = [("put", "a", 1), ("put", "b", 2), ("get", "a", None),
("put", "c", 3), ("get", "b", None), ("get", "c", None), ("get", "a", None)]
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # key -> NODE, not key -> value
# Sentinels, so no insert or remove is ever a special case.
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
self.evictions = []
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.next, node.prev = self.head.next, self.head
self.head.next.prev = self.head.next = node
def get(self, key):
node = self.map.get(key)
if node is None:
return -1
self._unlink(node) # a get CHANGES the order
self._push_front(node)
return node.value
def put(self, key, value):
node = self.map.get(key)
if node:
node.value = value
self._unlink(node)
self._push_front(node)
return
node = Node(key, value)
self.map[key] = node
self._push_front(node)
if len(self.map) > self.capacity:
oldest = self.tail.prev # O(1): no scan needed
self._unlink(oldest)
del self.map[oldest.key]
self.evictions.append(oldest.key)
c = LRUCache(2)
c.put("a",1); c.put("b",2); c.get("a"); c.put("c",3)
print("hand-rolled -> a:", c.get("a"), "b:", c.get("b"), "(evicted)")
Output
2Python
from collections import OrderedDict
ops = [("put", "a", 1), ("put", "b", 2), ("get", "a", None),
("put", "c", 3), ("get", "b", None), ("get", "c", None), ("get", "a", None)]
class LRUOrderedDict:
"""The same thing, using the structure the standard library already has."""
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
self.evictions = []
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.evictions.append(self.data.popitem(last=False)[0])
c = LRUOrderedDict(2)
c.put("a",1); c.put("b",2); c.get("a"); c.put("c",3)
print("OrderedDict -> a:", c.get("a"), "b:", c.get("b"), "(evicted)")
Output
The implementation
3Python
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.map = {} # key -> Node
self.head = Node() # sentinel: most recent side
self.tail = Node() # sentinel: least recent side
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node) # mark as most recent
return node.value
def put(self, key, value):
if key in self.map:
node = self.map[key]
node.value = value
self._remove(node)
self._add_front(node)
return
if len(self.map) >= self.cap:
lru = self.tail.prev # least recently used
self._remove(lru)
del self.map[lru.key] # remove from BOTH structures
node = Node(key, value)
self.map[key] = node
self._add_front(node)
c = LRUCache(2)
c.put(1, "a"); c.put(2, "b")
print("get 1 :", c.get(1)) # touches 1, so 2 is now least recent
c.put(3, "c") # evicts 2
print("get 2 :", c.get(2), "<- evicted")
print("get 3 :", c.get(3))
Output
The line to point at is del self.map[lru.key]. Evicting from the list without removing from the dictionary leaves a dangling entry, and the cache reports hits for items it has discarded. That is why the node stores its own key — the list gives you the node, and you need the key to clean up the map.
Why one structure is not enough
A dictionary gives O(1) lookup and knows nothing about order. A list keeps order and needs O(n) to find and remove an arbitrary element. The requirement is both at once, so you carry both.
The join between them is the important part: the map's value is not the cached value, it is the node in the linked list. That is what lets you go from a key straight to its position and unlink it without walking anything.
Why the list must be doubly linked
To move a node to the front on access, it must be unlinked from its current position — which requires knowing its predecessor.
In a singly linked list, finding the predecessor means walking from the head: O(n). A doubly linked list stores prev, so unlinking is four pointer assignments and O(1).
That is the specific reason for the "doubly" in the answer, and being able to say it is what distinguishes understanding from recall.
The other implementation detail worth building in from the start is sentinel nodes — a dummy head and tail. They remove every special case for inserting at the front, removing from the back, and handling an empty list, which is where a hand-rolled version usually breaks.
The Python answer
collections.OrderedDict is exactly a dict plus a doubly linked list, and it exposes move_to_end and popitem(last=False). That is the version to write in real code, and the ten-line implementation is a fine answer if you can also explain what it is doing underneath.
Say which one the interviewer wants. "Implement it from scratch" means the nodes; "use it" means OrderedDict, or functools.lru_cache if it is memoisation rather than a cache you control.
The Python shortcut
OrderedDict maintains insertion order with O(1) reordering, which collapses the whole implementation:
4Python
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.od = OrderedDict()
def get(self, key):
if key not in self.od:
return -1
self.od.move_to_end(key) # mark as most recent
return self.od[key]
def put(self, key, value):
if key in self.od:
self.od.move_to_end(key)
self.od[key] = value
if len(self.od) > self.cap:
self.od.popitem(last=False) # evict the oldest
c = LRUCache(2)
c.put(1, "a"); c.put(2, "b")
print("get 1 :", c.get(1))
c.put(3, "c")
print("get 2 :", c.get(2), "<- evicted")
print("get 3 :", c.get(3))
Output
move_to_end and popitem(last=False) are both O(1), because OrderedDict is itself a dict plus a doubly linked list — the same design, provided by the standard library.
In an interview, write the manual version unless told otherwise; the question is about the data structure choice. Mentioning OrderedDict afterwards shows you know the library, and mentioning functools.lru_cache — which is a C implementation of this for function memoisation — shows you know where it is already used.
Eviction policies
LRU is one choice among several, and knowing the alternatives is a common follow-up.
Policy
Evicts
Good when
LRU
Least recently used
Recent access predicts future access
LFU
Least frequently used
Some items are persistently popular
FIFO
Oldest inserted
Simple; access does not matter
MRU
Most recently used
Sequential scans that will not revisit
Random
An arbitrary item
Cheap, and surprisingly competitive
TTL
Anything expired
Freshness matters more than recency
ARC / 2Q
Adaptive between recency and frequency
Mixed workloads
LRU's weakness is a sequential scan larger than the cache: it evicts everything useful while caching items that will never be read again. That is the case LFU and the adaptive policies exist to handle, and databases use variants of 2Q or ARC for exactly this reason.
LFU's weakness is the mirror image: an item popular once stays cached forever unless counts decay.
Making it production-ready
An interview answer stops at the data structure. The follow-up questions usually go here:
Thread safety. Every operation mutates both structures, so concurrent access needs a lock — and a single lock makes the cache a contention point. Sharding by key hash into several independently-locked caches is the standard fix.
Memory limits by size, not count. Real caches bound total bytes, so each entry carries a size and eviction continues until the total fits.
TTL alongside LRU. Entries expire on time as well as on pressure, which usually means a lazy check on access plus a background sweep.
Metrics. Hit rate is the number that justifies the cache's existence, and eviction rate indicates whether it is too small.
Distributed caching. Once there are several machines, consistent hashing decides which node owns a key, and invalidation becomes the hard problem.
Questions people ask
Why not a singly linked list? Unlinking a node needs its predecessor, which costs O(n) to find without a prev pointer.
Why store the key in the node? Eviction finds the node from the list and must delete the corresponding dictionary entry.
Is OrderedDict acceptable in an interview? Mention it, and write the manual version — the question is about the design.
What is functools.lru_cache? A C implementation of exactly this, for memoising function calls. Keyed on the arguments, which must be hashable.
How do sentinels help? They remove the empty-list and first/last-element special cases that cause most pointer bugs.
When is LRU the wrong policy? Sequential scans larger than the cache, where it evicts everything useful. LFU or an adaptive policy handles that.
Recap in one screen
Hash table for O(1) lookup, doubly linked list for O(1) reordering and eviction — neither works alone.
The list must be doubly linked because unlinking a node requires its predecessor.
Use sentinel head and tail nodes to eliminate boundary special cases.
On eviction, remove from both the list and the dictionary — hence storing the key in the node.
OrderedDict and functools.lru_cache are the library versions of the same design.
How the code works
The from-scratch version with sentinel nodes, the OrderedDict version, and both run through the same sequence of operations so their answers can be compared.
How the code works
self.map = {} # key -> NODEThe join between the two structures. Storing the node rather than the value is what turns "remove this key from the order" into a pointer update instead of a scan.
self.head, self.tail = Node(), Node()Sentinels. With a real head and tail always present, unlinking never has to check for None — the same trick as the dummy head in a linked-list delete.
get() calls _unlink then _push_frontA read mutates the structure. That surprises people, and it is the definition of "recently used" — a cache where reads did not count would be FIFO, not LRU.
oldest = self.tail.prevEviction in O(1) because the order is maintained continuously. Searching for the least recently used at eviction time would be O(n) and defeat the whole design.
Change one thing
Change get so it does not reorder. You now have a FIFO cache, and the eviction sequence changes — run it and see.
Add a capacity=0 case. Every put should evict immediately; most implementations crash.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Why does an LRU cache need a doubly linked list rather than a singly linked one?
With only forward pointers you would have to scan to find the node before, which is O(n) and defeats the requirement.
What does the hash map store as its value?
Storing the node is what lets you go from a key straight to its position in the order and unlink it without walking.
Does a successful get change the cache?
That is what distinguishes LRU from FIFO. A cache where reads did not count would evict on insertion order instead.
Cheat sheet
Design an LRU cache
Two structures, because neither alone gives you both operations in O(1). A hash map for lookup by key, and a doubly linked list for recency order — the map stores the node, so touching an entry unlinks and relinks it in constant time, and eviction is whatever sits at the tail.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.