What is LRU Cache — How It Works and How to Implement It [2026]

Q: What data structures are used to implement LRU Cache in O(1)?

LRU Cache uses a HashMap (for O(1) key lookup) combined with a Doubly Linked List (for O(1) insertion and deletion of nodes). The HashMap stores key → node references so we can jump directly to any node. The Doubly Linked List maintains access order — the most recently used node sits at the head, and the least recently used sits at the tail.

Q: What is the difference between LRU and LFU cache eviction?

LRU (Least Recently Used) evicts the item that has not been accessed for the longest time, regardless of how often it was accessed overall. LFU (Least Frequently Used) evicts the item with the fewest total accesses. LRU is simpler and works well for temporal locality (recently accessed items are likely to be accessed again). LFU is better for frequency-based workloads where some items are accessed very often regardless of recency.

Q: How does Redis implement LRU eviction?

Redis does not implement a true LRU because tracking exact access order would require too much memory. Instead, Redis uses an approximated LRU: when eviction is needed, it samples a configurable number of random keys (default 5, set via maxmemory-samples) and evicts the one with the oldest access time. Increasing maxmemory-samples improves accuracy at the cost of CPU. The allkeys-lru policy applies LRU across all keys; volatile-lru applies only to keys with a TTL set.

Q: When should you NOT use LRU cache?

LRU is a poor fit when access patterns are frequency-based rather than recency-based. For example, if item A is accessed 10,000 times a day and item B was accessed just once a second ago, LRU will evict A next if B was the most recent access. Use LFU instead. Also avoid LRU for scan-heavy workloads (sequential full-table scans thrash the cache). Some databases use ARC (Adaptive Replacement Cache) which combines LRU and LFU automatically.

Q: What is the difference between LRU and FIFO cache eviction?

FIFO (First In, First Out) evicts the oldest inserted item regardless of access patterns. An item inserted first will be evicted first even if it was accessed a second ago. LRU considers recency of access, not insertion time. FIFO is simpler to implement (just a queue) but performs worse for workloads with temporal locality. LRU is almost always preferred over FIFO in production caches.

Q: What capacity should an LRU cache have?

Cache capacity depends on your access pattern and available memory. A good starting point is to profile your working set — the set of items accessed in a typical time window. If 20% of your items account for 80% of accesses (Zipf / Pareto distribution), caching 20% of the dataset gives ~80% hit rate. For Redis, start with 25-30% of your dataset size and monitor the hit rate with INFO stats keyspace_hits and keyspace_misses, then adjust.

1. What is Cache Eviction?

A cache has limited capacity. When it fills up and you need to insert a new item, you must evict (remove) an existing item to make room. The eviction policy decides which item to remove. A good eviction policy removes items that are least likely to be needed again — maximising the cache hit rate.

The most common eviction policies are:

LRU (Least Recently Used): evict the item accessed least recently — based on the assumption that recently used items will be used again soon (temporal locality).
LFU (Least Frequently Used): evict the item accessed fewest times total.
FIFO (First In, First Out): evict the oldest inserted item, regardless of access.
MRU (Most Recently Used): evict the most recently used item — useful in specific scan-once workloads.
Random: evict a random item — simple and surprisingly competitive in some workloads.

2. How LRU Cache Works

LRU maintains a strict ordering of items by recency of access. Every time you read or write an item, it moves to the "most recently used" end. When you need to evict, you remove the item at the "least recently used" end.

The challenge is implementing this with O(1) time complexity for both get (lookup by key) and put (insert and evict). A naive list would require O(n) scanning to find a key. The trick is combining two data structures:

HashMap: maps each key to its node in the linked list — O(1) lookup.
Doubly Linked List: maintains insertion order — O(1) move-to-front and remove-from-tail.

  HashMap                   Doubly Linked List
  ┌───────────────┐         HEAD ←──────────────────────────── TAIL
  │ key → node*  │         (Most Recently Used)         (Least Recently Used)
  ├───────────────┤
  │  "A" → [A] ──┼────────▶ [A] ⇌ [C] ⇌ [B]
  │  "B" → [B] ──┼────────────────────────▶[B]
  │  "C" → [C] ──┼──────────────▶[C]
  └───────────────┘

  get("B"):  move [B] to HEAD  →  [B] ⇌ [A] ⇌ [C]
  put("D"):  insert [D] at HEAD, evict [C] from TAIL  →  [D] ⇌ [B] ⇌ [A]

3. LRU Cache Implementation

Here is a complete LRU Cache implementation in Python using a Node class and a doubly linked list managed with sentinel head/tail nodes to avoid edge-case checks:

Python — LRU Cache (O(1) get and put) class Node: def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.map = {} # key → Node # Sentinel nodes (dummy head and tail) self.head = Node() # Most Recently Used side self.tail = Node() # Least Recently Used side self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): """Detach node from list.""" node.prev.next = node.next node.next.prev = node.prev def _insert_front(self, node): """Insert node right after head (MRU position).""" node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def get(self, key: int) -> int: if key not in self.map: return -1 node = self.map[key] self._remove(node) self._insert_front(node) # mark as recently used return node.val def put(self, key: int, value: int) -> None: if key in self.map: self._remove(self.map[key]) node = Node(key, value) self.map[key] = node self._insert_front(node) if len(self.map) > self.cap: # Evict LRU — node just before tail lru = self.tail.prev self._remove(lru) del self.map[lru.key] # Usage: cache = LRUCache(3) cache.put(1, "A") # cache: {1} cache.put(2, "B") # cache: {1,2} cache.put(3, "C") # cache: {1,2,3} cache.get(1) # returns "A", moves 1 to MRU. LRU is now 2 cache.put(4, "D") # evicts 2 (LRU). cache: {1,3,4}

