LRU Cache Implementation: Complete Implementation Guide

1. Introduction and Core Concepts

An LRU cache implementation is one of the most fundamental and widely used caching strategies in computer science. LRU stands for Least Recently Used, and it describes an eviction policy that discards the least recently accessed item first when the cache reaches its capacity. This approach is based on the principle of temporal locality: if an item has been accessed recently, it is likely to be accessed again soon, while items that have not been used for a long time are less likely to be needed in the near future.

At its core, an LRU cache is a fixed-size data structure that supports two primary operations: get(key) which retrieves a value and marks the key as recently used, and put(key, value) which inserts or updates a value and also marks the key as recently used. When a new item is inserted into a full cache, the item that has not been accessed for the longest time is evicted to make room. This simple yet powerful heuristic makes LRU exceptionally effective for a wide range of workloads where access patterns exhibit locality.

Understanding lru cache implementation matters because caching is a critical technique for bridging the speed gap between fast processors and slower storage or networks. Without efficient caching, modern web applications, databases, operating systems, and content delivery networks would be orders of magnitude slower. An LRU cache provides a predictable, easy-to-reason-about trade-off between memory consumption and hit rate, and it is often the default choice when building in-memory caches, page replacement systems, and memoization layers. Mastering its implementation is therefore essential for backend engineers, systems designers, and anyone preparing for technical interviews.

Why LRU Works So Well

