LRU Cache

Overview

An LRU Cache (Least Recently Used Cache) is a fixed-size data structure that evicts the least recently accessed item when the cache is full.

Cache Capacity: 3

Operations:
  PUT(A) → [A]
  PUT(B) → [B, A]
  PUT(C) → [C, B, A]
  GET(A) → [A, C, B]       ← A moves to front
  PUT(D) → [D, A, C]       ← B evicted (least recently used)

The core insight:

Items that were accessed recently are likely to be accessed again soon.

This is called temporal locality and is the foundation of almost every caching system.

Why does it exist?

Caches speed up systems by storing frequently accessed data closer to the consumer.

But caches have limited memory.

When the cache is full, you need to decide which item to remove.

The LRU policy says: remove the item that has gone the longest without being accessed.

Without an eviction policy:

• The cache grows unbounded → out of memory.
• Stale data occupies space → cache becomes useless.
• Cold data blocks hot data → cache hit ratio drops.

LRU provides a simple, effective eviction strategy with O(1) operations.

Real-world Motivation

LRU caching is everywhere.

Operating Systems

Every OS uses LRU (or LRU-approximation) for page replacement.

When physical memory is full, the kernel evicts the least recently used memory page to disk.

Linux uses a two-list LRU variant (active + inactive lists) in its page cache.

CPU Caches

L1, L2, and L3 caches use LRU-like policies to decide which cache line to evict.

Redis

Redis uses an approximated LRU algorithm (allkeys-lru policy). Instead of tracking exact access order for all keys, it samples a subset and evicts the least recently used among the sample.

Memcached

Uses LRU per slab class for memory management.

CDNs

Cloudflare, Akamai, and Fastly use LRU variants to decide which cached assets to keep at edge nodes.

See: CDN for how caching works at the edge.

Databases

MySQL's InnoDB buffer pool uses a modified LRU list. PostgreSQL uses a clock sweep (LRU approximation) for its shared buffer pool.

Web Browsers

Every browser caches HTTP responses, images, and DNS lookups using LRU-based eviction.

Application Frameworks

Python's functools.lru_cache, Guava's CacheBuilder in Java, and Go's groupcache all implement LRU.

Why Existing Solutions Fail

Without caching

Every request hits the database or upstream service.

Client → API → Database

Result: High latency. Database overloaded.

With unbounded cache (no eviction)

Client → API → Cache (grows forever)

Result: Out of memory crash.

With random eviction

Evict a random item when full.

Result: Hot items get evicted. Cache hit ratio is poor.

With FIFO eviction

Evict the oldest item.

Result: Old but frequently used items get evicted.
       A popular resource loaded at startup would be removed.

LRU eviction

Evict the item that hasn't been used for the longest time.

Result: Hot items stay. Cold items leave. Good hit ratio.

LRU is not perfect for every workload (see LFU Cache for frequency-based eviction), but it is the most widely used default because it performs well across diverse access patterns.

Internal Working

The challenge is making both get and put operations run in O(1) time.

The Key Insight

Combine two data structures:

flowchart LR
    subgraph HashMap["Hash Map — O(1) lookup"]
        K1["key₁ → node₁"]
        K2["key₂ → node₂"]
        K3["key₃ → node₃"]
    end

    subgraph DLL["Doubly Linked List — O(1) reorder"]
        direction LR
        HEAD["HEAD"] --> N1["node₁<br/>most recent"]
        N1 --> N2["node₂"]
        N2 --> N3["node₃<br/>least recent"]
        N3 --> TAIL["TAIL"]
        TAIL --> N3
        N3 --> N2
        N2 --> N1
        N1 --> HEAD
    end

    K1 -.-> N1
    K2 -.-> N2
    K3 -.-> N3

• Hash map: maps keys to linked list nodes → O(1) lookup.
• Doubly linked list: maintains access order → O(1) insertion, deletion, and reordering.

GET Operation

