LRU Cache Eviction — Missing DLL Removal Causes 4GB Leak

LRU (Least Recently Used) eviction is the industry-standard cache replacement policy. It works because most workloads exhibit temporal locality — data accessed recently is 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.

How LRU Cache Works — Step by Step

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.

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.

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.

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) {
            this.key = key;
            this.value = value;
        }
    }

    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());
    }
}

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.

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> {

    static class Node<K, V> {
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    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) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

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

    /**
     * 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) {
        Node<K,V> existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            remove(existing);
            insertFront(existing);
        } 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
    }
}

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.

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> {

    static class Node<K, V> {
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    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) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

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

    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) {
        lock.writeLock().lock();
        try {
            Node<K,V> existing = map.get(key);
            if (existing != null) {
                existing.value = value;
                remove(existing);
                insertFront(existing);
            } 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(() -> {
            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());
    }
}

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.

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.

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> {

    private final int capacity;

    public LinkedHashMapLRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder=true
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

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

    // 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, a=1, d=4}  order reflects access order
    }
}

Multi-Language Implementations: Python OrderedDict and C++ list+map

LRU cache is a language-agnostic data structure. While we've focused on Java, two other common production implementations use Python's collections.OrderedDict and C++'s std::list + std::unordered_map. Each language brings its own idioms and performance characteristics.

Python - collections.OrderedDict maintains insertion order and provides move_to_end(key) in O(1). - The built-in functools.lru_cache decorator uses OrderedDict internally and is the simplest way to add caching to a Python function. - The manual Python implementation mirrors the Java version: a dict for lookup and a doubly linked list (via custom Node class) for order. But the OrderedDict shortcut is idiomatic and often preferred.

C++ - std::unordered_map for O(1) average key lookup. - std::list for the DLL providing splice() operations to move nodes in O(1). - A list iterator stored in the map value gives direct access to the list node. - No sentinel nodes needed if using list's built-in end() as a sentinel-like boundary, but manual sentinels are still possible.

Both languages follow the same fundamental strategy: associative container for key lookup + ordered container for eviction order.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(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)  # pop first (LRU)

# Example usage
cache = LRUCache(3)
cache.put(1, 1)
cache.put(2, 2)
cache.put(3, 3)
print(cache.get(1))  # 1
cache.put(4, 4)       # evicts 2
print(cache.get(2))  # -1
print(cache.get(3))  # 3

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.

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

Real-World Applications of LRU Cache

LRU eviction is ubiquitous in computing — any system with a fixed-size cache and temporal locality benefits from it. Here are the most common production deployments:

1. CPU Caches (L1/L2/L3) — Modern CPUs use LRU-like policies to decide which cache line to evict when filling a new line from main memory. L1 caches often use pseudo-LRU to save on hardware cost.
2. Web Browser Cache — Browsers store recently visited pages, images, and scripts in a fixed-size disk cache. When the cache is full, the browser evicts the least recently used resource.
3. CDN Edge Nodes — Content Delivery Networks like Akamai, Cloudflare, and Fastly cache static content at edge servers. LRU ensures popular content stays cached while stale items are evicted.
4. Database Buffer Pool — Database systems like MySQL (InnoDB) and PostgreSQL use a buffer pool to cache pages from disk. InnoDB uses a variant of LRU with a midpoint insertion strategy to protect frequently accessed pages.
5. Redis — Redis uses approximate LRU for key eviction when memory is full (maxmemory-policy allkeys-lru). It samples a subset of keys and evicts the oldest among them.
6. DNS Resolver Caches — DNS servers cache resolved domain names with TTL. When the cache reaches its limit, LRU eviction is used to make room for new entries.
7. Operating System Page Cache — The Linux kernel uses a form of LRU (CLOCK algorithm) to manage the page cache — evicting pages that haven't been accessed recently.

These applications demonstrate that LRU is not just a data structure exercise; it is the backbone of performance in systems handling billions of requests per day.

Time and Space Complexity of LRU Cache

The HashMap + Doubly Linked List design achieves O(1) for all core operations. Below is the formal complexity summary.

Key insight: All operations are amortized O(1) because HashMap operations are O(1) on average (assuming good hash distribution). The DLL operations are strictly O(1). The worst-case of HashMap is O(n) for a single put, but with a proper hash function and load factor, the amortized average is O(1).

Memory overhead: For production systems with millions of entries, the per-entry overhead of the DLL (two pointers) plus HashMap (entry object with key, value, hash, next pointer) can be 40-72 bytes per entry in Java. This is the price of O(1) eviction. If memory is constrained, consider using a CLOCK algorithm (which uses a single reference bit per entry) at the cost of approximate LRU.

LRU vs Other Eviction Policies — Comparison

Choosing the right eviction policy depends on workload characteristics. Below is a comparison of the four most common policies: LRU, LFU (Least Frequently Used), FIFO (First In First Out), and ARC (Adaptive Replacement Cache).

Common Implementation Mistakes

Even experienced developers make these mistakes when implementing LRU caches. Recognise them, and you'll avoid production incidents.

Mistake 1: Forgetting to remove from DLL during eviction This is the most common bug. The eviction path removes a node from the HashMap but omits the DLL removal. The node remains reachable through the DLL, causing a memory leak. Symptom: heap grows unboundedly. Fix: always remove from DLL first, then from the map.

Mistake 2: Not moving existing nodes to head on get If get() doesn't promote the accessed node to MRU, recently used items can be evicted prematurely. Symptom: hit rate drops after deployment. Fix: call remove() then insertFront() on every get hit.

Mistake 3: Forgetting to handle duplicate keys on put When the same key is put again, the old node must be removed from the DLL before inserting the new one. Otherwise, duplicate nodes exist in the DLL for the same key. Symptom: inconsistent state, NPE. Fix: in the existing key branch, remove the old node before updating.

Mistake 4: Not using sentinel nodes Without sentinel head/tail, first insert and last remove require null checks. Missing these checks leads to NPE on edge cases. Symptom: crashes on first put or last eviction. Fix: always use sentinel nodes.

Mistake 5: Ignoring thread safety Using the basic cache in a multi-threaded context corrupts the DLL. Symptom: random NPE, infinite loops. Fix: add locks (ReentrantReadWriteLock) or use a concurrent library.

Interview Questions

LRU cache is a classic interview topic. Expect to implement it from scratch, then handle follow-ups about concurrency, generics, and memory trade-offs.

Q1: Implement an LRU cache with O(1) get and put. This tests your understanding of HashMap + Doubly Linked List. Use sentinel nodes. Show the eviction path clearly. Expect to write working code in 15-20 minutes.

Q2: Make your LRU cache thread-safe. Discuss lock granularity. ReentrantReadWriteLock is the go-to. Explain why promotion forces a lock escalation pattern. Mention CAS-based lock-free approaches for very high throughput.

Q3: How would you add TTL expiration to an LRU cache? Add a timestamp to each node. On get, check if expired; if so, evict and return miss. On put, check and evict expired entries. An alternative is a background thread that sweeps expired entries periodically.

Q4: What happens if the cache is accessed concurrently without locks? Describe corruption: two threads modifying prev/next at the same time can break the list into a cycle or lose nodes. Show an example: thread A reads node N, thread B evicts N, then A promotes N — now N is in the list but also marked as evicted.

Q5: Compare LRU with LFU and ARC. LRU is simple but vulnerable to scans. LFU resists scans but uses more memory. ARC adapts between them with ghost entries. Choose based on workload: LRU for temporal locality, LFU for stable popularity, ARC for mixed.

Problem Statement — What You're Actually Building

Stop thinking about this as a 'data structure' exercise. It's a resource management problem. You have finite memory, and you need to decide what to throw away when something new arrives. The LRU Cache is just one strategy: evict the item that's been untouched the longest.

The formal requirements are dead simple — but the constraints are where the trap lives. You need a get(key) that returns the value or -1, and a put(key, value) that inserts or updates. Both must run in O(1) average time. If the cache hits capacity before a put, you evict the least recently used entry before inserting.

Most developers nail the logic in 40 lines of hash map and linked list. But they choke when you ask: 'What happens under concurrent access?' or 'How do you prevent memory leaks when keys are abandoned?' That's the difference between a pass and a promotion.

// io.thecodeforge — dsa tutorial

// The spec in code form — nothing more
public class LRUCache {
    public LRUCache(int capacity) {
        // capacity > 0, or throw
    }
    
    public int get(int key) {
        // O(1) — return value, or -1 if missing
    }
    
    public void put(int key, int value) {
        // O(1) — upsert, evict LRU if full
    }
}

Efficient Solution — Doubly Linked List + Hash Map, No Surprises

You need O(1) get and put. That means instant lookup (hash map) and instant removal from the 'recently used' order (linked list). A singly linked list won't cut it — removing the tail requires O(n) traversal. That's why we use a doubly linked list with a dummy head and tail. Dummy nodes eliminate null checks on boundary removals. Senior move: they also catch logic bugs early because you never dereference a null next or prev on the edges.

The hash map stores the key and a reference to the linked list node. When you get a key, you move that node to the head (most recently used). When you put a key, you either update the existing node and move it to the head, or create a new node at the head. If capacity is exceeded, you remove the tail's previous node (the LRU item) and delete it from the hash map.

Here's the implementation that has survived three production rewrites at my current company. It's not the shortest. It's the one that doesn't crash at 3 AM under load.

// io.thecodeforge — dsa tutorial

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

public class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0); // dummy
    private final Node tail = new Node(0, 0); // dummy

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        insertAtHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            insertAtHead(node);
            return;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            map.remove(lru.key);
            remove(lru);
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        insertAtHead(newNode);
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertAtHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

Complexity Analysis — What the Interviewers Really Want to Hear

Time complexity is O(1) for both get and put — amortized constant for put if you consider hash map resizing. Space complexity is O(capacity) for the hash map and linked list combined. That's the easy part.

The harder question: 'Can you make the space complexity O(capacity) without the linked list overhead?' The answer is no, because you need order tracking. The linked list doubles the memory per entry — one Node object with two references. In Java, that's roughly 40 bytes per entry plus the hash map overhead. For a cache of 10,000 entries, expect around 1.2 MB. That's fine for most systems, but if you're caching on embedded devices or real-time trading systems, you'll want to explore alternatives like an array-based circular buffer with a monotonically increasing timestamp (O(log n) eviction, but no linked list overhead).

The real production concern isn't big-O. It's garbage collection churn. Every put can create a new Node. If you're doing millions of puts per second, you'll flood the young generation. That's why production caches like Caffeine use Segmented Least Recently Used (SLRU) with slabs, not a single list. But for a DSA interview, don't even breathe that — just say O(1) and move on.

// io.thecodeforge — dsa tutorial

// Space breakdown per entry:
// Node object: 16 bytes (header) + 4 (int key) + 4 (int value) + 8 (prev ref) + 8 (next ref) = ~40 bytes
// HashMap entry: another 32–48 bytes depending on implementation
// Total: ~80 bytes per cached item at minimum
public class SpaceNote {
    // For 10,000 entries: ~800 KB to 1.2 MB
}

FIFO Eviction: Why Simple Gets Smoked by Real Workloads

First-In-First-Out sounds innocent enough: evict the oldest entry regardless of how hot it is. That's exactly why it fails in production. FIFO cannot distinguish between a one-time request that happened to arrive early and a critical configuration key accessed every millisecond. Once an entry is buried under newer items, it gets evicted even if it's the most valuable piece of data in the cache.

In practice, FIFO exhibits terrible hit rates under temporal locality — the exact pattern most real systems exhibit. LRU exploits the fact that recently accessed data is likely to be accessed again. FIFO ignores that completely. A batch job that scans a million keys once will poison FIFO's entire cache, while LRU keeps the frequently accessed working set warm.

Don't reach for FIFO unless you're logging or tracing where eviction order truly doesn't matter. For caching, FIFO is the junior-dev default. You know better.

// io.thecodeforge — dsa tutorial

import java.util.*;

// Simple FIFO eviction using a queue + map — don't use this
class FifoCache<K, V> {
    private final int capacity;
    private final Queue<K> queue = new LinkedList<>();
    private final Map<K, V> map = new HashMap<>();

    public FifoCache(int capacity) { this.capacity = capacity; }

    public V get(K key) { return map.get(key); } // Never updates order!

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            return;
        }
        if (map.size() == capacity) {
            K oldest = queue.poll();
            map.remove(oldest);
        }
        queue.offer(key);
        map.put(key, value);
    }

    public static void main(String[] args) {
        FifoCache<String, String> cache = new FifoCache<>(3);
        cache.put("A", "1");
        cache.put("B", "2");
        cache.put("C", "3");
        cache.get("A"); // Access A — doesn't update order
        cache.put("D", "4"); // Evicts A, even though A was just accessed!
        System.out.println(cache.get("A")); // null → A is gone
    }
}

Hash Map + Array: The Academic Toy You Shouldn't Ship

You can implement an LRU cache using an array of cache entries and a hash map that stores each key's index. On every access, you update the index in the map and swap entries around in the array to maintain recency order. It works in theory. In production, it’s a disaster.

The core problem is that array-based implementations require O(n) shifts or O(n) compaction when the cache fills up and you evict the least recently used entry. Even O(log n) with a heap is worse than the O(1) eviction from a doubly linked list. More importantly, array implementations make the code brittle: off-by-one errors, capacity resizing that evicts data silently, and index invalidation become your daily headache.

Senior engineers use a doubly linked list + hash map for a reason. It’s not elegant — it’s practical. The list gives you O(1) removals from any position (as long as you hold the node reference), and the map gives you O(1) lookups. Trying to optimize array memory locality is a premature optimization that introduces complexity and bugs. Save your weekend. Use the list.

// io.thecodeforge — dsa tutorial

import java.util.*;

// DON'T DO THIS. Array-based LRU is a nightmare.
class ArrayLru<K, V> {
    private final int capacity;
    private int size = 0;
    private final Entry<K, V>[] entries;
    private final Map<K, Integer> indexMap = new HashMap<>();

    static class Entry<K, V> { K key; V value; long lastAccess; }

    @SuppressWarnings("unchecked")
    ArrayLru(int capacity) {
        this.capacity = capacity;
        this.entries = new Entry[capacity];
    }

    public V get(K key) {
        Integer idx = indexMap.get(key);
        if (idx == null) return null;
        entries[idx].lastAccess = System.nanoTime();
        return entries[idx].value;
    }

    public void put(K key, V value) {
        Integer existing = indexMap.get(key);
        if (existing != null) {
            entries[existing].value = value;
            entries[existing].lastAccess = System.nanoTime();
            return;
        }
        if (size == capacity) evictOldest();
        Entry<K, V> e = new Entry<>();
        e.key = key; e.value = value; e.lastAccess = System.nanoTime();
        entries[size] = e;
        indexMap.put(key, size);
        size++;
    }

    private void evictOldest() {
        int oldestIdx = 0;
        for (int i = 1; i < size; i++)
            if (entries[i].lastAccess < entries[oldestIdx].lastAccess)
                oldestIdx = i;
        indexMap.remove(entries[oldestIdx].key);
        entries[oldestIdx] = entries[size - 1]; // Compaction! O(n) per evict
        indexMap.put(entries[oldestIdx].key, oldestIdx);
        size--;
    }
}