Python Shortcut — OrderedDict

Python's collections.OrderedDict maintains insertion order and supports move_to_end(key) in O(1). You can build a fully functional LRU Cache in about 10 lines using it. However, interviewers expect the HashMap + Doubly Linked List implementation to demonstrate your understanding of the underlying mechanics.

4. Time and Space Complexity

Operation	Time Complexity	Notes
get(key)	O(1)	HashMap lookup + list node move-to-front
put(key, val)	O(1)	HashMap insert + list insert + optional eviction
Space	O(capacity)	HashMap + Doubly Linked List each store at most capacity items

5. Eviction Policy Comparison

Choosing the right eviction policy depends on your access pattern. Here is a comparison of the four most common policies:

Policy	Evicts	Best For	Weakness	Implementation Complexity
LRU	Least recently accessed	Temporal locality workloads	Poor for frequency-based access	Medium (HashMap + DLL)
LFU	Least frequently accessed	Frequency-based workloads	Cold-start problem; stale "popular" items	High (HashMap + min-heap or freq-map)
FIFO	Oldest inserted item	Simple queues, streaming	Evicts hot items inserted long ago	Low (just a queue)
MRU	Most recently accessed	Sequential scan workloads	Counter-intuitive, narrow use cases	Medium (HashMap + DLL, reversed)
Random	Random item	General fallback	Unpredictable; can evict hot items	Very low

6. Real-World LRU Usage

CPU Cache (Hardware LRU)

Modern CPUs use LRU (or pseudo-LRU) in L1/L2/L3 caches to manage cache lines. When a cache miss occurs, a new cache line is fetched from RAM and replaces the LRU line. Hardware LRU uses a matrix of bits to track access order without software overhead.

Redis — allkeys-lru

Redis supports configurable maxmemory policies. When memory hits the maxmemory limit, Redis evicts keys based on the configured policy. The allkeys-lru policy evicts the LRU key among all keys. Redis uses an approximated LRU: it samples a set of random keys (controlled by maxmemory-samples) and evicts the one with the oldest access timestamp stored in the key's object metadata.

Redis config — LRU eviction # redis.conf maxmemory 2gb maxmemory-policy allkeys-lru maxmemory-samples 10 # sample 10 keys, pick LRU (default: 5) # Available policies: # noeviction — return error when memory full (default) # allkeys-lru — evict LRU among all keys # volatile-lru — evict LRU among keys with TTL set # allkeys-lfu — evict LFU among all keys (Redis 4.0+) # volatile-lfu — evict LFU among keys with TTL # allkeys-random — evict random key # volatile-ttl — evict key with nearest expiry

Browser Cache

Web browsers use LRU (or similar) policies to manage cached HTTP responses, images, and scripts in their disk cache. When the cache quota is reached, the browser evicts the least recently accessed resources to make room for new ones.

Database Buffer Pool

MySQL InnoDB and PostgreSQL use LRU variants for their buffer pool (in-memory page cache). InnoDB uses a modified LRU that splits the list into "young" and "old" sublists to handle table scan pollution — large sequential scans do not evict hot random-access pages.

7. When LRU is NOT the Right Choice

LRU works well when your workload has temporal locality — recently accessed items are likely to be accessed again. It can be a poor choice in these scenarios:

Frequency-dominated workloads: If item A is accessed 1,000 times/hour and item B was accessed once a minute ago, LRU evicts A next. Use LFU instead.
Sequential scan workloads: A full table scan that reads every page once will evict your entire hot cache. MySQL InnoDB addresses this with its young/old sublist design. Use MRU or scan-resistant policies.
Large item size variance: LRU treats all items equally regardless of size. A 1MB cached response gets the same treatment as a 100-byte string. Size-aware eviction (SLRU, TinyLFU) handles this better.
Distributed caches with uneven sharding: LRU on individual shards can evict hot items if a shard is undersized. Consider consistent hashing to balance load across shards.

Redis LRU Approximation Caveat

Redis's approximated LRU (random sampling) is not a true LRU. With the default sample size of 5, it is reasonably accurate for most workloads. Increase maxmemory-samples to 10 for closer-to-true LRU behaviour, but this uses more CPU per eviction decision. For true frequency-based eviction, use allkeys-lfu instead — Redis 4.0+ implements the TinyLFU algorithm.

8. Thread-Safe LRU Cache

The implementation above is not thread-safe. In multi-threaded environments, concurrent get/put operations can corrupt the doubly linked list. Solutions:

Global lock: Wrap every get/put in a mutex. Simple but creates a bottleneck under high concurrency.
Segmented LRU: Shard the cache into N independent LRU caches, each with its own lock. Key is hashed to determine the shard. Java's ConcurrentLinkedHashMap (used in Caffeine) uses this approach.
Lock-free: Use atomic operations and CAS (Compare-And-Swap) for pointer updates. Very complex to implement correctly.
Caffeine (Java): The Caffeine library implements a highly optimised, thread-safe LRU using a lock-striped approach and achieves near-theoretical-maximum throughput.

How We Research and Update This Guide

We test the underlying formula or workflow, compare outputs with reliable references, and revise examples whenever the page content changes.

The workflow or formula is tested directly in the tool and compared against independent reference examples.
Examples are kept practical so readers can verify the result without hidden assumptions.
Pages are revised whenever the interface, calculation flow, or surrounding guidance materially changes.

Frequently Asked Questions — LRU Cache

What data structures are used to implement LRU Cache in O(1)?

What is the difference between LRU and LFU cache eviction?

How does Redis implement LRU eviction?

When should you NOT use LRU cache?

What is the difference between LRU and FIFO cache eviction?

What capacity should an LRU cache have?