LRU Cache: Least Recently Used Implementation

Key Insights

LRU cache achieves O(1) time complexity for both get and put operations by combining a hash map with a doubly linked list—the map provides constant-time lookups while the list maintains access order.
The most common implementation mistake is using a singly linked list, which forces O(n) deletion and defeats the purpose of caching.
Python’s OrderedDict and Java’s LinkedHashMap provide production-ready LRU implementations, but understanding the underlying mechanics is essential for interviews and custom requirements.

Introduction to LRU Cache

Caching is the art of keeping frequently accessed data close at hand. But caches have limited capacity, so when they fill up, something has to go. The eviction policy—the rule for deciding what gets removed—determines how effective your cache will be.

Least Recently Used (LRU) is one of the most popular eviction policies because it’s based on a simple but powerful assumption: if you haven’t accessed something recently, you’re less likely to need it soon. This temporal locality principle holds true across many domains.

You encounter LRU caches constantly:

Browser caches store recently visited pages and assets
Database query caches keep hot query results in memory
CDN edge nodes cache popular content closer to users
CPU caches use LRU variants to manage memory hierarchies
Connection pools evict idle connections based on last use

The challenge is implementing LRU efficiently. A naive approach might work for small caches, but production systems need O(1) operations. Let’s build one from scratch.

How LRU Works

The LRU policy is straightforward: when the cache is full and a new item arrives, evict the item that was accessed least recently. Every access—whether a read or write—updates an item’s “recency.”

Let’s trace through operations on a cache with capacity 3:

Operation          Cache State (most recent → least recent)    Result
---------          -----------------------------------------    ------
put(1, "A")        [1:A]                                        -
put(2, "B")        [2:B, 1:A]                                   -
put(3, "C")        [3:C, 2:B, 1:A]                              -
get(1)             [1:A, 3:C, 2:B]                              "A" (1 moves to front)
put(4, "D")        [4:D, 1:A, 3:C]                              - (2 evicted, was least recent)
get(2)             [4:D, 1:A, 3:C]                              None (2 was evicted)
put(1, "X")        [1:X, 4:D, 3:C]                              - (1 updated and moved to front)

Notice how accessing key 1 moved it to the front, which saved it from eviction when key 4 arrived. Key 2, sitting at the back, was the victim instead.

Data Structure Design

The requirements for an efficient LRU cache are:

O(1) lookup by key
O(1) insertion at the front (most recent position)
O(1) deletion from any position
O(1) removal from the back (least recent position)

No single data structure provides all of these. Hash maps give O(1) lookup but don’t maintain order. Linked lists maintain order but require O(n) search. The solution is to combine them.

A hash map stores key-to-node mappings for instant lookup. A doubly linked list maintains access order, with the most recent item at the head and the least recent at the tail. Each node in the list contains the key-value pair, and the map points directly to these nodes.

The doubly linked list is critical. With a singly linked list, removing a node requires finding its predecessor, which takes O(n) time. Doubly linked nodes store pointers in both directions, enabling O(1) removal.

class Node:
    """Doubly linked list node storing key-value pairs."""
    def __init__(self, key: int = 0, value: int = 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 = {}  # key -> Node
        
        # Dummy head and tail simplify edge cases
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

The dummy head and tail nodes are a crucial implementation detail. They eliminate null checks when inserting at the front or removing from the back, making the code cleaner and less error-prone.

Core Operations Implementation

With the data structures in place, the operations become straightforward. We need four helper methods for list manipulation, then the public get and put methods.

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_to_front(self, node: Node) -> None:
        """Insert node right after head (most recent position)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node: Node) -> None:
        """Remove node from its current position in the list."""
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _move_to_front(self, node: Node) -> None:
        """Move existing node to the front (mark as most recent)."""
        self._remove_node(node)
        self._add_to_front(node)
    
    def _evict_lru(self) -> Node:
        """Remove and return the least recently used node."""
        lru = self.tail.prev
        self._remove_node(lru)
        return lru
    
    def get(self, key: int) -> int:
        """Retrieve value by key, marking it as recently used."""
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self._move_to_front(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        """Insert or update key-value pair."""
        if key in self.cache:
            # Update existing: change value and move to front
            node = self.cache[key]
            node.value = value
            self._move_to_front(node)
        else:
            # Insert new: create node, add to front
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_front(node)
            
            # Evict if over capacity
            if len(self.cache) > self.capacity:
                lru = self._evict_lru()
                del self.cache[lru.key]

The key insight is that every access—whether get or put—moves the node to the front. This maintains the invariant that nodes closer to the tail are older.

Complexity Analysis

Both get and put operations run in O(1) time:

Operation	Hash Map	Linked List	Total
get	O(1) lookup	O(1) move to front	O(1)
put (new)	O(1) insert	O(1) add + O(1) evict	O(1)
put (update)	O(1) lookup	O(1) move to front	O(1)

Space complexity is O(capacity) for storing the nodes and hash map entries.

Compare this to naive alternatives:

Array-based: O(n) to find and remove the LRU item, O(n) to shift elements
Single linked list + map: O(1) lookup, but O(n) to remove (must find predecessor)
Sorted by timestamp: O(n) insertion to maintain order, or O(n) eviction to find minimum

The hash map + doubly linked list combination is optimal.

Language-Specific Implementations

Most languages provide ordered dictionaries that can simplify LRU implementation. Python’s OrderedDict maintains insertion order and supports moving items to the end:

from collections import OrderedDict

class LRUCache:
    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 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 oldest

Java’s LinkedHashMap offers similar functionality with an access-order mode:

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        // accessOrder=true enables LRU ordering
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

These built-in solutions are battle-tested and should be preferred in production code. The manual implementation is valuable for interviews, custom requirements, or when you need features these libraries don’t provide.

Variations and Extensions

Real-world caches often need capabilities beyond basic LRU:

LRU-K tracks the K-th most recent access rather than just the last one. This prevents “cache pollution” where a one-time sequential scan evicts frequently-used items. LRU-2 is common in database buffer pools.

TTL-based expiration adds time limits to cached items. You can implement this by storing timestamps and checking expiration on access, or by running a background cleanup thread.

Thread-safe LRU is essential for concurrent applications:

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) -> 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) -> None:
        with self.lock:
            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)

A reentrant lock (RLock) allows the same thread to acquire the lock multiple times, which is safer if your methods call each other.

Distributed LRU caches like Redis or Memcached handle multi-node scenarios. They use consistent hashing to distribute keys across nodes and implement approximate LRU due to the overhead of maintaining perfect ordering across a network.

The LRU cache is a fundamental building block that appears everywhere from operating systems to web applications. Understanding its mechanics—and the elegant combination of hash maps and doubly linked lists—gives you a powerful tool for both system design interviews and real-world performance optimization.