Build Your Own LRU Cache
Build the data structure that powers Redis's eviction policy, browser caches, and CDN edge nodes -- from scratch, in both JavaScript and Python.
Why build this
LRU Cache shows up in every serious system design interview for a reason: it sits at the intersection of two fundamental data structures (hashmap + doubly linked list) and requires O(1) time for both reads and writes. Most engineers can describe it; very few can implement it from scratch without bugs. The devil is in the pointer updates -- move a node to the head and you have to fix four pointers atomically, or your list is corrupt. After this track, you'll be able to implement it in any language in under 20 minutes and explain exactly why the doubly-linked list is mandatory (hint: singly-linked is O(n) for node removal). You'll also understand Redis's allkeys-lru eviction policy and why browsers use LRU for HTTP disk caches.
What you'll build
A complete LRU Cache in three stages, building from the underlying data structure up to a production-ready cache with TTL support. Stage 1 -- Doubly-Linked List: The primitive. A list where each node knows both its previous and next neighbor, enabling O(1) removal of any node and O(1) insertion at the head. This is the half of LRU that makes eviction fast. Stage 2 -- LRU Core: Combine the list with a hashmap. The hashmap gives O(1) lookup (is this key in the cache?). The list gives O(1) eviction (drop the tail) and O(1) promotion (move a node to the head on access). Together they make both get and put run in O(1) time -- the guarantee that makes LRU practical. Stage 3 -- LRU with TTL: Add time-to-live support. Each entry expires after a configurable duration. Expired entries are evicted lazily on access and don't count toward capacity. This is how Redis's EXPIRE command works layered over its LRU eviction policy.
How it works internally
Why a doubly-linked list? Eviction requires removing the tail node. In a singly-linked list, removing a node requires traversing from the head to find its predecessor -- O(n). In a doubly-linked list, the tail already knows its predecessor (node.prev), so removal is O(1): fix two pointers and you're done. This is the only reason LRU implementations use doubly-linked lists.
The O(1) proof: When you do get(key): 1. Hashmap lookup: O(1) to find the node. 2. Move to head: O(1) pointer updates (four assignments). 3. Return value: O(1). Total: O(1). When you do put(key, value): 1. Hashmap lookup: O(1) to check if key exists. 2. If exists: update value + move to head: O(1). 3. If new: create node, add to head, add to hashmap: O(1). 4. If over capacity: remove tail, remove from hashmap: O(1). Total: O(1).
Sentinel nodes (dummy head + tail): Production implementations use dummy head and tail sentinel nodes so that every real node has both a prev and next (the sentinels absorb the edge cases). Without sentinels, inserting the first node and removing the last node require special-casing that creates bugs. With sentinels, every addToHead and removeFromTail is the same three-line operation.
Redis allkeys-lru: When Redis's maxmemory is hit, the allkeys-lru policy approximates LRU by sampling N random keys (default N=5) and evicting the least recently accessed among them. Redis doesn't use an exact doubly-linked list across all keys because at billions of keys the pointer overhead dominates. The approximation is good enough: at N=10, it evicts near-optimal choices >99% of the time.
The 3 stages
Build a doubly-linked list with sentinel head and tail nodes. Implement addToHead (insert a new node after the sentinel head), removeFromTail (remove the node before the sentinel tail), and remove(node) (remove any node by fixing its neighbors' pointers). These three operations are all LRU needs.
Combine a Map (key to node) with the doubly-linked list. get moves the accessed node to the head (most recently used). put adds to the head; if over capacity, evicts the tail (least recently used). The hashmap handles lookup; the list handles eviction order.
Add a defaultTTL and optional per-put TTL. get checks expiry before returning -- expired entries are evicted lazily and return -1. put stores an expiresAt timestamp alongside each value. Expired entries don't count toward capacity, so they don't trigger eviction of live data.
You'll see this in production
When maxmemory is set, Redis uses LRU-approximation eviction. Each key stores a 24-bit LRU clock value (last access time). On eviction, Redis samples random keys and picks the one with the oldest clock. Your Stage 2 implementation is the exact algorithm -- Redis's is an approximation for scale.
Chrome's on-disk HTTP cache uses an LRU policy to decide which cached responses to evict when the cache fills. Each cached resource is a node; accessing it moves it to the front. Your Stage 3 (with TTL) is a close model -- HTTP Cache-Control max-age maps directly to your per-entry TTL.
Hardware cache lines in CPU L1 and L2 caches use LRU replacement (or pseudo-LRU) at the cache-set level. The same logic -- recently accessed lines stay, least recently used lines are evicted first -- plays out in silicon with 8-way or 16-way sets.
Memcached uses a doubly-linked list per slab class for LRU eviction -- literally the data structure you build in Stage 1. Items are moved to the head on access; the tail is evicted when memory is full.
OS and browser DNS resolvers cache responses using LRU + TTL -- your Stage 3 exactly. The DNS TTL field in each record maps to the per-entry TTL; the cache size bound triggers LRU eviction.
Before you start
- ✓JavaScript object references (nodes are objects; moving a node means changing pointers, not copying data)
- ✓What a hashmap does: O(1) key lookup
- ✓What a doubly-linked list is: each node has prev and next
- ✓Basic understanding of cache hit/miss and why caches have size limits
Stages
Ready to build?
Your code runs in the browser — no setup needed.