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.
The implementation
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:
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.