Project: Build an LRU Cache

Caches have a hard problem: they're finite. You can't keep everything, so when the cache fills up, something has to go. The smartest cheap guess is to throw out whatever you haven't touched in the longest time, the least recently used item, on the bet that what you've used recently you'll use again. An LRU cache does exactly that, and it's the perfect capstone for this series because it's two structures you already know, working together.

The problem: O(1) get, O(1) put, and a recency order

An LRU cache needs three operations, all fast:

• get(key) returns the value if it's there, and marks that key as just-used.
• put(key, value) stores the pair, marks it just-used, and if that pushes the cache over capacity, evicts the least-recently-used key.
• everything O(1), because a cache that's slow to read defeats the point of caching.

Two requirements pull in opposite directions. Fast lookup by key screams hash map. Tracking recency order (knowing who's stalest) screams an ordered structure. Neither alone does both: a hash map has no order, and a plain ordered list is O(n) to search. The LRU trick is to combine them so each covers the other's weakness.

Piece one: the hash map for lookup

You already know why a hash map gives O(1) lookup by key. Hashing turns the key straight into a bucket. The visualizer below is the same hashing from earlier in the series. It's the half of the LRU cache that answers "is this key here, and what's its value?" instantly.

That handles lookup. What it can't tell you is which key is the stalest, because hash maps have no inherent order. For that you need a second structure layered on top.

Piece two: an ordering structure for recency

To track recency you keep an ordered line of keys: most-recently-used at one end, least-recently-used at the other. Every time you touch a key, you move it to the recent end. Eviction is then trivial. You drop whoever's stuck at the stale end.

The textbook structure for this is a doubly linked list: O(1) to move a node to the front and O(1) to drop the node at the back, as long as you can reach any node directly (which the hash map lets you do, by storing a pointer to each key's node). The linked-list operations below, inserting at the head and removing a value, are exactly the moves an LRU cache makes to keep its recency order current.

insertHead is "mark as most-recently-used," and removing the tail value is "evict the stalest." Put together: the hash map finds a key in O(1), the linked list reorders or evicts in O(1), and a pointer from each map entry to its list node keeps them in sync. That's the classic LRU design.

The clean Python version: OrderedDict

You could hand-build that hash-map-plus-doubly-linked-list. But Python already ships the combination: collections.OrderedDict is a dict that remembers insertion order and lets you cheaply move a key to either end with move_to_end. It's literally a hash map welded to a linked list under the hood, exactly the structure we just described, done for you.

That makes a real LRU cache short and readable:

Trace the eviction. After the three puts, aarav and diya are newer than maya. Then get(\"maya\") moves maya to the recent end, so now aarav is the stalest. When kabir arrives and overflows capacity 3, popitem(last=False) drops aarav, the genuinely least-recently-used key. That get on maya is what saved it. That's LRU doing its job: recency, not insertion order, decides who survives.

You built the whole series into this

Step back and look at what just came together. The hash map gives O(1) lookup by key (lesson 4). The linked list / ordering structure tracks recency in O(1) (the structure behind move_to_end). The idea of caching a result so you never redo work is the same instinct as the memoization you just learned. And reasoning about why every operation stays O(1) is the Big-O thinking that opened the series. That's the point of data structures and algorithms: they're not trivia, they're parts you combine to build real things.

This is the last lesson. You went from "what even is Big-O" to building a production-pattern cache from first principles: arrays, hashing, recursion, trees, graphs, dynamic programming, and the judgement to pick the right one for the question. From here, the move is practice: take these on real problems and feel them become second nature.

Explore the full Data Structures & Algorithms series to revisit any piece, and if the dictionary and class syntax here needs grounding, the Python series and the Python classes lesson have you covered.