flowchart TD
    A["GET(key)"] --> B{"Key in hash map?"}
    B -->|No| C["Return -1<br/>(Cache Miss)"]
    B -->|Yes| D["Find node via hash map"]
    D --> E["Remove node from current position"]
    E --> F["Insert node at head<br/>(most recently used)"]
    F --> G["Return value"]

PUT Operation

flowchart TD
    A["PUT(key, value)"] --> B{"Key in hash map?"}
    B -->|Yes| C["Update value in existing node"]
    C --> D["Move node to head"]
    B -->|No| E{"Cache full?"}
    E -->|Yes| F["Remove tail node<br/>(least recently used)"]
    F --> G["Delete from hash map"]
    G --> H["Create new node"]
    E -->|No| H
    H --> I["Insert node at head"]
    I --> J["Add to hash map"]

Step-by-Step Example

Capacity: 3

PUT(1, "A"):
  List: [1:A]
  Map:  {1 → node}

PUT(2, "B"):
  List: [2:B] → [1:A]
  Map:  {1 → node, 2 → node}

PUT(3, "C"):
  List: [3:C] → [2:B] → [1:A]
  Map:  {1 → node, 2 → node, 3 → node}

GET(1):
  Move 1 to front.
  List: [1:A] → [3:C] → [2:B]
  Return "A"

PUT(4, "D"):
  Cache full. Evict tail → key 2.
  List: [4:D] → [1:A] → [3:C]
  Map:  {1 → node, 3 → node, 4 → node}

GET(2):
  Not found. Return -1. (Cache miss)

Data Structures

Node

Each node in the doubly linked list stores:

Node:
  key:   hashable identifier
  value: cached data
  prev:  pointer to previous node
  next:  pointer to next node

Key is stored in the node so that when evicting from the tail, we can efficiently remove it from the hash map without searching.

Doubly Linked List

HEAD ⟷ node₁ ⟷ node₂ ⟷ node₃ ⟷ TAIL

HEAD and TAIL are sentinel (dummy) nodes.

They simplify edge cases:
  - No null checks when inserting at head.
  - No null checks when removing from tail.
  - Empty list: HEAD ⟷ TAIL

Why doubly linked?

• Singly linked list: removal requires traversal to find previous node → O(n).
• Doubly linked list: each node stores prev → removal is O(1).

Hash Map

HashMap<Key, Node>

  key₁ → pointer to node₁ in the linked list
  key₂ → pointer to node₂ in the linked list
  key₃ → pointer to node₃ in the linked list

This gives O(1) access to any node by key, enabling O(1) repositioning in the list.

Algorithms

Core Operations

get(key)

1. If key not in hash map → return -1
2. node = hash_map[key]
3. Remove node from its current position in the list
4. Insert node right after HEAD (mark as most recently used)
5. Return node.value

put(key, value)

1. If key in hash map:
     a. node = hash_map[key]
     b. node.value = value
     c. Remove node from current position
     d. Insert node right after HEAD
     e. Return

2. If len(hash_map) >= capacity:
     a. tail_node = TAIL.prev  (least recently used)
     b. Remove tail_node from list
     c. Delete hash_map[tail_node.key]

3. Create new_node(key, value)
4. Insert new_node right after HEAD
5. hash_map[key] = new_node

remove_node(node)

node.prev.next = node.next
node.next.prev = node.prev

insert_after_head(node)

node.next = HEAD.next
node.prev = HEAD
HEAD.next.prev = node
HEAD.next = node

All four operations are O(1) — no loops, no traversals.

Implementation

Language Choice

Python

Why Python?

• Clean syntax makes the data structure design easy to understand.
• LRU Cache is a classic interview question — Python is the most common interview language.
• Python's functools.lru_cache uses the same design internally.
• The implementation translates directly to any other language.
• No boilerplate — focus on the algorithm.

Complete Implementation

