Introduction to LRU Cache
An LRU (Least Recently Used) cache is a popular eviction policy used in caching systems to manage limited memory. When the cache reaches its capacity, the least recently accessed item is removed to make room for a new one. This strategy is based on the principle of locality — items accessed recently are likely to be accessed again soon.
LRU caches are everywhere: operating system page replacement, database query caches, browser caches, and in-memory data stores like Redis. Understanding how to implement one is a common interview question and a fundamental skill for any backend developer.
Why LRU Cache Matters
Without caching, every request for data would require a costly operation — a database query, a network call, or a disk read. Caching mitigates this, but caches have finite size. When full, you need a policy to decide what to evict. LRU is one of the most effective because:
- Predictable performance: It guarantees O(1) time complexity for both get and put operations when implemented correctly.
- Simple heuristic: It uses access recency as the eviction signal, which works well for most real-world workloads.
- Wide applicability: From CPU caches to web proxies, LRU is a sensible default.
Designing the Data Structure
The key challenge is achieving O(1) time for both get and put. A naive list-based approach would require O(n) search. The standard solution combines two data structures:
- Hash map (dictionary): Maps keys to nodes, giving O(1) lookup.
- Doubly linked list: Maintains order of usage. The most recently used item is at the head; the least recently used is at the tail. Doubly linked nodes allow O(1) removal and insertion.
Together, the hash map finds the node in O(1), and the linked list reorders it in O(1).
Node Structure
Each node in the doubly linked list stores the key, value, and pointers to the previous and next nodes. Storing the key inside the node is important — when evicting the tail node, we need its key to remove the corresponding entry from the hash map.
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
Step-by-Step Implementation
Below is a complete implementation of an LRU cache from scratch. We use sentinel head and tail nodes to simplify boundary conditions — we never need to check whether a node is at the boundary of the list.
1. Initialize the Cache
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> DLinkedNode
self.size = 0
# Sentinel nodes
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
2. Helper Methods for the Linked List
We define two private helpers: one to remove a node from the list, and one to insert a node right after the head (marking it as most recently used).
def _remove_node(self, node):
"""Remove an existing node from the linked list."""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _add_to_head(self, node):
"""Insert a node right after the head (most recently used)."""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
3. Implementing the Get Operation
When a key is requested, we look it up in the hash map. If found, we move the corresponding node to the head of the list (since it is now the most recently used) and return its value. If not found, return -1.
def get(self, key: int) -> int:
node = self.cache.get(key)
if not node:
return -1
# Move the accessed node to the head
self._remove_node(node)
self._add_to_head(node)
return node.value
4. Implementing the Put Operation
The put operation has two cases. If the key already exists, update its value and move the node to the head. If it does not exist, create a new node, add it to the head and the hash map, and increment the size. If the size exceeds capacity, evict the tail's previous node (the least recently used) from both the list and the hash map.
def put(self, key: int, value: int) -> None:
node = self.cache.get(key)
if node:
# Update the value and move to head
node.value = value
self._remove_node(node)
self._add_to_head(node)
else:
new_node = DLinkedNode(key, value)
self.cache[key] = new_node
self._add_to_head(new_node)
self.size += 1
if self.size > self.capacity:
# Evict the least recently used node (tail.prev)
lru = self.tail.prev
self._remove_node(lru)
del self.cache[lru.key]
self.size -= 1
5. Putting It All Together
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.size = 0
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def _remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
node = self.cache.get(key)
if not node:
return -1
self._remove_node(node)
self._add_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.cache.get(key)
if node:
node.value = value
self._remove_node(node)
self._add_to_head(node)
else:
new_node = DLinkedNode(key, value)
self.cache[key] = new_node
self._add_to_head(new_node)
self.size += 1
if self.size > self.capacity:
lru = self.tail.prev
self._remove_node(lru)
del self.cache[lru.key]
self.size -= 1
# Example usage
if __name__ == "__main__":
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1)) # returns 1
lru.put(3, 3) # evicts key 2
print(lru.get(2)) # returns -1 (not found)
lru.put(4, 4) # evicts key 1
print(lru.get(1)) # returns -1
print(lru.get(3)) # returns 3
print(lru.get(4)) # returns 4
Using Python's Built-in OrderedDict
Python's standard library provides collections.OrderedDict, which remembers insertion order and supports moving keys to the end. This makes implementing an LRU cache trivial and concise.
from collections import OrderedDict
class LRUCacheOrdered:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # Mark as most recently used
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove least recently used
This version is shorter, less error-prone, and leverages C-optimized internals for better performance in most cases. For production code, prefer this approach unless you have a specific reason to implement the data structure manually.
Using functools.lru_cache for Function-Level Caching
If your goal is to cache the results of a function rather than build a general-purpose cache, Python's functools.lru_cache decorator is the right tool. It automatically manages an LRU cache keyed by the function arguments.
from functools import lru_cache
@lru_cache(maxsize=128)
def expensive_computation(n: int) -> int:
print(f"Computing for {n}")
# Simulate expensive work
result = sum(i * i for i in range(n))
return result
print(expensive_computation(1000)) # Computes and caches
print(expensive_computation(1000)) # Returns cached result instantly
print(expensive_computation.cache_info())
# CacheInfo(hits=1, misses=1, maxsize=128, currsize=1)
The cache_info() method reports hits, misses, current size, and max size. You can also call cache_clear() to reset the cache. For Python 3.9 and later, functools.cache is available as a simpler alias when you want an unbounded cache.
Best Practices
- Choose the right capacity: Too small and you lose hit rate; too large and you waste memory. Measure your workload's access pattern and tune accordingly.
- Prefer standard libraries: Use
OrderedDictorfunctools.lru_cachein production. Reserve manual implementations for learning or interviews. - Make values immutable or handle carefully: If cached objects are mutable, external modifications can corrupt cache state. Consider storing copies or using immutable data types.
- Thread safety: The implementations above are not thread-safe. In concurrent environments, wrap access with a lock or use
functools.lru_cache, which is internally synchronized. - Monitor cache metrics: Track hit rate, eviction count, and memory usage. A low hit rate suggests your capacity is too small or your access pattern does not fit LRU.
- Consider alternatives: LFU (Least Frequently Used) and ARC (Adaptive Replacement Cache) can outperform LRU for certain workloads. Evaluate based on your data.
- Set TTLs when appropriate: Combine LRU with time-based expiration to prevent stale data from lingering in the cache.
Common Pitfalls
When implementing an LRU cache manually, several bugs are easy to introduce. Forgetting to store the key in the node makes eviction impossible because you cannot remove the hash map entry. Forgetting to update the size counter leads to incorrect eviction behavior. Mixing up the order of pointer reassignments in _remove_node or _add_to_head can corrupt the list. Always test edge cases: capacity of 1, evicting the only element, and updating an existing key without growing the size.
Conclusion
The LRU cache is a foundational data structure that elegantly balances simplicity and effectiveness. By combining a hash map with a doubly linked list, it achieves constant-time operations while maintaining a sensible eviction policy. Whether you implement it from scratch to deepen your understanding or rely on Python's OrderedDict and functools.lru_cache in production, mastering the LRU cache equips you with a versatile tool for building fast, memory-efficient systems. Start with the manual implementation to learn the mechanics, then graduate to the standard library for real-world projects, and always measure your cache's performance to ensure it delivers the expected benefits.