Introduction to LRU Cache
An LRU (Least Recently Used) Cache is a data structure that stores a limited number of items and automatically evicts the least recently accessed item when capacity is reached. It is one of the most commonly asked interview questions and a fundamental building block in systems where memory or storage is constrained.
The core idea is simple: every time you read or write a key, that key becomes the "most recently used." When the cache is full and you need to insert a new entry, the "least recently used" entry is removed first. This strategy assumes that items accessed recently are more likely to be accessed again soon — a principle known as temporal locality.
Why LRU Cache Matters
LRU caches are everywhere in modern software. Operating systems use them for page replacement, databases use them for buffer pools, browsers use them for caching resources, and web applications use them to cache expensive computations or API responses. Understanding how to build one from scratch teaches you about data structure trade-offs, hash maps, and linked lists — all in a single problem.
Without an eviction strategy, a cache would grow indefinitely and eventually exhaust available memory. With a poor eviction strategy, you might evict items that are still needed, causing cache misses and performance degradation. LRU strikes a good balance between simplicity and effectiveness for most workloads.
Understanding the Requirements
Before writing any code, let's define what a correct LRU cache must do. A typical LRU cache supports two primary operations:
get(key)— Returns the value associated with the key if it exists, otherwise returns -1 (or null). Accessing a key marks it as recently used.put(key, value)— Inserts or updates the key-value pair. If the cache is at capacity and the key is new, evicts the least recently used item before inserting.
Both operations must run in O(1) average time complexity. This is the key constraint that determines our choice of data structures.
Choosing the Right Data Structures
A naive approach — using only an array — would require O(n) time to find and move elements, which is too slow. To achieve O(1) for both operations, we combine two data structures:
- Hash Map (Map) — Provides
O(1)lookup from key to the corresponding node in the linked list. - Doubly Linked List — Allows
O(1)insertion and removal of nodes when we already have a reference to them. We maintain the list in order of recency: most recently used at the head, least recently used at the tail.
The hash map gives us instant access to any node, and the doubly linked list lets us reorder nodes in constant time by adjusting pointers.
Implementing the Doubly Linked List Node
First, we need a node class to represent each entry in our doubly linked list. Each node stores a key, a value, and pointers to the previous and next nodes.
class DLLNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
We store the key inside the node (not just the value) because when we evict the tail node, we need to know which key to remove from the hash map. Without storing the key, we would have no way to clean up the map entry.
Building the LRU Cache Class
Now let's build the main LRUCache class. We initialize it with a capacity, an empty Map, and two sentinel nodes — head and tail — that act as boundaries. Using sentinel nodes simplifies pointer manipulation because we never have to handle null checks for edge cases at the boundaries.
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
// Sentinel nodes
this.head = new DLLNode(null, null); // Most recently used side
this.tail = new DLLNode(null, null); // Least recently used side
this.head.next = this.tail;
this.tail.prev = this.head;
}
The head sentinel represents the "most recently used" boundary, and the tail sentinel represents the "least recently used" boundary. Real data nodes always live between these two sentinels.
Helper Methods for List Manipulation
To keep our code clean, we'll write two helper methods: one to add a node right after the head (marking it most recently used), and one to remove a node from its current position in the list.
// Remove a node from the linked list
removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// Add a node right after head (most recently used position)
addToHead(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
These two operations are the foundation of all recency updates. Whenever a node is accessed or created, we remove it from its current position and add it to the head.
Implementing the Get Operation
The get method checks if the key exists in the map. If it does, it retrieves the node, moves it to the head (since it is now the most recently used), and returns its value. If the key does not exist, it returns -1.
get(key) {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key);
// Move the accessed node to the head (most recently used)
this.removeNode(node);
this.addToHead(node);
return node.value;
}
Notice that even a read operation modifies the internal order of the linked list. This is essential because "recently used" includes both reads and writes, not just writes.
Implementing the Put Operation
The put method has two cases. If the key already exists, we update the value and move the node to the head. If the key is new, we create a new node, add it to the head, and store it in the map. If this causes the cache to exceed capacity, we evict the least recently used node — the one right before the tail sentinel.
put(key, value) {
if (this.cache.has(key)) {
// Key exists: update value and move to head
const node = this.cache.get(key);
node.value = value;
this.removeNode(node);
this.addToHead(node);
} else {
// New key: create node
const newNode = new DLLNode(key, value);
this.cache.set(key, newNode);
this.addToHead(newNode);
// Evict least recently used if over capacity
if (this.cache.size > this.capacity) {
const lruNode = this.tail.prev;
this.removeNode(lruNode);
this.cache.delete(lruNode.key);
}
}
}
}
The eviction step is critical. We grab the node just before the tail sentinel (the least recently used), remove it from the linked list, and delete its key from the map. This keeps both data structures in sync.
Complete Implementation
Here is the full, ready-to-use implementation in one block:
class DLLNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
this.head = new DLLNode(null, null);
this.tail = new DLLNode(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
addToHead(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key);
this.removeNode(node);
this.addToHead(node);
return node.value;
}
put(key, value) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.value = value;
this.removeNode(node);
this.addToHead(node);
} else {
const newNode = new DLLNode(key, value);
this.cache.set(key, newNode);
this.addToHead(newNode);
if (this.cache.size > this.capacity) {
const lruNode = this.tail.prev;
this.removeNode(lruNode);
this.cache.delete(lruNode.key);
}
}
}
}
Testing the Implementation
Let's verify our implementation with a practical example. We'll create a cache with capacity 2 and perform a series of operations to confirm correct eviction behavior.
const cache = new LRUCache(2);
cache.put(1, 1); // Cache: {1=1}
cache.put(2, 2); // Cache: {2=2, 1=1}
console.log(cache.get(1)); // Returns 1, Cache: {1=1, 2=2}
cache.put(3, 3); // Evicts key 2, Cache: {3=3, 1=1}
console.log(cache.get(2)); // Returns -1 (not found)
cache.put(4, 4); // Evicts key 1, Cache: {4=4, 3=3}
console.log(cache.get(1)); // Returns -1 (not found)
console.log(cache.get(3)); // Returns 3, Cache: {3=3, 4=4}
console.log(cache.get(4)); // Returns 4, Cache: {4=4, 3=3}
Trace through the operations carefully. After get(1) is called, key 1 becomes most recently used, so when put(3, 3) triggers an eviction, key 2 (not key 1) is evicted. This demonstrates that reads affect eviction order — a common source of bugs if overlooked.
Using JavaScript's Built-in Map for a Simpler Implementation
JavaScript's Map object maintains insertion order and iterates entries in the order they were added. We can leverage this to build a simpler LRU cache without an explicit doubly linked list. The trick is to delete and re-insert a key every time it is accessed, which moves it to the "end" of the iteration order. The first entry in iteration order is then the least recently used.
class SimpleLRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
const value = this.cache.get(key);
// Re-insert to mark as most recently used
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// Evict the first entry (least recently used)
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
this.cache.set(key, value);
}
}
This version is much shorter and easier to reason about. However, the delete and set combination on every access is slightly less efficient than the doubly linked list approach, since Map internally does more bookkeeping. For most practical applications, this difference is negligible, and the simpler implementation is preferable.
Best Practices
When implementing or using an LRU cache in production code, keep the following best practices in mind:
- Choose the right capacity. A cache that is too small will have frequent evictions and low hit rates. A cache that is too large wastes memory. Profile your workload to find the sweet spot.
- Consider TTL alongside LRU. LRU only evicts based on access patterns. Combining it with a time-to-live (TTL) ensures stale entries are removed even if the cache is not full.
- Make the cache generic. Instead of hardcoding value types, design your cache to work with any key-value pair. This improves reusability across your application.
- Handle edge cases. Always validate that capacity is a positive integer. A capacity of zero means no caching should occur, and your code should handle this gracefully.
- Monitor cache hit rates. In production, instrument your cache to track hits and misses. A consistently low hit rate may indicate that your capacity is too small or that LRU is the wrong eviction policy for your access pattern.
- Be aware of concurrency. The implementations above are not thread-safe. In a multi-threaded environment (such as Node.js worker threads), you would need locking or a concurrent data structure.
Conclusion
Implementing an LRU cache in JavaScript is an excellent exercise that combines hash maps and doubly linked lists to achieve constant-time operations. The classic approach using a Map plus a doubly linked list with sentinel nodes gives you full control and optimal performance, while the simpler Map-only approach leverages JavaScript's built-in iteration ordering for cleaner code. Whichever approach you choose, understanding the mechanics behind eviction, recency tracking, and the interaction between the two data structures will make you a stronger developer — both in interviews and in real-world system design.