Data Structures
LRU Cache (Hash Map + DLL)
Difficulty: Intermediate
Hold a fixed number of recently used items, evict the least-recently-touched one when you run out of room, and answer both get(key) and put(key, value) in O(1). No single primitive does that: a hash map gives O(1) lookup but no recency...
LRU Cache (Hash Map + DLL)
Hold a fixed number of recently used items, evict the least-recently-touched one when you run out of room, and answer both get(key) and put(key, value) in O(1). No single primitive does that: a hash map gives O(1) lookup but no recency order, and a doubly linked list gives O(1) recency moves but no key index. The classical LRU Cache wires the two together so each compensates for what the other lacks.
This lesson designs the composite from scratch: a hash map that points keys to DLL nodes, and a doubly linked list that orders nodes by recency with most-recent at the head and least-recent at the tail. You will trace get and put through both structures, handle the capacity-of-one and update-existing-key edge cases, and see why this design appears in browser caches, database query caches, OS page replacement, and CDNs.
In Hash Map (Dictionary) Basics, you used a hash map for O(1) lookup by key. Doubly Linked List added the prev pointer that makes mid-list deletion O(1) once you hold the node, plus the sentinel pattern that erases null checks at the boundaries; both are load-bearing here.
The LRU pattern (one structure for indexing, another for ordering, kept consistent on every operation) is the gateway to a wider family of composite designs covered in later lessons.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain why caching matters and how the LRU eviction policy decides which item to remove when the cache is full.
Design an LRU Cache using a hash map for O(1) lookup and a doubly linked list for O(1) removal and insertion.
Implement get(key) that returns the value in O(1) and moves the accessed entry to the front (most recently used).
Implement put(key, value) that inserts or updates in O(1), evicting the least recently used entry when at capacity.
Trace LRU Cache operations step by step, predicting the state of both the hash map and the doubly linked list after each get/put.
Identify real-world applications of LRU caching and compare LRU with other eviction policies like LFU and FIFO.
Why This Matters
01
LRU Cache is one of the most frequently asked interview questions at top tech companies. It elegantly combines two data structures -- a hash map and a doubly linked list -- to achieve O(1) for both get and put, making it a perfect test of data structure design skills.
02
Caching is fundamental to every layer of software: CPU caches use LRU-like policies, operating systems use it for page replacement, databases cache query results, and CDNs cache web assets. Understanding LRU gives you insight into real-world performance optimization.
03
Building an LRU Cache exercises critical skills: designing composite data structures, managing pointer manipulation in a doubly linked list, and reasoning about edge cases (empty cache, capacity of 1, update vs insert).
04
The sentinel node pattern introduced in the Doubly Linked List lesson pays off here -- it eliminates all null-check edge cases in the move-to-front and eviction logic, producing clean, bug-free code.
Key Terms
8 terms you'll encounter in this lesson
Cache
A fast-access storage layer that keeps frequently or recently used data close at hand, reducing the need to fetch from a slower source. Caches trade memory for speed.
Cache Hit
When the requested data is found in the cache, avoiding a trip to the slower backing store. A high hit rate means the cache is effective.
Cache Miss
When the requested data is not in the cache, requiring a fetch from the slower source and potentially inserting the data into the cache.
LRU (Least Recently Used)
An eviction policy that removes the item that has gone the longest without being accessed. The idea is that recently used items are more likely to be used again soon.
Eviction
The process of removing an entry from the cache when it reaches capacity. The eviction policy (LRU, LFU, FIFO, etc.) determines which entry is removed.
Sentinel Node
A dummy head and/or tail node in a doubly linked list that contains no real data. Sentinels eliminate null-check edge cases in insert and delete operations.
Move to Front
The operation of removing a node from its current position in the doubly linked list and re-inserting it right after the head sentinel, marking it as the most recently used.
Capacity
The maximum number of entries the cache can hold. When size reaches capacity and a new entry must be added, the LRU entry is evicted first.
Heads Up
Common misconceptions to watch out for
"A singly linked list works just as well for LRU"
A singly linked list cannot delete a node in O(1) because you need the previous node's pointer to rewire next. A doubly linked list gives you the prev pointer, enabling O(1) removal when you have a direct reference to the node (which the hash map provides).
"get() only reads the value -- it does not change the cache"
A get() that finds the key is a cache hit, so the entry must be moved to the front of the DLL to mark it as most recently used. Without this update, the eviction order would be wrong.
"put() always increases the cache size by 1"
If the key already exists, put() updates the value and moves the node to the front without increasing size. Only a brand-new key increases size (and may trigger eviction if at capacity).
"The hash map stores the key-value pair directly"
The hash map stores a reference (pointer) to the DLL node, not just the value. This reference is what enables O(1) removal: map.get(key) gives you the node, and you can unlink it from the DLL immediately.