The effectiveness of LRU comes from its ability to adapt dynamically to changing access patterns without requiring any prior knowledge of the workload. Unlike static caching or First-In-First-Out (FIFO) policies, LRU continuously reorders items based on actual usage. This makes it resilient to bursts of requests for a subset of keys and allows it to retain hot data while naturally phasing out cold data. For many real-world traces, LRU achieves a hit rate close to that of the optimal offline algorithm (Belady's algorithm) while being fully online and implementable in constant time.

Core Requirements of an LRU Cache

A correct lru cache implementation must satisfy several invariants. First, it must have a fixed capacity defined at creation time. Second, both get and put operations must run in O(1) average time complexity to be useful at scale. Third, it must maintain a strict recency ordering where every access moves the accessed key to the most-recently-used position. Finally, it must handle edge cases such as updating an existing key, evicting when full, and operating correctly with capacity zero or one. Achieving O(1) for both operations simultaneously is the key design challenge that dictates the classic data structure combination.

2. How It Works

The classic lru cache implementation achieves O(1) get and put by combining two data structures: a hash map and a doubly linked list. The hash map provides O(1) lookup from key to node, while the doubly linked list maintains the recency order and allows O(1) insertion, deletion, and movement of nodes when we have a direct pointer to the node. Neither structure alone is sufficient. A hash map alone cannot track order efficiently, and a linked list alone cannot find a key quickly. Together, they provide the ideal balance.

Conceptually, the doubly linked list is ordered from most recently used (MRU) at the head to least recently used (LRU) at the tail. The hash map stores entries of the form key -> node_reference, where the node contains the key, value, and pointers to its previous and next nodes. When a key is accessed via get, we use the hash map to locate its node in O(1), remove it from its current position in the list, and move it to the head. When a new key is inserted via put and the cache is full, we evict the tail node (the LRU item), remove its entry from the hash map, and insert the new node at the head.

To simplify boundary conditions, most implementations use dummy head and tail sentinel nodes. These sentinels never hold real data and never get evicted; they simply ensure that every real node always has a predecessor and successor, eliminating null-pointer checks during insertion and deletion. All operations then become a sequence of pointer rewiring steps that are constant time and easy to reason about.

Anatomy of Get and Put Operations

The get operation follows three steps: lookup, hit handling, and miss handling. On lookup, check if the key exists in the hash map. If it does not, return -1 or null to indicate a miss. If it does, retrieve the node, detach it from the list, and reattach it at the head to mark it as most recently used, then return its value. This move-to-head step is what maintains the LRU invariant.

The put operation is slightly more complex because it must handle both updates and inserts. If the key already exists, update the node's value and move it to the head, just like get. If the key is new, create a new node, insert it at the head, and add it to the hash map. Then check if the size exceeds capacity. If it does, identify the node before the dummy tail (the true LRU node), remove it from both the list and the hash map, and decrement the size. All of these steps are O(1) because they involve only hash map operations and a constant number of pointer manipulations.

Why a Doubly Linked List is Essential

A singly linked list cannot support O(1) removal of an arbitrary node because you need the predecessor to rewire pointers, and finding the predecessor requires an O(n) traversal. A doubly linked list stores both prev and next pointers, so given a node reference from the hash map, you can unlink it in O(1) by linking its predecessor directly to its successor. This is why the combination of hash map plus doubly linked list is the canonical solution taught in textbooks and expected in interviews.

3. Implementation

There are several ways to build an lru cache implementation in Python, ranging from a from-scratch doubly linked list to leveraging the standard library. Below we present the most instructive approaches with detailed comments, starting with the canonical interview-ready version.

Classic Hash Map + Doubly Linked List (Interview Standard)

This implementation explicitly manages nodes and pointers, giving you full control and demonstrating a deep understanding of the underlying mechanics. It is the version most interviewers expect you to be able to whiteboard.

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.capacity = capacity
        self.cache = {}  # key -> Node
        # Dummy head and tail to avoid edge cases
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node):
        """Remove node from linked list in O(1)."""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node: Node):
        """Insert node right after dummy head (MRU position)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # Move to head to mark as recently used
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing node
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_head(node)
        else:
            if self.capacity <= 0:
                return
            # Evict LRU if at capacity
            if len(self.cache) >= self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            # Insert new node
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)

Concise Implementation Using OrderedDict

Python's collections.OrderedDict maintains insertion order and provides move_to_end() and popitem(last=False) operations that make an LRU cache trivial. This is the preferred approach for production Python code where clarity and brevity matter more than demonstrating pointer manipulation.

from collections import OrderedDict

class LRUCacheOrderedDict:
    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
        # Move to end to mark as recently used (MRU at end)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.cache:
            # Update and move to end
            self.cache.move_to_end(key)
        self.cache[key] = value
        # Evict LRU (first item) if over capacity
        if len(self.cache) > self.capacity:
            # popitem(last=False) removes FIFO order (LRU)
            self.cache.popitem(last=False)

Thread-Safe LRU Cache for Concurrent Environments

In web servers and multi-threaded applications, cache access must be synchronized. The following wrapper adds a reentrant lock to ensure atomic get and put operations without corrupting the linked list or hash map under concurrency.

import threading
from collections import OrderedDict

class ThreadSafeLRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()
        self.lock = threading.RLock()

    def get(self, key: int):
        with self.lock:
            if key not in self.cache:
                return -1
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int):
        with self.lock:
            if self.capacity <= 0:
                return
            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)

    def __len__(self):
        with self.lock:
            return len(self.cache)

Using functools.lru_cache for Function Memoization

For pure function memoization, Python provides a built-in decorator that implements an LRU cache automatically. This is ideal for expensive recursive or I/O-bound functions where you want to cache return values based on arguments without writing cache logic yourself.

from functools import lru_cache
import time

@lru_cache(maxsize=128)
def expensive_fibonacci(n: int) -> int:
    """Fibonacci with automatic LRU memoization."""
    if n < 2:
        return n
    return expensive_fibonacci(n-1) + expensive_fibonacci(n-2)

# First call computes, second call is O(1) cache hit
print(expensive_fibonacci(30))  # Computed
print(expensive_fibonacci(30))  # Cached

# Inspect cache statistics
print(expensive_fibonacci.cache_info())
# CacheInfo(hits=1, misses=31, maxsize=128, currsize=31)

# For unhashable arguments or custom eviction, use manual LRUCache class above

4. Step-by-Step Example

To solidify how an lru cache implementation behaves, let us walk through a concrete trace with capacity 3. We will track both the hash map contents and the doubly linked list order from MRU (head.next) to LRU (tail.prev) after each operation. This visualization is invaluable for debugging and for explaining your solution in an interview.

We start with an empty cache: capacity = 3, cache = {}, list = head <-> tail. No items are present and no evictions have occurred. The dummy head and tail are linked directly to each other, representing an empty recency order.

Operation 1: put(1, 100). Key 1 is new and the cache is not full. We create Node(1,100), insert it at the head, and add it to the map. State: cache = {1: Node1}, list = head <-> 1 <-> tail. Recency order: [1] where 1 is MRU and also LRU since it is the only element.

Continuing the Trace

Operation 2: put(2, 200). Similar to above, Node 2 becomes MRU. State: cache = {1: Node1, 2: Node2}, list = head <-> 2 <-> 1 <-> tail. Order: [2, 1]. Operation 3: put(3, 300). State: cache = {1,2,3}, list = head <-> 3 <-> 2 <-> 1 <-> tail. Order: [3, 2, 1]. The cache is now full.

Operation 4: get(1). Key 1 is a hit. We locate Node 1 via the hash map, detach it from the tail position, and move it to the head. State: list = head <-> 1 <-> 3 <-> 2 <-> tail. Order becomes [1, 3, 2]. Notice how get reorders the list without changing the map size. Return value is 100. This reordering is the essence of LRU.

Operation 5: put(4, 400). Key 4 is new and the cache is full, so eviction is required. The LRU node is at the tail, which is Node 2 (key 2). We remove Node 2 from the list and delete key 2 from the hash map, then insert Node 4 at the head. State: cache = {1: Node1, 3: Node3, 4: Node4}, list = head <-> 4 <-> 1 <-> 3 <-> tail. Order: [4, 1, 3]. Key 2 is gone.

Operation 6: get(2) results in a miss and returns -1 because key 2 was evicted. The list remains [4, 1, 3]. Operation 7: put(3, 333) is an update. Key 3 already exists, so we update its value to 333 and move it to the head. State: list = head <-> 3 <-> 4 <-> 1 <-> tail. Order: [3, 4, 1]. No eviction occurs on updates. This trace demonstrates all critical transitions: insert, hit promotion, eviction, miss, and update promotion.

5. Complexity Analysis

The primary reason the hash map plus doubly linked list design is canonical is its optimal time complexity. Both get and put operate in O(1) average time, which is essential for caches that may handle millions of operations per second. The space complexity is O(capacity) for storing the cached entries plus O(1) overhead for sentinel nodes and pointers.

It is important to distinguish between average and worst-case behavior. Hash map operations are O(1) average but can degrade to O(n) in the worst case due to hash collisions, though Python's dictionary implementation makes this extremely rare in practice. Linked list pointer manipulations are always O(1) worst-case because they involve a fixed number of assignments. Therefore, the overall worst-case time is dominated by the hash map's worst case, but for all practical purposes we treat it as O(1).

Space usage is linear in the number of cached items. Each entry stores a key, value, and two pointers (prev and next) plus the hash map entry overhead. For a capacity of N, we store exactly N nodes and N hash map entries. There is no additional per-operation allocation beyond eviction and insertion, making memory usage predictable and bounded, which is critical for systems with strict memory limits.

When comparing to naive alternatives, the advantage is stark. An implementation using only a Python list or OrderedDict without move-to-end would require O(n) to find and reorder an item. An implementation using only a hash map with timestamps would require O(n) to scan for the LRU item on eviction. The hybrid structure avoids both linear scans, making it the only design that achieves true O(1) for both operations.

Amortized and Real-World Performance

In CPython, dictionary lookups and OrderedDict operations are highly optimized in C and typically complete in tens of nanoseconds for small caches. The doubly linked list version in pure Python will be slower due to Python-level object overhead, but still O(1). For high-performance systems, you might implement the linked list in C or use functools.lru_cache which is implemented in C. The choice depends on whether you need custom key types, thread safety, or observability beyond simple function memoization.

6. Variations and Optimizations

While the classic LRU is excellent for general workloads, several variations optimize for specific access patterns, concurrency requirements, or memory constraints. Understanding these helps you choose the right policy for your system and answer advanced interview follow-ups.

One common optimization is the use of a segmented LRU, such as 2Q or LRU-K. Standard LRU suffers from cache pollution when a scan of cold items (e.g., a one-time bulk read) evicts hot items. LRU-K tracks the K-th most recent access instead of just the last access, which better distinguishes frequently accessed items from scan traffic. Similarly, 2Q divides the cache into a FIFO queue for first-time items and an LRU queue for items accessed at least twice, protecting the hot set from scans.

Another important variant is TinyLFU and Window-TinyLFU (W-TinyLFU), which combine LRU with frequency sketching to achieve higher hit rates than pure LRU while retaining O(1) operations. These are used in high-performance caches like Caffeine (Java) and Ristretto (Go). They maintain a small admission window (often LRU) and a main cache with frequency-based eviction, allowing them to adapt to both recency and frequency.

Pseudo-LRU and Hardware Considerations

In CPU caches where true LRU is too expensive in hardware, pseudo-LRU (PLRU) is used. PLRU uses a binary tree of bits to approximate LRU with O(log n) update cost and less storage, which is crucial when cache associativity is high and every gate counts. For software caches, this trade-off is rarely needed, but it is a common interview topic for systems roles.

Expiration and Size-Aware Eviction

Production caches often need time-to-live (TTL) or time-to-idle (TTI) expiration. An LRU cache can be extended to store an expiry timestamp per node and lazily evict expired entries on get, or actively purge them with a background thread. Similarly, when values have variable sizes (e.g., images vs. JSON), capacity may be defined in bytes rather than item count. In that case, eviction may remove multiple LRU items until enough space is freed, and the cache must track total byte size rather than just item count.

Concurrency optimizations include sharding the cache into multiple LRU segments each with its own lock (striped locking) to reduce contention, or using lock-free concurrent hash maps with atomic list operations. For read-heavy workloads, you can also use a read-write lock or copy-on-write techniques to allow concurrent gets without blocking each other.

7. Real-World Applications

LRU caches are ubiquitous in modern software stacks because they provide a simple, effective way to reduce latency and load on slower tiers. Anywhere there is a speed differential between two layers, an LRU cache is a natural fit.

In operating systems, LRU is the classic page replacement algorithm. When physical RAM is full, the OS must evict a virtual memory page to disk. While true LRU is expensive to implement in hardware, approximations like Clock and Not Recently Used (NRU) are used, which are inspired by LRU. Similarly, file system buffer caches and disk block caches use LRU to keep frequently accessed blocks in memory.

In databases, buffer pools cache table pages and index pages in memory. Systems like MySQL InnoDB, PostgreSQL, and Redis use LRU or variants (e.g., InnoDB's midpoint insertion strategy) to decide which pages to keep. Query result caches also use LRU to avoid re-executing expensive queries. Without these caches, every query would require disk I/O, increasing latency by orders of magnitude.

Web infrastructure relies heavily on LRU. Web servers and reverse proxies like Nginx and Varnish cache HTTP responses, API gateways cache authentication results, and CDNs cache static assets at edge locations using LRU eviction. Browsers themselves maintain an LRU cache for images, scripts, and DNS lookups to speed up page loads. Application-level caches using Memcached or Redis often configure LRU as the eviction policy when memory is full.

On mobile and desktop applications, LRU caches manage memory for images, decoded bitmaps, and view holders. Android even provides android.util.LruCache as a first-class API. In all these cases, the cache size is tuned based on available memory, and LRU ensures that the most relevant data stays resident while gracefully handling memory pressure.

8. Comparison with Alternatives

Choosing a cache eviction policy requires understanding the trade-offs between hit rate, implementation complexity, and workload suitability. LRU is a strong default, but other policies may outperform it for specific patterns. The table below provides a comprehensive comparison to guide your decision.

For most web and application workloads, LRU provides the best balance of simplicity and performance. LFU can achieve higher hit rates when a small set of keys is extremely hot (e.g., celebrity profiles on a social network), but it requires additional bookkeeping and can retain stale hot items long after they cool down. Modern hybrids like TinyLFU attempt to get the best of both by combining recency and frequency. FIFO and Random are primarily used when implementation simplicity or hardware constraints outweigh hit rate considerations, such as in some CPU caches or embedded systems.

When evaluating alternatives, always measure with real traces from your system. Theoretical hit rates can be misleading; a policy that looks optimal on paper may perform poorly if your workload exhibits sequential scans or rapidly shifting hot sets. Many production systems support pluggable eviction policies so you can A/B test LRU vs. LFU vs. W-TinyLFU under live traffic.

9. Common Mistakes and Best Practices

Even experienced engineers make subtle errors when building an lru cache implementation. The most frequent bug is failing to move a node to the head on both get and put-update operations. If you only move on put, frequently read keys will be evicted despite being hot. Conversely, forgetting to update the hash map when evicting the LRU node leads to memory leaks and phantom hits where get returns a node that is no longer in the list.

Another common pitfall is mishandling capacity edge cases. A capacity of zero should result in a cache that never stores anything and always misses, not an exception or infinite loop. Negative capacities should be rejected at construction time. When capacity is one, every new put should evict the previous entry, and the linked list logic must still work correctly with only one real node between the sentinels. Writing explicit tests for these boundaries prevents production outages.

Concurrency bugs are especially dangerous. Without proper locking, two threads interleaving get and put can corrupt the doubly linked list pointers, creating cycles or lost nodes that are hard to reproduce. Even with locking, deadlocks can occur if you acquire multiple locks in inconsistent order or call user-provided callbacks while holding the cache lock. The best practice is to use a single reentrant lock, keep critical sections minimal, and never invoke external code while holding the lock.

Best Practices for Production Use

• Use sentinel nodes: Dummy head and tail eliminate null checks and make _remove and _add_to_head uniform. This reduces bugs and simplifies reasoning.
• Prefer OrderedDict or built-ins: In Python, do not reimplement the linked list unless you are interviewing. OrderedDict is battle-tested, faster in C, and less error-prone.
• Instrument your cache: Expose hit rate, miss rate, eviction count, and current size via metrics. A sudden drop in hit rate often indicates a bad deployment or a change in access patterns.
• Bound memory by bytes, not just count: If values vary in size, track total byte size and evict until under the byte limit. Otherwise a few large values can exhaust memory.
• Consider TTL and invalidation: Pure LRU never expires entries. Add per-entry TTL for data that can become stale, and provide explicit invalidate(key) and clear() methods.
• Test with realistic traces: Unit tests with small deterministic sequences are necessary but not sufficient. Replay production access logs to measure real hit rates and ensure no pathological behavior.
• Avoid caching non-hashable or mutable keys: If keys are mutable objects, their hash can change after insertion, making them unreachable. Always use immutable, hashable keys.

Finally, be mindful of Python's Global Interpreter Lock (GIL) and garbage collection. While the GIL provides some protection, it does not make your cache thread-safe for compound operations like get-then-put. Always use explicit locks for correctness, and avoid holding references to large objects longer than necessary to allow garbage collection to reclaim memory after eviction.

10. Interview Questions

LRU cache implementation is a perennial favorite in coding interviews at top technology companies. Interviewers use it to assess your ability to design data structures, analyze complexity, and write bug-free code under pressure. Below are the most common questions and how to approach them.

Question 1: Design an LRU Cache with O(1) get and put

This is the classic LeetCode 146 problem. You are asked to implement a class with __init__(capacity), get(key), and put(key, value). The expected answer is the hash map plus doubly linked list design described in Section 3. Start by explaining why you need both structures, sketch the sentinel nodes, and then code _remove and _add_to_head helpers before implementing get and put. Be sure to discuss eviction logic and handle the update case. Interviewers will check that you move nodes on get and that you delete from both the list and map on eviction.

Question 2: How would you make your LRU cache thread-safe?

Follow up to Question 1, this tests systems knowledge. Explain that you would add a reentrant lock (RLock) to protect all public methods, and that you must hold the lock for the entire get or put operation to make move-to-head atomic. Discuss alternatives like sharding for higher concurrency, read-write locks for read-heavy workloads, and why you should not use fine-grained per-node locks (complexity and deadlock risk). Mention that Python's OrderedDict version can be wrapped similarly, as shown in Section 3.

Question 3: What is the difference between LRU and LFU, and when would you choose one over the other?

This is a conceptual question that probes understanding of trade-offs. Answer by comparing eviction criteria: LRU evicts based on recency, LFU on frequency. Explain that LRU is better for workloads with temporal locality and changing hot sets, while LFU excels when a small set of keys is persistently hot (Zipfian distribution). Mention scan pollution as LRU's weakness and LFU's need for aging or decay to handle shifting popularity. Reference the comparison table in Section 8 and suggest hybrids like W-TinyLFU for the best of both worlds.

Question 4: Implement an LRU cache with TTL (time-to-live) per entry

Here you must extend the basic design to store an expiry timestamp with each node. On get, check if the entry is expired; if so, remove it and return a miss. On put, store expiry = now + ttl. Discuss lazy vs. active expiration: lazy checks on access are simple and O(1), while a background thread that periodically scans and purges expired entries prevents memory bloat from never-accessed expired items. Also discuss how TTL interacts with LRU ordering—expired items should be removed regardless of recency.

Question 5: How would you implement an LRU cache that is bounded by total memory in bytes rather than entry count?

This tests your ability to adapt the design to real-world constraints where values have variable sizes. Explain that you would track current_bytes and each node's size_in_bytes. On put, after inserting, while current_bytes > max_bytes, evict LRU nodes one by one, subtracting their sizes. Note that a single large put may evict multiple items, and that you need to handle the case where a single item exceeds max_bytes (either reject it or allow the cache to temporarily exceed the limit). This question also opens discussion about memory fragmentation and estimating object sizes in Python.

Preparing for these questions requires not just memorizing code, but being able to whiteboard the pointer manipulations, reason about concurrency and expiration, and articulate trade-offs clearly. Practice walking through the step-by-step example from Section 4 out loud, as interviewers often ask you to trace operations to verify your logic.