"""
LRU Cache — O(1) get and put using HashMap + Doubly Linked List.

This is the classic implementation used in system design interviews
and production systems like Redis, Memcached, and OS page caches.
"""


class Node:
    """Doubly linked list node storing a key-value pair."""

    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev: "Node | None" = None
        self.next: "Node | None" = None

    def __repr__(self) -> str:
        return f"Node({self.key}: {self.value})"


class LRUCache:
    """
    Fixed-capacity cache with O(1) get and put.

    Eviction policy: Least Recently Used.

    Internal structure:
        HEAD <-> node1 <-> node2 <-> ... <-> nodeN <-> TAIL
        (most recent)                    (least recent)

        HashMap: key -> Node reference
    """

    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be positive")

        self.capacity = capacity
        self.cache: dict[int, Node] = {}  # key -> Node

        # Sentinel nodes — eliminate edge cases
        self.head = Node()  # dummy head
        self.tail = Node()  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        """
        Retrieve value by key. Returns -1 if not found.
        Moves accessed node to head (most recently used).
        Time: O(1)
        """
        if key not in self.cache:
            return -1

        node = self.cache[key]
        # Move to head — this key was just accessed
        self._remove(node)
        self._insert_after_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        """
        Insert or update a key-value pair.
        If cache is full, evict the least recently used item.
        Time: O(1)
        """
        if key in self.cache:
            # Key exists — update value and move to head
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._insert_after_head(node)
            return

        # Check capacity before inserting
        if len(self.cache) >= self.capacity:
            # Evict the least recently used (tail.prev)
            lru_node = self.tail.prev
            self._remove(lru_node)
            del self.cache[lru_node.key]

        # Insert new node at head
        new_node = Node(key, value)
        self._insert_after_head(new_node)
        self.cache[key] = new_node

    def _remove(self, node: Node) -> None:
        """
        Remove a node from the doubly linked list.
        Time: O(1)
        """
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_after_head(self, node: Node) -> None:
        """
        Insert a node right after the dummy head.
        This position represents "most recently used."
        Time: O(1)
        """
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def _get_order(self) -> list[tuple[int, int]]:
        """Helper: return items in order from most to least recently used."""
        result = []
        current = self.head.next
        while current != self.tail:
            result.append((current.key, current.value))
            current = current.next
        return result

    def __len__(self) -> int:
        return len(self.cache)

    def __contains__(self, key: int) -> bool:
        return key in self.cache

    def __repr__(self) -> str:
        items = self._get_order()
        return f"LRUCache(cap={self.capacity}, items={items})"

Test Harness

"""Test harness for LRU Cache implementation."""


def test_basic_operations():
    """Test basic get/put behavior."""
    print("=== Test: Basic Operations ===")

    cache = LRUCache(2)

    cache.put(1, 10)
    cache.put(2, 20)
    print(f"After PUT(1,10), PUT(2,20): {cache}")

    result = cache.get(1)
    print(f"GET(1) = {result}")  # Expected: 10
    assert result == 10

    # This should evict key 2 (least recently used)
    cache.put(3, 30)
    print(f"After PUT(3,30): {cache}")

    result = cache.get(2)
    print(f"GET(2) = {result}")  # Expected: -1 (evicted)
    assert result == -1

    result = cache.get(3)
    print(f"GET(3) = {result}")  # Expected: 30
    assert result == 30

    print("✓ Basic operations passed\n")


def test_update_existing_key():
    """Test that updating an existing key moves it to front."""
    print("=== Test: Update Existing Key ===")

    cache = LRUCache(2)

    cache.put(1, 10)
    cache.put(2, 20)
    print(f"Initial: {cache}")

    # Update key 1 — should move to front
    cache.put(1, 100)
    print(f"After PUT(1,100): {cache}")

    # Key 2 is now least recently used
    cache.put(3, 30)
    print(f"After PUT(3,30): {cache}")

    result = cache.get(2)
    print(f"GET(2) = {result}")  # Expected: -1 (evicted)
    assert result == -1

    result = cache.get(1)
    print(f"GET(1) = {result}")  # Expected: 100 (updated value)
    assert result == 100

    print("✓ Update existing key passed\n")


