← Back to DevBytes
Developer Tutorial July 14, 2026 14 min read

LRU Cache Implementation: Multiple Solutions and Complexity Analysis

What is an LRU Cache?

An LRU Cache (Least Recently Used Cache) is a data structure that stores a limited number of items and evicts the least recently accessed item when the cache reaches its capacity and a new item needs to be inserted. The core idea is simple: if an item hasn't been used for the longest time, it's the most expendable one.

An LRU cache must support two primary operations with specific performance guarantees:

Both operations must run in O(1) time complexity on average — constant time regardless of cache size. This constraint is what makes the problem interesting and separates naive solutions from production-ready ones.

Why LRU Cache Matters

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

LRU caching is ubiquitous in systems design and real-world software engineering. Here are some key scenarios where it shines:

Understanding how to build an LRU cache from scratch is also a classic interview question at companies like Google, Meta, Amazon, and Microsoft, testing your grasp of data structures, pointers, and algorithmic trade-offs.

Implementation Approaches

We'll explore three distinct solutions, moving from the simplest (leaning on language features) to the most explicit (building everything from scratch).

Solution 1: Using OrderedDict (Python)

Python's collections.OrderedDict maintains insertion order and has a move_to_end method that can reposition a key to the front or back in O(1) time. By combining this with a capacity check, we can implement an LRU cache with minimal code.

How it works:

Complete implementation:

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
        # Mark as recently used by moving to end (right side)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update value and mark as recently used
            self.cache[key] = value
            self.cache.move_to_end(key)
            return
        
        # Evict least recently used if at capacity
        if len(self.cache) >= self.capacity:
            # popitem(last=False) removes the first inserted item (LRU)
            self.cache.popitem(last=False)
        
        # Insert new item (automatically at the end, most recent)
        self.cache[key] = value

# Usage example
cache = LRUCacheOrderedDict(2)
cache.put(1, 10)      # cache: {1: 10}
cache.put(2, 20)      # cache: {1: 10, 2: 20}
print(cache.get(1))   # returns 10, cache: {2: 20, 1: 10}
cache.put(3, 30)      # evicts key 2, cache: {1: 10, 3: 30}
print(cache.get(2))   # returns -1 (evicted)
cache.put(4, 40)      # evicts key 1, cache: {3: 30, 4: 40}
print(cache.get(1))   # returns -1 (evicted)
print(cache.get(3))   # returns 30
print(cache.get(4))   # returns 40

Pros: Extremely concise, leverages Python's built-in efficient data structures, perfect for production Python code where you don't need custom node manipulation.

Cons: Tied to Python; doesn't demonstrate the underlying mechanics that interviewers often want to see. In languages without OrderedDict (or LinkedHashMap in Java), you need the manual approach.

Solution 2: Doubly Linked List + Hash Map (Manual Implementation)

This is the canonical implementation that satisfies the O(1) requirement from scratch. The insight is that we need two complementary data structures working together:

Why doubly linked? A singly linked list requires O(n) to remove an arbitrary node because you need to find its predecessor. A doubly linked list lets you remove any node in O(1) given a reference to it — you can reach its prev and next nodes directly.

Here's the full implementation with detailed comments:

class DLinkedNode:
    """Node in the doubly linked list."""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCacheManual:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.cache = {}  # key -> DLinkedNode
        
        # Dummy head and tail to simplify edge cases
        # head <-> ... <-> tail
        # head always points to most recent, tail to least recent
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_node(self, node: DLinkedNode) -> None:
        """Add a node right after head (making it most recent)."""
        node.prev = self.head
        node.next = self.head.next
        
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node: DLinkedNode) -> None:
        """Remove an arbitrary node from the linked list."""
        prev_node = node.prev
        next_node = node.next
        
        prev_node.next = next_node
        next_node.prev = prev_node
        
        # Clean up pointers (optional but good practice)
        node.prev = None
        node.next = None
    
    def _move_to_head(self, node: DLinkedNode) -> None:
        """Move existing node to head (mark as most recent)."""
        self._remove_node(node)
        self._add_node(node)
    
    def _pop_tail(self) -> DLinkedNode:
        """Remove and return the least recently used node (before tail)."""
        lru_node = self.tail.prev
        self._remove_node(lru_node)
        return lru_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._move_to_head(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing node's value and move to head
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
            return
        
        # Evict if at capacity
        if self.size >= self.capacity:
            lru_node = self._pop_tail()
            del self.cache[lru_node.key]
            self.size -= 1
        
        # Insert new node
        new_node = DLinkedNode(key, value)
        self.cache[key] = new_node
        self._add_node(new_node)
        self.size += 1


# Detailed walkthrough
def demonstrate_manual_lru():
    cache = LRUCacheManual(2)
    
    print("=== Starting LRU Cache (capacity=2) ===")
    
    cache.put(1, 100)
    print("put(1, 100)  -> cache size:", cache.size, "| keys:", list(cache.cache.keys()))
    
    cache.put(2, 200)
    print("put(2, 200)  -> cache size:", cache.size, "| keys:", list(cache.cache.keys()))
    
    print("get(1) ->", cache.get(1), "  (moves key 1 to most recent)")
    
    cache.put(3, 300)  # Should evict key 2 (LRU)
    print("put(3, 300)  -> evicted key 2 | keys:", list(cache.cache.keys()))
    
    print("get(2) ->", cache.get(2), "  (should be -1, evicted)")
    
    cache.put(4, 400)  # Should evict key 1 (now LRU after get(1) and put(3))
    print("put(4, 400)  -> evicted key 1 | keys:", list(cache.cache.keys()))
    
    print("get(1) ->", cache.get(1), "  (should be -1)")
    print("get(3) ->", cache.get(3))
    print("get(4) ->", cache.get(4))

demonstrate_manual_lru()

Let's trace through the linked list state after each operation to solidify understanding:

Initial state:  HEAD <-> TAIL  (dummy nodes only)

After put(1, 100):
  HEAD <-> Node(1) <-> TAIL
  Most recent: Node(1), Least recent: Node(1)

After put(2, 200):
  HEAD <-> Node(2) <-> Node(1) <-> TAIL
  Most recent: Node(2), Least recent: Node(1)

After get(1):  (moves Node(1) to head)
  HEAD <-> Node(1) <-> Node(2) <-> TAIL
  Most recent: Node(1), Least recent: Node(2)

After put(3, 300):  (evicts tail.prev = Node(2))
  Remove Node(2), add Node(3) at head
  HEAD <-> Node(3) <-> Node(1) <-> TAIL
  Most recent: Node(3), Least recent: Node(1)

Key design decisions:

Solution 3: Java LinkedHashMap (Bonus Language Perspective)

Java developers get an even more streamlined approach using LinkedHashMap with a custom constructor that sets accessOrder=true. This changes the map's ordering from insertion-order to access-order, meaning every get and put moves the entry to the end (most recent). Overriding removeEldestEntry handles eviction automatically.

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCacheJava extends LinkedHashMap {
    private final int capacity;
    
    public LRUCacheJava(int capacity) {
        // accessOrder=true: iteration order is from least-recent to most-recent
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        // Evict the eldest entry when size exceeds capacity
        return size() > capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
}

// Usage
// LRUCacheJava cache = new LRUCacheJava(2);
// cache.put(1, 10);
// cache.put(2, 20);
// int val = cache.get(1);  // returns 10, moves 1 to most recent

This is essentially equivalent to the Python OrderedDict approach but baked into Java's standard library. The removeEldestEntry hook is called after every put and putAll; returning true causes the eldest entry to be evicted.

Solution 4: Using functools.lru_cache (Python Decorator)

Python's standard library provides functools.lru_cache as a decorator for automatic memoization with LRU eviction. It's not a general-purpose key-value store — it caches function return values based on arguments — but it's incredibly useful for dynamic programming and expensive computations.

from functools import lru_cache

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

# The cache stores results keyed by argument values
print(fibonacci(100))  # Fast computation, cached intermediate results

# Inspect cache statistics
print(fibonacci.cache_info())  # hits, misses, maxsize, currsize

# Clear the cache if needed
fibonacci.cache_clear()

# Decorator with typed=True separates int and float arguments
@lru_cache(maxsize=256, typed=True)
def process_data(data_id: int, version: str) -> dict:
    # Expensive computation here
    return {"id": data_id, "version": version, "result": data_id * 42}

Important note: lru_cache is for memoization of function calls, not a general-purpose cache store. For arbitrary key-value caching with LRU eviction, use the OrderedDict approach or the manual linked list implementation.

Complexity Analysis

Let's break down the time and space complexity for each approach:

Solution 1: OrderedDict

Solution 2: Doubly Linked List + Hash Map

Solution 3: Java LinkedHashMap

Solution 4: functools.lru_cache

Comparative Table

| Approach              | get()  | put()  | Space  | Language Agnostic? |
|-----------------------|--------|--------|--------|--------------------|
| OrderedDict           | O(1)   | O(1)   | O(n)   | Python only        |
| Linked List + HashMap | O(1)   | O(1)   | O(n)   | Yes                |
| Java LinkedHashMap    | O(1)   | O(1)   | O(n)   | Java only          |
| functools.lru_cache   | O(1)   | O(1)*  | O(m)   | Python only        |

* For lru_cache, "put" is implicit on function call; eviction happens during insertion.

Best Practices and Edge Cases

When implementing an LRU cache in production or during an interview, keep these considerations in mind:

1. Thread Safety

The basic implementations above are not thread-safe. In multi-threaded environments, concurrent get and put calls can corrupt the linked list pointers or the hash map. Solutions include:

2. Handling Capacity Zero

What if capacity=0? The cache should reject all items:

def put(self, key, value):
    if self.capacity == 0:
        return  # Silently ignore, or raise an exception
    # ... rest of logic

3. Handling Duplicate Keys Gracefully

When put is called with an existing key, the value should update and the item should become the most recently used. All three solutions handle this correctly, but it's worth explicitly testing:

cache = LRUCacheManual(2)
cache.put(1, 10)
cache.put(1, 999)  # Update key 1
print(cache.get(1))  # Should return 999, not 10

4. Memory Overhead Awareness

The doubly linked list approach creates one node object per entry. For caches with millions of small entries, this overhead (two pointers + object header) can be significant. In memory-constrained environments:

5. Testing Eviction Order

A common bug is implementing the linked list direction incorrectly. Write tests that verify exact eviction order:

def test_eviction_order():
    cache = LRUCacheManual(3)
    cache.put(1, 'a')
    cache.put(2, 'b')
    cache.put(3, 'c')
    
    # Access 1 (now order: 2(LRU), 3, 1(MRU))
    cache.get(1)
    
    # Access 2 (now order: 3(LRU), 1, 2(MRU))
    cache.get(2)
    
    # Insert 4 — should evict 3 (the LRU)
    cache.put(4, 'd')
    
    assert cache.get(3) == -1, "Key 3 should have been evicted"
    assert cache.get(1) == 'a', "Key 1 should still exist"
    assert cache.get(2) == 'b', "Key 2 should still exist"
    assert cache.get(4) == 'd', "Key 4 should exist"
    print("All eviction order tests passed!")

test_eviction_order()

6. Choosing the Right Implementation for Your Context

7. Time-Based Expiration Extension

Pure LRU only considers recency of access, not age of entries. In production, you often need hybrid eviction — LRU plus time-to-live (TTL). To extend the manual implementation:

import time

class DLinkedNodeWithTTL:
    def __init__(self, key, value, ttl_seconds=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
        self.created_at = time.time()
        self.ttl = ttl_seconds  # None means no expiration
    
    def is_expired(self) -> bool:
        if self.ttl is None:
            return False
        return time.time() - self.created_at > self.ttl


class LRUCacheWithTTL(LRUCacheManual):
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        if node.is_expired():
            self._remove_node(node)
            del self.cache[key]
            self.size -= 1
            return -1
        self._move_to_head(node)
        return node.value
    
    def put(self, key: int, value: int, ttl_seconds=None) -> None:
        # Check for expired entry first
        if key in self.cache:
            node = self.cache[key]
            if node.is_expired():
                self._remove_node(node)
                del self.cache[key]
                self.size -= 1
            else:
                node.value = value
                node.created_at = time.time()
                node.ttl = ttl_seconds
                self._move_to_head(node)
                return
        
        # Evict if at capacity (could also scan for expired entries)
        if self.size >= self.capacity:
            lru_node = self._pop_tail()
            del self.cache[lru_node.key]
            self.size -= 1
        
        new_node = DLinkedNodeWithTTL(key, value, ttl_seconds)
        self.cache[key] = new_node
        self._add_node(new_node)
        self.size += 1

This hybrid approach gives you both recency-based and time-based eviction, which is closer to what production caching systems like Redis offer.

Conclusion

The LRU cache is a deceptively simple data structure that demands careful engineering to achieve true O(1) performance. The combination of a hash map for instant lookup and a doubly linked list for constant-time reordering is a beautiful example of algorithmic synergy — neither data structure alone can satisfy both requirements, but together they form a solution that has stood the test of time.

Whether you reach for Python's OrderedDict for rapid development, implement the manual linked-list approach to demonstrate deep understanding, or leverage functools.lru_cache for automatic memoization, the core principles remain the same: track recency, evict the coldest item, and do it all in constant time. Understanding these internals not only helps in technical interviews but also gives you intuition for designing cache layers, choosing eviction policies, and reasoning about memory-bound system performance in real-world applications.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles