LRU Cache: Implementation and Time Complexity Analysis

What is an LRU Cache?

An LRU Cache (Least Recently Used Cache) is a fixed-size data structure that evicts the least recently accessed item when it reaches capacity and a new item needs to be inserted. It maintains items in order of recency, automatically discarding items that haven't been accessed for the longest period. This eviction policy is based on the observation that data accessed recently is likely to be accessed again soon, while data that hasn't been touched for a while is less valuable to keep around.

At its core, an LRU Cache must support two primary operations efficiently:

• get(key) — Retrieve the value associated with a key. If the key exists, this access marks it as the most recently used item.
• put(key, value) — Insert or update a key-value pair. If the cache is at capacity, evict the least recently used item before inserting the new one.

Both operations should ideally run in O(1) time complexity, which makes the LRU Cache an interesting algorithmic challenge — a simple array or linked list alone won't give us constant-time lookups and constant-time eviction simultaneously.

Why the LRU Cache Matters

The LRU eviction strategy appears throughout systems design and performance engineering. Here are some practical scenarios where it shines:

• Database query caches: MySQL and PostgreSQL use LRU variants to manage buffer pools, keeping frequently accessed data pages in memory while aging out stale ones.
• CPU caches: Modern processors approximate LRU to decide which cache lines to evict when fetching new data from RAM.
• Web browsers: Cached HTTP responses, rendered DOM trees, and compiled JavaScript bytecode all benefit from LRU-based memory management.
• CDNs and proxy servers: Edge caches like Varnish use LRU to serve hot content from memory while dropping cold content.
• Mobile apps and image loaders: Libraries like Glide or Picasso for Android use LRU caches to limit memory usage when displaying image feeds.
• Redis: The maxmemory-policy allkeys-lru configuration tells Redis to evict the least recently used keys across the entire dataset when it hits its memory limit.

In all these cases, the cache has a fixed memory budget, and LRU provides a simple, high-performance heuristic that performs well under typical access patterns exhibiting temporal locality.

Core Data Structures Behind O(1) Operations

To achieve O(1) for both get and put, we combine two data structures:

• Hash Map (Dictionary): Maps keys directly to nodes in a linked list, giving us O(1) lookups.
• Doubly Linked List: Maintains the order of items from most recently used (head) to least recently used (tail). It allows O(1) removal of any node (including the tail) and O(1) insertion at the head.

Here's why a singly linked list or an array won't work alone:

• A singly linked list cannot remove an arbitrary node in O(1) because we need the previous node's pointer to rewire the chain, which requires a traversal from the head.
• An array requires O(n) shifting when we remove or reorder elements in the middle.

With a doubly linked list, each node has both prev and next pointers. Given a direct reference to a node (which the hash map provides), we can unlink it in O(1) by updating its neighbors' pointers.

Node Structure

class DoublyLinkedNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

The node stores the key alongside the value. This is critical: when we evict the tail node, we need its key to remove the corresponding entry from the hash map. Without storing the key in the node, we'd have no way to clean up the dictionary.

Full Implementation in Python

Below is a complete, production-style implementation of an LRU Cache. It includes thorough handling of edge cases: accessing an existing key updates its position, inserting a new key at capacity triggers eviction, and updating an existing key overwrites the value while refreshing recency.

class LRUCache:
    """
    A fixed-capacity cache that evicts the least recently used item
    when space is needed for a new insertion.
    
    All operations run in O(1) time.
    """
    
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be a positive integer")
        
        self.capacity = capacity
        self.size = 0
        
        # Hash map: key -> DoublyLinkedNode
        self.cache = {}
        
        # Sentinel nodes for the doubly linked list.
        # Head points to the most recently used item.
        # Tail points to the least recently used item.
        self.head = DoublyLinkedNode(None, None)  # dummy head
        self.tail = DoublyLinkedNode(None, None)  # dummy tail
        
        self.head.next = self.tail
        self.tail.prev = self.head
    
    # --------------------------------------------------
    # Private linked list helpers
    # --------------------------------------------------
    
    def _add_to_front(self, node):
        """Insert node immediately after the dummy head (MRU position)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        """Unlink node from the list without deleting it."""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
    
    def _move_to_front(self, node):
        """Promote an existing node to the MRU position."""
        self._remove_node(node)
        self._add_to_front(node)
    
    def _evict_lru(self):
        """Remove the least recently used node (the one just before dummy tail)."""
        lru_node = self.tail.prev
        self._remove_node(lru_node)
        del self.cache[lru_node.key]
        self.size -= 1
    
    # --------------------------------------------------
    # Public API
    # --------------------------------------------------
    
    def get(self, key):
        """
        Retrieve the value for 'key' if it exists.
        Returns -1 if the key is not present.
        On a cache hit, the item is marked as most recently used.
        
        Time Complexity: O(1)
        """
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self._move_to_front(node)
        return node.value
    
    def put(self, key, value):
        """
        Insert or update a key-value pair.
        If the key already exists, update its value and move it to the front.
        If the key is new and the cache is at capacity, evict the LRU item first.
        
        Time Complexity: O(1)
        """
        if key in self.cache:
            # Update existing key
            node = self.cache[key]
            node.value = value
            self._move_to_front(node)
            return
        
        # Evict if at capacity before inserting the new item
        if self.size == self.capacity:
            self._evict_lru()
        
        # Create and insert the new node
        new_node = DoublyLinkedNode(key, value)
        self.cache[key] = new_node
        self._add_to_front(new_node)
        self.size += 1
    
    # --------------------------------------------------
    # Debugging helpers
    # --------------------------------------------------
    
    def __str__(self):
        """Return a string showing items from MRU to LRU."""
        items = []
        current = self.head.next
        while current != self.tail:
            items.append(f"{current.key}:{current.value}")
            current = current.next
        return "{" + " -> ".join(items) + "}"
    
    def __len__(self):
        return self.size


class DoublyLinkedNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

Step-by-Step Walkthrough

Let's trace through a sequence of operations to see the internal mechanics in action:

# Create a cache with capacity 3
cache = LRUCache(3)

cache.put("a", 1)   # Cache: {a:1}
cache.put("b", 2)   # Cache: {b:2 -> a:1}
cache.put("c", 3)   # Cache: {c:3 -> b:2 -> a:1}

# Accessing "a" moves it to the front
cache.get("a")      # Returns 1, Cache: {a:1 -> c:3 -> b:2}

# Inserting "d" at capacity evicts the LRU item ("b")
cache.put("d", 4)   # Evicts b:2, Cache: {d:4 -> a:1 -> c:3}

# Verify eviction
print(cache.get("b"))  # Returns -1 (not found)
print(cache.get("a"))  # Returns 1
print(cache.get("c"))  # Returns 3
print(cache.get("d"))  # Returns 4

Time Complexity Analysis

Let's analyze every method in detail to confirm the O(1) guarantee:

get(key) — O(1)

• Hash map lookup: key in self.cache is O(1) average case. Python dictionaries use open addressing with random probing, giving amortized constant-time lookups.
• Linked list promotion: _move_to_front calls _remove_node and _add_to_front, both of which are pointer rewiring operations that touch only the node and its immediate neighbors — no traversal involved.

The worst case for the hash lookup is O(n) if there are many hash collisions, but Python's dictionary implementation resizes dynamically to keep the load factor low, making this exceedingly rare in practice. We can treat it as O(1) amortized.

put(key, value) — O(1)

• Hash map lookup for checking key existence: O(1).
• Eviction path: _evict_lru grabs self.tail.prev (the LRU node), unlinks it (O(1) pointer updates), and deletes the key from the dictionary (O(1)).
• Insertion path: Creating a new node, inserting it into the dictionary, and calling _add_to_front are all constant-time operations.

There's no loop, no traversal, and no allocation that scales with cache size. Every operation completes in a bounded number of steps regardless of how many items are in the cache.

Space Complexity

The space complexity is O(n) where n is the cache capacity. We store one dictionary entry and one doubly linked list node per cached item. The sentinel head and tail nodes consume constant extra space.

Comparison with Alternative Approaches

Here's how the combined hash-map-plus-doubly-linked-list approach compares to naive implementations:

Using Python's Built-in OrderedDict

Python's collections.OrderedDict (and since Python 3.7, the standard dict which maintains insertion order) can be leveraged to build an LRU Cache with remarkably little code. The OrderedDict internally uses a doubly linked list to preserve order, and its move_to_end method gives us the promotion behavior we need.

from collections import OrderedDict

class LRUCacheBuiltin:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key):
        if key not in self.cache:
            return -1
        # Move the accessed key to the end (most recent position)
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            # Update and move to most recent
            self.cache.move_to_end(key)
            self.cache[key] = value
            return
        
        # Evict the least recently used (first item) if at capacity
        if len(self.cache) >= self.capacity:
            self.cache.popitem(last=False)  # last=False pops the first inserted item
        
        self.cache[key] = value
        # New items are automatically placed at the end (most recent)

This implementation is concise and leverages Python's optimized C-level data structures. The popitem(last=False) call removes the oldest entry in O(1), and move_to_end is also O(1). For production Python code, this is often the preferred approach unless you need explicit control over the linked list (for example, to add custom eviction callbacks or statistics).

Best Practices and Common Pitfalls

1. Always Store the Key Inside the Node

A common mistake is storing only the value in the linked list node. When the LRU node is evicted from the tail, you need its key to remove the corresponding entry from the hash map. Without the key, the dictionary would accumulate stale entries, causing a memory leak and incorrect behavior on subsequent get calls.

2. Use Sentinel Nodes

Sentinel (dummy) head and tail nodes eliminate edge-case null checks. Without them, every insertion and removal would need to handle cases where the list is empty or where we're operating on the first or last real node. Sentinels make the code cleaner and less error-prone.

3. Thread Safety Considerations

The basic LRU Cache implementation is not thread-safe. If multiple threads access the cache concurrently, you must add synchronization. A coarse-grained lock (like threading.Lock in Python) around get and put works but creates contention. For high-concurrency scenarios, consider:

• Per-segment locking (sharding the cache into multiple LRU segments by key hash).
• Lock-free approximations like the Clock-PRO or CLOCK-Pro algorithms.
• Using a concurrent language or framework with built-in concurrent LRU structures (Java's ConcurrentLinkedHashMap, or libraries like Caffeine).

4. Handle Capacity Zero or Negative Gracefully

Always validate the capacity parameter in the constructor. A zero-capacity cache should reject all put operations (or raise an error at construction time). Our implementation raises a ValueError for non-positive capacities, which is clear and immediate.

5. Consider Eviction Callbacks

In real-world systems, you often need to perform cleanup when an item is evicted — closing file handles, decrementing reference counts, or notifying downstream systems. Add an optional callback parameter:

class LRUCacheWithCallback:
    def __init__(self, capacity, on_evict=None):
        self.capacity = capacity
        self.on_evict = on_evict  # callable(key, value)
        # ... rest of initialization
    
    def _evict_lru(self):
        lru_node = self.tail.prev
        self._remove_node(lru_node)
        del self.cache[lru_node.key]
        self.size -= 1
        if self.on_evict:
            self.on_evict(lru_node.key, lru_node.value)

6. Monitor Cache Metrics

Track hit rate, miss rate, and eviction count. These metrics help you tune the cache capacity and diagnose performance issues. A simple instrumentation layer might look like this:

class InstrumentedLRUCache(LRUCache):
    def __init__(self, capacity):
        super().__init__(capacity)
        self.hits = 0
        self.misses = 0
        self.evictions = 0
    
    def get(self, key):
        if key in self.cache:
            self.hits += 1
            return super().get(key)
        self.misses += 1
        return -1
    
    def _evict_lru(self):
        self.evictions += 1
        super()._evict_lru()
    
    @property
    def hit_ratio(self):
        total = self.hits + self.misses
        return self.hits / total if total > 0 else 0.0

7. Beware of Memory Overhead

Each cache entry consumes memory for the dictionary slot, the node object, and its two pointers. In Python, this overhead is roughly 200–300 bytes per entry. For caches holding millions of small items, consider using a more memory-efficient representation: array-backed storage with integer indices instead of Python objects, or a language with value types like C++ or Rust. Alternatively, use an off-the-shelf library like cachetools or lru-dict which are implemented in C for better memory density.

8. Choose the Right Eviction Policy Variant

Standard LRU assumes that recency perfectly predicts future access, but this isn't always true. Consider these variants when appropriate:

• LRU-K: Tracks the timestamp of the K-th most recent access. Evicts items whose K-th access is furthest in the past. This prevents cache pollution from single-access items.
• 2Q (Two Queues): Maintains a small FIFO queue for first-time accesses and promotes items to the main LRU queue only if they are accessed again. Simple and effective.
• CLOCK / CLOCK-Pro: An approximation that uses a circular buffer and a reference bit, avoiding the overhead of linked list pointers. Used in operating system page replacement.
• LFU (Least Frequently Used): Evicts items with the lowest access count. Combines well with LRU for hybrid policies like Redis's LFU mode.

LRU Cache in a Web Application Context

Imagine a high-traffic API endpoint that fetches user profiles from a database. Without caching, every request hits the database. With an LRU cache in front, we can dramatically reduce database load. Here's a sketch of how that might look in a Flask-like application:

# Global LRU cache shared across requests
user_profile_cache = LRUCache(capacity=5000)

def get_user_profile(user_id: int):
    # Try cache first
    cached = user_profile_cache.get(user_id)
    if cached != -1:
        return cached
    
    # Cache miss — fetch from database
    profile = db.fetch_user_profile(user_id)
    if profile:
        user_profile_cache.put(user_id, profile)
    return profile

The LRU eviction policy ensures that the cache automatically adapts to changing traffic patterns: if a subset of users becomes suddenly popular, their profiles will naturally displace less frequently accessed ones, keeping the cache fresh without manual invalidation.

Testing the LRU Cache

A thorough test suite validates correctness under various scenarios. Here's a minimal pytest-compatible test plan:

def test_basic_operations():
    cache = LRUCache(3)
    
    cache.put("a", 1)
    cache.put("b", 2)
    cache.put("c", 3)
    assert cache.get("a") == 1
    assert cache.get("b") == 2
    assert cache.get("c") == 3
    
    # Test eviction
    cache.put("d", 4)  # Should evict the LRU: "a" was accessed, so "b" or "c"? 
    # Actually after get("a") -> get("b") -> get("c"), "c" is MRU, "a" is LRU
    # Wait — let's trace carefully:
    # After puts: MRU=c, then b, LRU=a
    # get("a") moves a to front: MRU=a, then c, LRU=b
    # get("b") moves b to front: MRU=b, then a, LRU=c
    # get("c") moves c to front: MRU=c, then b, LRU=a
    # put("d") evicts "a"
    assert cache.get("a") == -1
    assert cache.get("b") == 2
    assert cache.get("c") == 3
    assert cache.get("d") == 4

def test_update_existing_key():
    cache = LRUCache(2)
    cache.put("x", 100)
    cache.put("x", 200)  # Update
    assert cache.get("x") == 200
    assert len(cache) == 1

def test_capacity_one():
    cache = LRUCache(1)
    cache.put("k1", "v1")
    assert cache.get("k1") == "v1"
    cache.put("k2", "v2")
    assert cache.get("k1") == -1
    assert cache.get("k2") == "v2"

def test_zero_capacity_raises():
    import pytest
    with pytest.raises(ValueError):
        LRUCache(0)
    with pytest.raises(ValueError):
        LRUCache(-5)

Conclusion

The LRU Cache is a foundational building block in systems design, balancing memory constraints with access patterns that exhibit temporal locality. By pairing a hash map with a doubly linked list — or leveraging Python's OrderedDict — you achieve true O(1) operations for both reads and writes. The implementation requires careful attention to details like storing keys in nodes, using sentinel pointers, and handling the eviction path correctly, but once in place, it delivers predictable, high-performance caching that adapts automatically to workload shifts.

Beyond the basic implementation, production-grade LRU caches benefit from instrumentation, eviction callbacks, thread safety, and consideration of variant policies like LRU-K or CLOCK. Whether you're building a database buffer pool, a web application cache layer, or a mobile image loader, understanding LRU internals gives you both a practical tool and deeper insight into the trade-offs that govern memory-bound system performance.