def test_eviction_order():
    """Test that eviction follows LRU order correctly."""
    print("=== Test: Eviction Order ===")

    cache = LRUCache(3)

    cache.put(1, 10)
    cache.put(2, 20)
    cache.put(3, 30)
    print(f"Full cache: {cache}")

    # Access key 1 — moves it to front
    cache.get(1)
    print(f"After GET(1): {cache}")

    # Access key 2 — moves it to front
    cache.get(2)
    print(f"After GET(2): {cache}")

    # Now order is: 2, 1, 3 (3 is LRU)
    # Adding key 4 should evict key 3
    cache.put(4, 40)
    print(f"After PUT(4,40): {cache}")

    result = cache.get(3)
    print(f"GET(3) = {result}")  # Expected: -1 (evicted)
    assert result == -1

    assert cache.get(1) == 10
    assert cache.get(2) == 20
    assert cache.get(4) == 40

    print("✓ Eviction order passed\n")


def test_capacity_one():
    """Edge case: cache with capacity 1."""
    print("=== Test: Capacity 1 ===")

    cache = LRUCache(1)

    cache.put(1, 10)
    print(f"After PUT(1,10): {cache}")

    result = cache.get(1)
    print(f"GET(1) = {result}")  # Expected: 10
    assert result == 10

    cache.put(2, 20)
    print(f"After PUT(2,20): {cache}")

    result = cache.get(1)
    print(f"GET(1) = {result}")  # Expected: -1 (evicted)
    assert result == -1

    result = cache.get(2)
    print(f"GET(2) = {result}")  # Expected: 20
    assert result == 20

    print("✓ Capacity 1 passed\n")


def test_leetcode_example():
    """LeetCode 146 example for verification."""
    print("=== Test: LeetCode 146 Example ===")

    cache = LRUCache(2)

    cache.put(1, 1)
    cache.put(2, 2)
    assert cache.get(1) == 1

    cache.put(3, 3)  # evicts key 2
    assert cache.get(2) == -1

    cache.put(4, 4)  # evicts key 1
    assert cache.get(1) == -1
    assert cache.get(3) == 3
    assert cache.get(4) == 4

    print("✓ LeetCode 146 example passed\n")


if __name__ == "__main__":
    test_basic_operations()
    test_update_existing_key()
    test_eviction_order()
    test_capacity_one()
    test_leetcode_example()
    print("All tests passed! ✓")

Sample Output

=== Test: Basic Operations ===
After PUT(1,10), PUT(2,20): LRUCache(cap=2, items=[(2, 20), (1, 10)])
GET(1) = 10
After PUT(3,30): LRUCache(cap=2, items=[(3, 30), (1, 10)])
GET(2) = -1
GET(3) = 30
✓ Basic operations passed

=== Test: Update Existing Key ===
Initial: LRUCache(cap=2, items=[(2, 20), (1, 10)])
After PUT(1,100): LRUCache(cap=2, items=[(1, 100), (2, 20)])
After PUT(3,30): LRUCache(cap=2, items=[(3, 30), (1, 100)])
GET(2) = -1
GET(1) = 100
✓ Update existing key passed

=== Test: Eviction Order ===
Full cache: LRUCache(cap=3, items=[(3, 30), (2, 20), (1, 10)])
After GET(1): LRUCache(cap=3, items=[(1, 10), (3, 30), (2, 20)])
After GET(2): LRUCache(cap=3, items=[(2, 20), (1, 10), (3, 30)])
After PUT(4,40): LRUCache(cap=3, items=[(4, 40), (2, 20), (1, 10)])
GET(3) = -1
✓ Eviction order passed

