DSA Advanced

LRU Cache Eviction — Missing DLL Removal Causes 4GB Leak

Q: Why use sentinel head and tail nodes?

Sentinel nodes eliminate null checks in insert and remove operations. Without them, every insert/remove must check 'is this node the head?' and 'is this node the tail?' With sentinels, head.next is always the MRU node and tail.prev is always the LRU node — the code is cleaner and less error-prone.

Q: What is the difference between LRU, LFU, and FIFO caches?

LRU (Least Recently Used) evicts the item not accessed for the longest time. LFU (Least Frequently Used) evicts the item accessed the fewest times — useful when access frequency is a better predictor than recency. FIFO (First In First Out) evicts the oldest inserted item regardless of access pattern. LRU is the most common in practice because it adapts well to temporal locality.

Q: Can Python's OrderedDict implement an LRU cache?

Yes. Python's collections.OrderedDict maintains insertion order and supports move_to_end(key) in O(1). Use it as: get moves key to end (MRU), put moves to end and pops the first item (LRU) if over capacity. Python's functools.lru_cache decorator implements this pattern exactly.

Q: How is Java's LinkedHashMap related to LRU cache?

Java's LinkedHashMap can implement LRU by setting accessOrder=true in the constructor and overriding removeEldestEntry(). However, this hides the pointer manipulation internally. Implementing from scratch with HashMap + custom DLL demonstrates understanding of the underlying mechanics — which is what interviewers test.

Q: How do you make an LRU cache thread-safe?

Wrap all get and put operations in a synchronized block or use a ReentrantReadWriteLock — reads (get) acquire the read lock, writes (put) acquire the write lock. For high contention, consider a sharded LRU cache where keys are partitioned across multiple independent LRU caches, each with its own lock.

Q: What happens when cache capacity is 1?

Every put of a new key evicts the current entry. The DLL always has exactly one node between head and tail. head.next == tail.prev. This is a valid edge case that must be tested explicitly.

📅 March 05, 2026 ⏱ 8 min read 🎯 Advanced

Where developers are forged. · Structured learning · Free forever.

📍 Part of: Linked List → Topic 9 of 10

Heap grew 4GB in 6 hours — eviction missed DLL removal.

🔥 Advanced — solid DSA foundation required

In this tutorial, you'll learn

Heap grew 4GB in 6 hours — eviction missed DLL removal.

LRU Cache provides O(1) get and put by combining a hash map (lookup) with a DLL (order maintenance).
DLL head = most recently used (MRU), tail = least recently used (LRU).
On get: move accessed node to head. On put: insert at head, evict tail if over capacity.

✦ Plain-English analogy ✦ Real code with output ✦ Interview questions

⚡Quick Answer

Core data structures: HashMap for O(1) key lookup + Doubly Linked List for O(1) order maintenance.
DLL head = most recently used (MRU). DLL tail = least recently used (LRU).
On get: move accessed node to head. On put: insert at head, evict tail.prev if over capacity.
Sentinel head/tail nodes eliminate all null-check edge cases in insert/remove.
Production risk: forgetting to update both the map and the DLL during eviction causes memory leaks or stale references.
Real-world: CPU caches, Redis, CDN edge nodes, database buffer pools all use LRU eviction.

🚨 START HERE

LRU Cache Triage Cheat Sheet

Fast commands to diagnose common production issues with LRU cache implementations.

🟡

Memory grows unboundedly — eviction appears broken.

Immediate ActionHeap dump to compare DLL node count vs HashMap entry count.

Commands

jcmd <pid> GC.heap_dump /tmp/heap.hprof

jmap -histo <pid> | grep Node (count Node instances)

Fix NowIf DLL node count >> HashMap size, eviction is not removing from DLL. Check the eviction code path for a missing _remove() call.

🟡

NullPointerException in cache get/put — sporadic crashes.

Immediate ActionThread dump to confirm stack trace location.

Commands

jcmd <pid> Thread.print

grep -r 'sentinel\|dummy' src/ (verify sentinel initialization)

Fix NowEnsure sentinel head and tail are initialized in the constructor and never set to null.

🟡

Cache hit rate drops to near zero after deployment.

Immediate ActionAdd metrics: cache.hits, cache.misses, cache.evictions. Compare pre/post deployment.

Commands

Check monitoring dashboard for hit_rate metric

jcmd <pid> GC.class_histogram (check for unexpected object growth)

Fix NowVerify get() calls _remove() then _insert_front() in that order. Missing either breaks the promotion-to-MRU logic.

Production Incident

The Session Cache That Leaked 4GB of Memory

A web application's session cache used an LRU cache to store user sessions. After a deployment, the cache grew unboundedly, consuming 4GB of heap and triggering OOM kills every 6 hours. The eviction path was broken — the DLL was never trimmed.

SymptomHeap usage grows linearly after deployment. OOM kills every 6 hours. Thread dump shows cache put operations succeeding but no evictions. Heap dump shows millions of SessionNode objects unreachable from the HashMap but still referenced by the DLL.

AssumptionThe team initially blamed a memory leak in the session serialization layer, because the heap dump showed millions of SessionNode objects. The root cause was misattributed to a third-party library.

Root causeA recent refactoring changed the eviction logic. The original code removed the LRU node from both the DLL and the HashMap during eviction. The refactored code only removed the node from the HashMap (del self.map[lru.key]) but forgot to call _remove(lru) on the DLL. The DLL grew unboundedly, keeping every evicted node alive through the DLL's next/prev pointers. The HashMap was correct, but the DLL leaked memory.

Fix1. Restored the _remove(lru) call before del self.map[lru.key] in the eviction path. 2. Added an invariant check: assert len(self.map) == self._dll_size() in debug builds. 3. Added a metric: cache.dll.size vs cache.map.size — alert if they diverge. 4. Added integration tests that verify DLL and HashMap sizes match after 100K put operations with capacity=100.

Key Lesson

Every eviction must update BOTH the HashMap and the DLL. Missing either causes a memory leak or stale references.After any refactoring of cache eviction logic, verify that the DLL and HashMap remain in sync by comparing their sizes.Add invariant assertions in debug builds: DLL Heap dumps showing objects unreachable from the HashMap but alive in the DLL are a strong signal of a broken eviction path.

Production Debug Guide

Symptom-driven investigation paths for cache-related incidents.

Memory grows unboundedly despite fixed cache capacity.→Check if eviction removes nodes from BOTH the HashMap and the DLL. A missing DLL removal causes the DLL to grow while the HashMap stays correct.

Cache hit rate drops after a deployment.→Verify that get() moves the accessed node to the head (MRU position). If the move-to-head logic is broken, recently accessed items are evicted prematurely.

NullPointerException during get or put.→Check if sentinel head/tail nodes are properly initialized. Missing sentinel initialization causes null dereference on the first insert or remove.

Duplicate keys in the DLL but not in the HashMap.→Check if put() for an existing key removes the old node from the DLL before inserting the new one. Missing the remove step creates duplicate DLL entries.

Cache returns stale values after put with existing key.→Verify that put() with an existing key updates the node's value AND moves it to the head. Updating the value without moving to head preserves stale ordering.

LRU (Least Recently Used) eviction is the industry-standard cache replacement policy. It works because most workloads exhibit temporal locality — data accessed recently is more likely to be accessed again soon. CPU L1/L2 caches, Redis, database buffer pools, and CDN edge nodes all rely on LRU.

The challenge: both get and put must run in O(1) time. A plain array requires O(n) to find and move elements. A single linked list requires O(n) to find a node by key. The solution pairs a HashMap (O(1) lookup by key) with a doubly linked list (O(1) insertion/deletion at any known node). Neither structure alone suffices.

A common misconception is that LinkedHashMap alone implements LRU. It can, but only with accessOrder=true and careful override of removeEldestEntry. A from-scratch implementation demonstrates understanding of the pointer manipulation that LinkedHashMap hides internally.

What is LRU Cache? — Plain English

An LRU (Least Recently Used) Cache evicts the least recently accessed item when the cache is full and a new item must be inserted. It is a fixed-capacity key-value store where both get and put run in O(1).

Real-world use: CPU caches, DNS resolver caches, web browser caches, database buffer pools. When storage is limited, you want to keep the items most likely to be accessed again — which are usually the recently used ones.

Implementation: combine a hash map (for O(1) key lookup) with a doubly linked list (for O(1) order maintenance). The DLL head = most recently used, DLL tail = least recently used.

Mental Model

The Desk Analogy

Why LRU matches real-world access patterns

Your desk holds 5 folders. You work on folder A, then B, then C.
When folder D arrives and the desk is full, you evict the oldest untouched folder.
The folders you touched recently are the ones you will likely need again.
This temporal locality is why LRU outperforms random eviction in most workloads.

📊 Production Insight

LRU is not always the best eviction policy. For workloads with scan patterns (e.g., full-table scans in databases), LRU thrashes — the scan evicts all hot data. In these cases, variants like LRU-K (tracks last K accesses) or ARC (Adaptive Replacement Cache) perform better. Know your access pattern before choosing LRU.

🎯 Key Takeaway

LRU evicts the least recently accessed item. It works because most workloads exhibit temporal locality. The O(1) requirement forces a dual-structure design: HashMap + Doubly Linked List.

How LRU Cache Works — Step by Step

Data structures

hash map: key -> node in DLL
DLL: maintains access order (head=MRU, tail=LRU)
Use sentinel head and tail nodes to simplify edge cases

get(key) O(1): 1. If key not in map: return -1. 2. Move the node to the front of the DLL (most recently used). 3. Return the node's value.

put(key, value) O(1): 1. If key already in map: update value, move node to front. 2. Else: create new node, insert at front, add to map. 3. If cache exceeds capacity: remove the LRU node (tail.prev), delete from map.

🔥Why Two Structures?

HashMap alone: O(1) lookup but no ordering — cannot find the LRU item in O(1).
DLL alone: O(1) insert/remove at known positions but O(n) to find a node by key.
Combined: HashMap finds the node in O(1). DLL maintains eviction order in O(1).
The HashMap value is a pointer to the DLL node — this is the bridge between the two structures.

📊 Production Insight

The eviction path is the most failure-prone operation. It must atomically update both the HashMap and the DLL. If the HashMap removal succeeds but the DLL removal fails (or is skipped), the evicted node remains reachable through the DLL, causing a memory leak. Always remove from the DLL first, then from the HashMap.

🎯 Key Takeaway

The two-structure design is non-negotiable for O(1) operations. The HashMap bridges key lookup to DLL node pointers. The DLL maintains eviction order. The eviction path must update both structures atomically.

LRU Operation Decision Flow

Ifget(key): key exists in HashMap

→

UseRemove node from DLL, insert at head (MRU). Return value.

Ifget(key): key not in HashMap

→

UseReturn -1 (cache miss). No state change.

Ifput(key, value): key exists

→

UseRemove old node from DLL. Update value. Insert at head. No eviction.

Ifput(key, value): key is new, cache not full

→

UseCreate node, insert at head, add to HashMap. No eviction.

Ifput(key, value): key is new, cache is full

→

UseEvict tail.prev (LRU): remove from DLL and HashMap. Then insert new node at head.

Worked Example — Tracing the Algorithm

LRU Cache capacity=3. Operations: put(1,A), put(2,B), put(3,C), get(1), put(4,D), get(2).

put(1,A): cache=[1:A]. DLL: head<->1<->tail. put(2,B): cache=[1:A, 2:B]. DLL: head<->2<->1<->tail. (2 is MRU) put(3,C): cache=[1:A, 2:B, 3:C]. DLL: head<->3<->2<->1<->tail. get(1): 1 exists. Move 1 to front. DLL: head<->1<->3<->2<->tail. Return A. put(4,D): cache full (size=3). Insert 4, evict LRU=tail.prev=2. Remove 2 from map and DLL. Insert 4 at front. cache=[1:A, 3:C, 4:D]. DLL: head<->4<->1<->3<->tail. get(2): 2 not in cache. Return -1. (Was evicted.)

Key insight: get(1) promoted key 1 to MRU, saving it from eviction when key 4 was inserted.

💡Pro Tip: Trace With Concrete Values

When debugging LRU cache issues, draw the DLL state after each operation. Label each node with its key and mark the head (MRU) and tail.prev (LRU). This visual trace immediately reveals ordering bugs that are invisible in code.

📊 Production Insight

The worked example demonstrates the promotion effect: get(1) moved key 1 to MRU, which saved it from eviction. Without this promotion, key 1 would have been evicted instead of key 2. This is the core behavior that distinguishes LRU from FIFO — access recency, not insertion order, determines eviction.

🎯 Key Takeaway

Tracing with concrete values reveals the promotion mechanic that distinguishes LRU from FIFO. The get operation is not just a lookup — it is a state mutation that changes eviction priority.

Implementation

Sentinel head and tail nodes eliminate all null-pointer edge cases. _remove unlinks a node by connecting its neighbours directly. _insert_front places a node right after the sentinel head (MRU position). get moves the accessed node to the front. put inserts at the front and evicts tail.prev when over capacity. The hash map (self.map) gives O(1) node lookup; the DLL gives O(1) order updates.

LRUCache.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134

package io.thecodeforge.cache;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU Cache using HashMap + Doubly Linked List.
 * O(1) get and put. Sentinel nodes eliminate null-check edge cases.
 */
public class LRUCache {

    // --- Internal node for the doubly linked list ---
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {\n            this.key = key;\n            this.value = value;\n        }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head; // sentinel — head.next is MRU
    private final Node tail; // sentinel — tail.prev is LRU

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();

        // Sentinel nodes: never null, always present
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    // --- Remove a node from the DLL (O(1)) ---
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // --- Insert a node at the front (MRU position) (O(1)) ---
    private void insertFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * Get value by key. Moves accessed node to MRU position.
     * Returns -1 if key not found.
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);          // unlink from current position
        insertFront(node);     // promote to MRU
        return node.value;
    }

    /**
     * Insert or update key-value pair.
     * If cache is full, evicts the LRU item first.
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // Key exists: update value and promote to MRU
            Node existing = map.get(key);
            existing.value = value;
            remove(existing);
            insertFront(existing);
        } else {
            // New key: create node and insert at MRU
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            insertFront(newNode);

            // Evict if over capacity
            if (map.size() > capacity) {
                Node lru = tail.prev; // least recently used
                remove(lru);          // remove from DLL FIRST
                map.remove(lru.key);  // then remove from map
            }
        }
    }

    // --- Debug: verify DLL and map are in sync ---
    public int dllSize() {
        int count = 0;
        Node current = head.next;
        while (current != tail) {
            count++;
            current = current.next;
        }
        return count;
    }

    public boolean isConsistent() {
        return map.size() == dllSize();
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);

        cache.put(1, 100);
        cache.put(2, 200);
        cache.put(3, 300);
        System.out.println("After 3 puts: " + cache.map.keySet());
        System.out.println("DLL size: " + cache.dllSize() + ", Map size: " + cache.map.size());
        System.out.println("Consistent: " + cache.isConsistent());

        System.out.println("get(1): " + cache.get(1)); // promotes 1 to MRU

        cache.put(4, 400); // evicts 2 (LRU)
        System.out.println("After put(4): " + cache.map.keySet());
        System.out.println("get(2): " + cache.get(2)); // -1 (evicted)
        System.out.println("get(1): " + cache.get(1)); // 100 (was promoted)
        System.out.println("Consistent: " + cache.isConsistent());

        // Edge case: capacity 1
        LRUCache tiny = new LRUCache(1);
        tiny.put(1, 10);
        tiny.put(2, 20); // evicts 1
        System.out.println("\nCapacity 1 cache:");
        System.out.println("get(1): " + tiny.get(1)); // -1
        System.out.println("get(2): " + tiny.get(2)); // 20
        System.out.println("Consistent: " + tiny.isConsistent());
    }
}

▶ Output

After 3 puts: [1, 2, 3]
DLL size: 3, Map size: 3
Consistent: true
get(1): 100
After put(4): [1, 3, 4]
get(2): -1
get(1): 100
Consistent: true

Capacity 1 cache:
get(1): -1
get(2): 20
Consistent: true

⚠ Watch Out: Eviction Order Matters

During eviction, remove the node from the DLL BEFORE removing it from the HashMap. If you remove from the HashMap first and an exception occurs during DLL removal, the DLL has a dangling node that is unreachable from the HashMap but still connected in the list — a silent memory leak. DLL-first removal is the safer order.

📊 Production Insight

The isConsistent() method — which verifies DLL size equals HashMap size — should be enabled in debug builds and integration tests. It catches the most common LRU bug: DLL and HashMap falling out of sync due to a missing removal in one of the two structures.

🎯 Key Takeaway

Sentinel nodes eliminate null checks. The eviction order (DLL first, then HashMap) prevents silent memory leaks. The isConsistent() invariant check catches sync bugs between the two structures.

Eviction Path: What Must Happen

IfCache is at capacity and a new key is inserted

→

UseIdentify LRU node (tail.prev). Remove from DLL. Remove from HashMap. Then insert new node at head.

IfExisting key is updated via put

→

UseNo eviction. Update value in place. Remove node from DLL. Insert at head (MRU).

IfCapacity is 1

→

UseEvery put of a new key evicts the current single entry. head.next == tail.prev always.

IfSame key is put twice consecutively

→

UseSecond put updates the value and promotes to MRU. No eviction. DLL and map sizes unchanged.

Generic LRUCache Implementation

The previous implementation hardcodes key and value types as int. In real-world production systems, caches hold arbitrary types — session objects, API responses, database query results. A generic version parameterizes the key and value types, making the cache reusable across the entire application.

Generifying the cache is straightforward: replace every occurrence of int key with K key, and int value with V value. The HashMap becomes Map<K, Node<K,V>>. The sentinel nodes become Node<K,V> with null keys (or use placeholder values). The factory method or constructor accepts a capacity and optionally an equality/duration strategy.

The trade-off is that the cache must now handle the additional overhead of generic type erasure in Java, but that is negligible. The real benefit is a single, type-safe cache class that can be instantiated for any key-value pair.

io/thecodeforge/cache/LRUCache.java · JAVA

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980

package io.thecodeforge.cache;

import java.util.HashMap;
import java.util.Map;

/**
 * Generic LRU Cache — type-safe, reusable for any key-value pair.
 * Same O(1) semantics as the int-based version.
 */
public class LRUCache<K, V> {\n\n    static class Node<K, V> {\n        K key;\n        V value;\n        Node<K,V> prev;\n        Node<K,V> next;\n\n        Node(K key, V value) {\n            this.key = key;\n            this.value = value;\n        }
    }

    private final int capacity;
    private final Map<K, Node<K,V>> map;
    private final Node<K,V> head;
    private final Node<K,V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node<K,V> node) {\n        node.prev.next = node.next;\n        node.next.prev = node.prev;\n    }

    private void insertFront(Node<K,V> node) {\n        node.next = head.next;\n        node.prev = head;\n        head.next.prev = node;\n        head.next = node;\n    }

    /**
     * Get value by key. Returns null if key not found.
     */
    public V get(K key) {
        Node<K,V> node = map.get(key);
        if (node == null) {
            return null;
        }
        remove(node);
        insertFront(node);
        return node.value;
    }

    /**
     * Insert or update key-value pair. Evicts LRU if over capacity.
     */
    public void put(K key, V value) {\n        Node<K,V> existing = map.get(key);\n        if (existing != null) {\n            existing.value = value;\n            remove(existing);\n            insertFront(existing);\n        } else {
            Node<K,V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            insertFront(newNode);

            if (map.size() > capacity) {
                Node<K,V> lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
        }
    }

    public boolean isConsistent() {
        int dllCount = 0;
        Node<K,V> cur = head.next;
        while (cur != tail) {
            dllCount++;
            cur = cur.next;
        }
        return map.size() == dllCount;
    }

    // Example usage:
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);
        cache.put("a", 1);
        cache.put("b", 2);
        cache.put("c", 3);
        System.out.println(cache.get("a")); // 1, promotes "a"
        cache.put("d", 4); // evicts "b"
        System.out.println(cache.get("b")); // null
    }
}

▶ Output

1
null

🔥Production Note: Null Keys

Sentinels only reference null keys internally — never added to the map.
If your K type allows null, consider using Optional<K> or a sentinel marker interface.
Alternatively, use a separate field to indicate a sentinel node.

📊 Production Insight

The generic version is what you would use in production. It eliminates code duplication and allows the same cache class to serve session caches, response caches, and database query caches. The performance overhead of generics is zero after type erasure. The only extra cost is a null-or-null check in get (returning null instead of -1).

🎯 Key Takeaway

Generifying the LRU cache makes it production-ready for any key-value type. The implementation is identical to the int-only version except the Node class and map are parameterized.

Thread-Safe LRU Cache with ReentrantReadWriteLock

In multi-threaded environments, the basic LRU cache is not safe. Concurrent get and put can corrupt the DLL (two threads modifying prev/next pointers simultaneously) or produce stale values. The simplest way to make it thread-safe is to synchronize all public methods, but that serializes all access. A better approach uses ReentrantReadWriteLock: multiple gets can proceed concurrently (read lock), but puts and puts that evict must be exclusive (write lock).

The production incident we covered earlier would have been magnified in a concurrent environment — a race condition between a get and an eviction could leave the DLL in an inconsistent state. Using locks ensures the DLL invariants are maintained atomically.

io/thecodeforge/cache/ConcurrentLRUCache.java · JAVA

package io.thecodeforge.cache;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * Thread-safe LRU Cache using ReentrantReadWriteLock.
 * Read lock for get operations (multiple readers).
 * Write lock for put operations (single writer).
 */
public class ConcurrentLRUCache<K, V> {\n\n    static class Node<K, V> {\n        K key;\n        V value;\n        Node<K,V> prev;\n        Node<K,V> next;\n\n        Node(K key, V value) {\n            this.key = key;\n            this.value = value;\n        }
    }

    private final int capacity;
    private final Map<K, Node<K,V>> map;
    private final Node<K,V> head, tail;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    public ConcurrentLRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    // --- DLL helpers (must be called with write lock held) ---
    private void remove(Node<K,V> node) {\n        node.prev.next = node.next;\n        node.next.prev = node.prev;\n    }

    private void insertFront(Node<K,V> node) {\n        node.next = head.next;\n        node.prev = head;\n        head.next.prev = node;\n        head.next = node;\n    }

    public V get(K key) {
        lock.readLock().lock();
        try {
            Node<K,V> node = map.get(key);
            if (node == null) {
                return null;
            }
            // Need to promote: demote to write lock
            lock.readLock().unlock();
            lock.writeLock().lock();
            try {
                // Double-check — node may have been evicted after read lock released
                if (map.get(key) != node) {
                    // Node was removed by another thread; treat as miss
                    return null;
                }
                remove(node);
                insertFront(node);
                return node.value;
            } finally {
                lock.writeLock().unlock();
                lock.readLock().lock(); // re-acquire read lock for consistency at exit
            }
        } finally {
            lock.readLock().unlock();
        }
    }

    public void put(K key, V value) {\n        lock.writeLock().lock();\n        try {\n            Node<K,V> existing = map.get(key);\n            if (existing != null) {\n                existing.value = value;\n                remove(existing);\n                insertFront(existing);\n            } else {
                Node<K,V> newNode = new Node<>(key, value);
                map.put(key, newNode);
                insertFront(newNode);

                if (map.size() > capacity) {
                    Node<K,V> lru = tail.prev;
                    remove(lru);
                    map.remove(lru.key);
                }
            }
        } finally {
            lock.writeLock().unlock();
        }
    }

    public int size() {
        lock.readLock().lock();
        try {
            return map.size();
        } finally {
            lock.readLock().unlock();
        }
    }

    // Example usage:
    public static void main(String[] args) throws InterruptedException {
        ConcurrentLRUCache<String, Integer> cache = new ConcurrentLRUCache<>(1000);
        // Simulate concurrent access
        Thread writer = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                cache.put("key" + i, i);
            }
        });
        Thread reader = new Thread(() -> {\n            for (int i = 0; i < 1000; i++) {
                Integer val = cache.get("key" + i);
                // May get null if evicted, that's okay
            }
        });
        writer.start();
        reader.start();
        writer.join();
        reader.join();
        System.out.println("Final size: " + cache.size());
    }
}

▶ Output

Final size: 1000

⚠ Lock Escalation in get()

Note the pattern: get() acquires the read lock first, then if a hit occurs, it releases the read lock and acquires the write lock. This is necessary because promotion modifies the DLL (write operation). After the promotion, the method re-acquires the read lock before releasing the write lock to maintain proper lock nesting — the final clean-up then releases the read lock. A simpler alternative is to always use write lock for all operations, but that reduces concurrency.

📊 Production Insight

The lock escalation pattern in get() is critical for performance. In a typical workload, reads outnumber writes 10:1. Using a read lock for the initial lookup avoids contention on the hot path. Only when a cache hit occurs and promotion is needed do we escalate to a write lock. However, lock escalation can cause deadlocks if not done carefully — always release the read lock before acquiring the write lock, and use a retry loop if the node state changes.

🎯 Key Takeaway

ReentrantReadWriteLock allows multiple concurrent reads for get() while serializing writes. The lock escalation pattern in get() is necessary because promotion is a write operation. This provides good concurrency for read-heavy workloads.

Alternative Implementation Approaches

The HashMap + Doubly Linked List combination delivers O(1) for both get and put, but it's not the only way to implement LRU. Two alternative approaches — Array-based and Heap-based — trade time complexity for simplicity or memory efficiency. Understanding these alternatives justifies why the DLL+HashMap design is the industry standard.

Array-based LRU uses an array of key-value pairs and increments a counter on each access. When a new item must be inserted, scan the array for the smallest counter (least recently used) and replace it. get() is O(n) because we scan to find the key. put() is also O(n). This is impractical for large caches but simple to implement and understand. It's sometimes used in embedded systems with tiny cache sizes (<100).

Heap-based LRU (min-heap by access timestamp) provides O(log n) for both get and put. Each node stores a key, value, and access timestamp. On get, update the timestamp and heapify. On put, insert a new node, then if over capacity, extract the min (LRU). The heap gives better performance than an array but worse than DLL+HashMap. It also requires handling timestamp increments carefully to avoid overflow.

The DLL+HashMap approach is optimal because it achieves O(1) for both operations by combining a hash map for key lookup with a linked list for order maintenance. The HashMap provides direct node access (no scanning), and the DLL provides constant-time insertion and removal at known positions.

🔥Complexity Comparison

Array: get O(n), put O(n), evict O(n). Simple but slow for large caches.
Heap: get O(log n) (if we update timestamp and heapify), put O(log n), evict O(log n). Better but not optimal.
DLL+HashMap: get O(1), put O(1), evict O(1). Optimal time complexity.
Memory: DLL+HashMap uses more memory per entry (two pointers + hash overhead) but that's acceptable for most applications.

📊 Production Insight

The heap approach is sometimes used in practice when you need additional ordering criteria beyond recency — for example, combined LRU and priority. But for pure LRU, the extra log factor adds latency at scale. In production systems like Caffeine or Guava Cache, the DLL+HashMap design (with generational improvements) is the standard.

🎯 Key Takeaway

Array and heap alternatives illustrate the trade-off space. The HashMap+DLL design achieves O(1) for all operations, which is why it is the standard LRU implementation in production systems.

LinkedHashMap Shortcut for LRU Cache

Java's LinkedHashMap can implement an LRU cache in just a few lines by setting accessOrder=true and overriding removeEldestEntry. This is often the quickest path to a working LRU cache for non-critical code. However, it hides the underlying mechanics — the same HashMap+DLL that we implemented manually.

When accessOrder=true, LinkedHashMap maintains the iteration order as the order in which entries were last accessed (not insertion order). The eldest entry (the one that would be removed) is determined by the access order, which corresponds to the least recently used. Overriding removeEldestEntry with a size check allows automatic eviction.

This approach is ideal for quick prototypes, small-scale caches, and interview warm-ups. But it has limitations: no per-entry expiration, no control over the DLL removal order, and limited configurability. For production, a purpose-built cache library (Caffeine, Guava) is better.

io/thecodeforge/cache/LinkedHashMapLRUCache.java · JAVA

12345678910111213141516171819202122232425

package io.thecodeforge.cache;

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

/**
 * LRU Cache using LinkedHashMap with access order.
 * Simple, but hides the underlying DLL mechanics.
 */
public class LinkedHashMapLRUCache<K, V> extends LinkedHashMap<K, V> {\n\n    private final int capacity;\n\n    public LinkedHashMapLRUCache(int capacity) {\n        // initialCapacity, loadFactor, accessOrder=true\n        super(capacity, 0.75f, true);\n        this.capacity = capacity;\n    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {\n        return size() > capacity;\n    }

    // get() is inherited from LinkedHashMap - returns null if not found
    // put() is inherited - automatically evicts via removeEldestEntry

    public static void main(String[] args) {
        LinkedHashMapLRUCache<String, Integer> cache = new LinkedHashMapLRUCache<>(3);
        cache.put("a", 1);
        cache.put("b", 2);
        cache.put("c", 3);
        cache.get("a"); // promotes "a" to MRU
        cache.put("d", 4); // evicts "b" (LRU)
        System.out.println(cache); // {c=3

▶ Output

{c=3

💡When to Use LinkedHashMap vs Manual Implementation

LinkedHashMap: quick to write, good for small caches, built-in access order.
Manual DLL+HashMap: full control over eviction order, easier to extend (TTL, metrics), shows deeper understanding.
For production, use a library (Caffeine/Guava) — they handle edge cases you haven't thought of.
In interviews, manual implementation is expected to demonstrate pointer manipulation.

📊 Production Insight

The LinkedHashMap shortcut is deceptively simple. In production, it has subtle issues: concurrent access is not safe by default (you must wrap or use Collections.synchronizedMap), and it does not provide metrics, eviction listeners, or variable expiration. We've seen teams use it in high-throughput systems and later hit performance cliffs because they couldn't control the underlying data structure. Use libraries like Caffeine that implement a modern variant of LRU (TinyLFU) with better scan resistance.

🎯 Key Takeaway

Java's LinkedHashMap provides a one-liner LRU cache by enabling access order and overriding removeEldestEntry. It's great for quick needs but lacks the flexibility and performance of a manual implementation or dedicated caching library.

Advantages and Disadvantages of LRU Cache

No cache eviction policy is perfect for every workload. Understanding the strengths and weaknesses of LRU helps you choose the right policy and design the right mitigations.

Advantages

Excellent temporal locality: LRU works well for workloads where recently accessed data is likely to be accessed again soon (the common case).
O(1) operations: With the HashMap+DLL design, get and put are both constant time.
Simple to implement: The algorithm is well-understood and straightforward to code.
Predictable memory usage: Fixed capacity ensures bounded memory consumption.
Good for streaming or sequential access with high locality of reference.

Disadvantages

Scan thrashing: When a full scan of items occurs (e.g., a database full-table scan), every item is accessed once, evicting all hot data. After the scan, the cache is cold. This is the Achilles' heel of LRU.
High memory overhead per entry: Each entry requires a key, value, two pointers (prev/next), plus hash map overhead. For large caches, this adds up.
Not adaptive to workload changes: LRU does not distinguish between a one-time access and a frequently accessed item — both look the same after one access.
Not suitable for all patterns: Workloads with cyclic access patterns (e.g., round-robin workloads) cause LRU to thrash.
No expiration mechanism: LRU evicts based on recency, but does not automatically expire stale data. TTL must be added separately.

Despite these disadvantages, LRU remains the most widely used cache eviction policy due to its simplicity and effectiveness for typical internet workloads.

🔥When LRU Fails: Scan Resistance

A database buffer pool using LRU during a full table scan: the scan touches every row once, evicting all frequently accessed pages.
After the scan, every subsequent query experiences cache misses, severely degrading performance.
Solution: Use LRU-K (tracks last K accesses) or ARC (Adaptive Replacement Cache) which includes a ghost-entry mechanism to detect scans.
In practice, many production caches (like Caffeine) implement TinyLFU with a sketch-based frequency filter to avoid admitting scan items.

📊 Production Insight

When deploying LRU in production, always monitor the cache hit rate and eviction rate. A sudden drop in hit rate may indicate scan thrashing. Consider adding a secondary data structure (like a bloom filter in TinyLFU) to prevent admitting one-time-use items. Also, measure per-entry memory overhead: for extremely large caches, the DLL pointers dominate memory usage, and a different data structure (like a CLOCK approximation) may be more memory-efficient.

🎯 Key Takeaway

LRU is optimal for temporal locality but vulnerable to scan thrashing. Its simplicity and O(1) performance make it the default choice for most caching scenarios.

LeetCode Problem #146 — Interview Practice Context

LeetCode Problem #146 (LRU Cache) is the canonical interview question for cache data structures. It asks you to implement an LRUCache class with get and put methods following the same contract we've built here. The official constraints (1 ≤ capacity ≤ 3000) make it suitable for any language.

If you've followed our implementation, you're already prepared. The main differences in the LeetCode version: - Returns -1 for missing keys (not null). - Typically expects int keys and int values. - No sentinel nodes required (but recommended). - Capacity is given as a constructor parameter.

The most common pitfalls: forgetting to move nodes on get, not removing from DLL on eviction, and using incorrect sentinel initialization. Our production incident story — the missing DLL removal — is exactly the bug that kills LeetCode solutions too.

After solving #146, try #460 (LFU Cache) which uses a frequency map + DLL list per frequency — a harder variant that tests the same pointer manipulation skills.

💡LeetCode Tip: Test with Capacity 1

Always test your LRU cache with capacity=1. Trace through put(1,1), put(2,2), get(1). The expected output is -1 because put(2,2) evicts the only entry (key=1). Many candidates get this wrong because they don't handle the case where head.next == tail.prev (only one node).

📊 Production Insight

LeetCode's problem is a simplified version of what you'll encounter in production. In real systems, you also need thread safety, TTL, metrics, and handling of null keys/values. But the core data structure — HashMap + DLL with sentinels — is the same. Mastering this gives you a foundation for building production caches or understanding libraries like Caffeine.

🎯 Key Takeaway

LeetCode #146 tests the exact HashMap+DLL implementation we built. Practice it to solidify the pointer manipulation, and be especially careful with the eviction order and sentinel nodes.

🗂 Cache Eviction Policies Compared

Trade-offs for different access patterns and workloads.

Policy	Eviction Rule	Best For	Weakness
LRU (Least Recently Used)	Evict the item not accessed for the longest time	Temporal locality workloads (web caches, session stores)	Thrashes on scan patterns — a full scan evicts all hot data
LFU (Least Frequently Used)	Evict the item accessed the fewest times	Frequency-based workloads (DNS caching, popular content)	Slow to adapt — a previously popular item may lingerorder).
FIFO (First In First Out)	Evict the oldest inserted item regardless of access	Simple bounded queues, streaming buffers	Ignores access patterns — a frequently accessed item is evicted if it was inserted early
ARC (Adaptive Replacement Cache)	Dynamically balances LRU and LFU based on workload	Mixed workloads with unpredictable access patterns	More complex to implement — requires two LRU lists and two ghost lists
LRU-K	Evict based on the K-th most recent access time	Database buffer pools (K=2 is common)	Higher per-item metadata overhead than plain LRU

🎯 Key Takeaways

LRU Cache provides O(1) get and put by combining a hash map (lookup) with a DLL (order maintenance).
DLL head = most recently used (MRU), tail = least recently used (LRU).
On get: move accessed node to head. On put: insert at head, evict tail if over capacity.
Sentinel head/tail nodes eliminate null checks in insert and remove operations.
Python's OrderedDict or Java's LinkedHashMap can also implement LRU in fewer lines.

⚠ Common Mistakes to Avoid

✕Forgetting to remove from the DLL during eviction

Symptom

HashMap stays at capacity but the DLL grows unboundedly, causing a memory leak —

Fix

always call remove(lru) on the DLL before map.remove(lru.key). Both structures must be updated atomically.

✕Not using sentinel nodes

Symptom

NullPointerException when the cache has 0 or 1 elements, because head.prev or tail.next is null —

Fix

initialize sentinel head and tail nodes in the constructor. They are never removed, never null.

✕Forgetting to move the node to the front on get

Symptom

get() returns the correct value but does not update recency, so frequently accessed items are evicted as if they were cold —

Fix

always call remove(node) then insertFront(node) inside get().

✕Not handling put() with an existing key correctly

Symptom

duplicate entries in the DLL for the same key, causing size mismatch between map and DLL —

Fix

if the key exists, remove the old node from the DLL, update the value, then insert at front. Do not create a new node.

✕Evicting before inserting on put

Symptom

if the new key already exists in the cache, you evict an unrelated item unnecessarily —

Fix

check if the key exists first. Only evict when inserting a NEW key that exceeds capacity.

✕No invariant check between DLL and HashMap

Symptom

silent divergence between the two structures that only manifests as a memory leak weeks later —

Fix

add an isConsistent() method that verifies DLL size equals HashMap size. Enable it in debug builds and integration tests.

Interview Questions on This Topic

QWhat two data structures power an O(1) LRU cache?
QWhy are sentinel head and tail nodes useful in the LRU cache DLL?
QHow does the LRU cache handle a put operation when the cache is at capacity?
QWalk me through what happens when you call get() on a key that exists — what exact pointer operations occur?
QHow would you implement a thread-safe LRU cache? What locking strategy would you use?
QHow does LRU differ from LFU, and when would you choose one over the other?
QWhat happens if the cache capacity is 1? Trace through a sequence of put(1,A), put(2,B), get(1).
QHow would you extend this to support TTL (time-to-live) expiration in addition to LRU eviction?

Frequently Asked Questions

Why use sentinel head and tail nodes?

Sentinel nodes eliminate null checks in insert and remove operations. Without them, every insert/remove must check 'is this node the head?' and 'is this node the tail?' With sentinels, head.next is always the MRU node and tail.prev is always the LRU node — the code is cleaner and less error-prone.

What is the difference between LRU, LFU, and FIFO caches?

LRU (Least Recently Used) evicts the item not accessed for the longest time. LFU (Least Frequently Used) evicts the item accessed the fewest times — useful when access frequency is a better predictor than recency. FIFO (First In First Out) evicts the oldest inserted item regardless of access pattern. LRU is the most common in practice because it adapts well to temporal locality.

Can Python's OrderedDict implement an LRU cache?

Yes. Python's collections.OrderedDict maintains insertion order and supports move_to_end(key) in O(1). Use it as: get moves key to end (MRU), put moves to end and pops the first item (LRU) if over capacity. Python's functools.lru_cache decorator implements this pattern exactly.

How is Java's LinkedHashMap related to LRU cache?

Java's LinkedHashMap can implement LRU by setting accessOrder=true in the constructor and overriding removeEldestEntry(). However, this hides the pointer manipulation internally. Implementing from scratch with HashMap + custom DLL demonstrates understanding of the underlying mechanics — which is what interviewers test.

How do you make an LRU cache thread-safe?

Wrap all get and put operations in a synchronized block or use a ReentrantReadWriteLock — reads (get) acquire the read lock, writes (put) acquire the write lock. For high contention, consider a sharded LRU cache where keys are partitioned across multiple independent LRU caches, each with its own lock.

What happens when cache capacity is 1?

Every put of a new key evicts the current entry. The DLL always has exactly one node between head and tail. head.next == tail.prev. This is a valid edge case that must be tested explicitly.

🔥

Naren Founder & Author

Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.

About Naren Get in touch

Forged with 🔥 at TheCodeForge.io — Where Developers Are Forged