=== Test: Capacity 1 ===
After PUT(1,10): LRUCache(cap=1, items=[(1, 10)])
GET(1) = 10
After PUT(2,20): LRUCache(cap=1, items=[(2, 20)])
GET(1) = -1
GET(2) = 20
✓ Capacity 1 passed

=== Test: LeetCode 146 Example ===
✓ LeetCode 146 example passed

All tests passed! ✓

Complexity

Overall space complexity:

O(capacity)

Each entry stores:
  - Hash map entry: key + pointer to node
  - Linked list node: key + value + 2 pointers

Total: O(capacity) × (key + value + 3 pointers)

The O(1) guarantee for all operations is what makes LRU Cache a favorite in interviews and production.

Trade-offs

Advantages

• O(1) get and put — the fastest cache operations possible.
• Simple to understand and implement.
• Works well for most access patterns with temporal locality.
• Battle-tested — used in operating systems, databases, and web infrastructure.
• Deterministic behavior — easy to reason about and debug.

Disadvantages

• Scan pollution: A sequential scan of many keys can evict all hot items. Example: A batch job reads 1 million cold keys → all hot cache entries are evicted.
• No frequency awareness: An item accessed 1,000 times has the same priority as one accessed once, if the single-access item was more recent.
• Per-item tracking overhead: Every item needs 2 extra pointers (prev/next) and a hash map entry.
• Not thread-safe by default: Requires locking for concurrent access.

Alternatives

See: Caching Strategies for a deeper comparison of eviction policies.

Production Improvements

Thread Safety

Production LRU caches must be thread-safe.

Option 1: Global mutex

mutex.lock()
  get() or put()
mutex.unlock()

Simple but creates contention under high concurrency.

Option 2: Sharded LRU

Partition keys across multiple independent LRU caches.

Shard = hash(key) % num_shards

Each shard has its own lock.

Result: num_shards × less contention.

This is what Memcached does internally.

Option 3: Lock-free approximation

Redis uses approximated LRU: sample N random keys and evict the one with the oldest access timestamp. No linked list, no locks on the eviction path.

TTL (Time-to-Live)

Production caches add expiration:

put(key, value, ttl=60s)

After 60 seconds, the entry becomes invalid.

Two strategies:

• Lazy expiration: Check TTL on access. Only delete if expired.
• Active expiration: Background thread periodically scans for expired keys.

Redis uses both.

Size-Aware Eviction

Not all values are the same size.

A 10 MB image and a 100-byte JSON object both count as "one item" in basic LRU.

Production caches often track total memory usage and evict until memory drops below a threshold.

Metrics and Monitoring

Track:

• Hit ratio: hits / (hits + misses) — the most important cache metric.
• Eviction rate: how often items are evicted.
• Memory usage: current vs. maximum.
• Latency: p50, p99 for get/put operations.
• Hot keys: most frequently accessed items.

Persistence

Some caches persist data to disk for crash recovery:

• Redis RDB: periodic snapshots.
• Redis AOF: append-only file logging every write.

See: Caching Strategies for persistence patterns.

Replication

For high availability:

Primary LRU Cache
    │
    ├── Replica 1 (read-only)
    ├── Replica 2 (read-only)
    └── Replica 3 (read-only)

Writes go to primary. Reads distributed across replicas.

Common Bugs

1. Forgetting to store the key in the node

When evicting from the tail, you need the key to remove it from the hash map. If the node doesn't store the key, you must scan the entire hash map — breaking the O(1) guarantee.

2. Not using sentinel nodes

Without dummy head/tail, every operation needs null checks for edge cases (empty list, single element, etc.). Sentinel nodes eliminate these bugs entirely.

3. Incorrect pointer updates during removal

The four-pointer update in remove and insert is error-prone. Off-by-one pointer assignment causes list corruption.

Always draw the diagram:

Before: A ⟷ B ⟷ C
Remove B:
  A.next = C
  C.prev = A

4. Not moving node to head on GET

A common mistake is only moving nodes on put. The get operation must also update recency, otherwise the eviction order is wrong.

5. Not deleting from hash map on eviction

Evicting from the linked list but forgetting to remove the hash map entry causes ghost references and memory leaks.

6. Capacity zero

Not validating capacity > 0 in the constructor. A zero-capacity cache causes division errors or infinite loops.

7. Thread safety in concurrent access

Two threads simultaneously accessing the same node can corrupt the linked list. Always protect with a lock or use a sharded design.

8. Memory leaks in languages without GC

In C/C++, removed nodes must be explicitly freed. In garbage-collected languages (Python, Java, Go), circular references in the linked list can delay collection.

Interview Questions

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

Hint: Doubly linked list for order + hash map for O(1) lookup. Sentinel nodes for clean edge cases.

2. How would you make an LRU Cache thread-safe?

Hint: Mutex per cache (simple) or sharded caches with per-shard locks (scalable). Consider read-write locks if reads dominate.

3. What is the difference between LRU and LFU? When would you choose each?

Hint: LRU tracks recency, LFU tracks frequency. LRU suffers from scan pollution. LFU is slow to adapt. W-TinyLFU combines both.

4. How does Redis implement LRU eviction without a linked list?

Hint: Approximated LRU. Each key stores a last-access timestamp. On eviction, sample N random keys and evict the oldest. Configurable sample size.

5. How would you implement an LRU Cache that also supports TTL?

Hint: Add an expires_at field to each node. On get, check if expired — treat as miss and remove. Background thread for proactive cleanup.

Used By

This concept is required before understanding:

• ✅ Caching Strategies
• ✅ CDN
• ✅ API Gateway
• ✅ Load Balancer
• ✅ Rate Limiter
• ✅ TinyURL
• ✅ WhatsApp

Related Topics

Prerequisites

• Hashing & Hash Functions
• Caching Strategies

Next Topics

• LFU Cache
• Cache Invalidation
• Cache Eviction
• Consistent Hashing
• Distributed Cache

Related Pages

• Bloom Filters
• CDN
• API Gateway
• Database Indexing

Try It Yourself

Exercise

Extend the LRU Cache to support TTL (Time-to-Live):

• put(key, value, ttl_seconds) — the entry expires after ttl_seconds.
• get(key) — return -1 if the key has expired.
• Expired entries should be lazily removed on access.
• Add a cleanup() method that removes all expired entries.

Advanced Challenge

Implement a Sharded LRU Cache for concurrent access:

• Partition keys across N shards using a hash function.
• Each shard is an independent LRU Cache with its own lock.
• Support get, put, delete, and stats operations.
• Track per-shard hit/miss ratios.
• Benchmark against a single-lock LRU Cache to measure throughput improvement.
• Use Python's threading module or Go's goroutines.

Website Integration

Suggested URL

/system-design/caching/lru-cache

Breadcrumb

System Design

→ Caching

→ LRU Cache

Sidebar Category

Caching

Previous Page

HTTPS & TLS

Next Page

LFU Cache

Related Links

• Hashing & Hash Functions
• Caching Strategies
• CDN
• Bloom Filters
• API Gateway
• TinyURL
• WhatsApp

Hero Illustration Prompt

"A clean technical illustration showing an LRU Cache as a horizontal doubly linked list with nodes flowing from Most Recently Used (left) to Least Recently Used (right). Above the list, a hash map connects keys to nodes with dotted arrows. Show an eviction happening at the tail with a fading-out node, and a new insertion at the head with a glowing node. Modern flat engineering style with warm orange and teal accents, suitable for a backend engineering learning platform."

SEO Meta Description

Learn LRU Cache from first principles. Understand the doubly linked list + hash map design for O(1) operations, build a complete implementation in Python with test harness, and apply it to real system design interviews, Redis, Memcached, and OS page caches.