LinkedHashMap Internals & LRU Cache

LeetCode #146 — LRU Cache is the single most asked LinkedList/HashMap question at FAANG companies. Google, Meta, Amazon, and Microsoft have all asked it in phone screens and on-sites. Mastering this one problem demonstrates HashMap internals, doubly-linked list manipulation, and O(1) design thinking.

LinkedHashMap Internals

What Is LinkedHashMap?

LinkedHashMap<K,V> extends HashMap and adds a doubly-linked list that threads through all entries. This overlay preserves either insertion order (default) or access order (LRU mode).

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {

    // Each entry extends HashMap.Node and adds before/after pointers
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;  // doubly-linked list pointers
    }

    transient LinkedHashMap.Entry<K,V> head; // eldest (first inserted)
    transient LinkedHashMap.Entry<K,V> tail; // newest (last inserted/accessed)

    final boolean accessOrder; // false = insertion order, true = access order
}

HashMap Buckets + Linked List Threading

The key insight: entries live in two structures simultaneously — the HashMap bucket array for O(1) lookup, and a doubly-linked list for ordering.

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart TD
    subgraph BUCKETS["HashMap Bucket Array"]
        direction TB
        B0["[0] null"]
        B1["[1] Entry:A"]
        B2["[2] Entry:C"]
        B3["[3] null"]
        B4["[4] Entry:B"]
        B5["[5] Entry:D"]
    end

    subgraph DLL["Doubly-Linked List (insertion order)"]
        direction LR
        HEAD["head"] --> EA["A"]
        EA --> EB["B"]
        EB --> EC["C"]
        EC --> ED["D"]
        ED --> TAIL["tail"]
    end

    B1 -.-> EA
    B4 -.-> EB
    B2 -.-> EC
    B5 -.-> ED

    style B0 fill:#EFF6FF,stroke:#93C5FD,color:#1E40AF
    style B1 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style B2 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style B3 fill:#EFF6FF,stroke:#93C5FD,color:#1E40AF
    style B4 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style B5 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style HEAD fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style EA fill:#FEF3C7,stroke:#FCD34D,color:#92400E
    style EB fill:#FEF3C7,stroke:#FCD34D,color:#92400E
    style EC fill:#FEF3C7,stroke:#FCD34D,color:#92400E
    style ED fill:#FEF3C7,stroke:#FCD34D,color:#92400E
    style TAIL fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF

Each Entry object has:

• hash, key, value, next — from HashMap.Node (bucket chain)
• before, after — doubly-linked list pointers (ordering chain)

Insertion-Order vs Access-Order

Insertion Order (Default)

Map<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

map.keySet(); // [C, A, B] — preserves insertion order

map.get("C"); // does NOT change order
map.keySet(); // [C, A, B] — still the same

Access Order (LRU Mode)

// Third constructor parameter: accessOrder = true
Map<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

map.keySet(); // [C, A, B]

map.get("C"); // moves C to tail (most recently used)
map.keySet(); // [A, B, C] — C moved to end!

map.get("A"); // moves A to tail
map.keySet(); // [B, C, A]

Access-Order Behavior Diagram

When get("B") is called in access-order mode, entry B is unlinked from its current position and moved to the tail:

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph BEFORE["Before get(B)"]
        direction LR
        H1["head"] --> A1["A"]
        A1 --> B1["B"]
        B1 --> C1["C"]
        C1 --> D1["D"]
        D1 --> T1["tail"]
    end

    subgraph AFTER["After get(B)"]
        direction LR
        H2["head"] --> A2["A"]
        A2 --> C2["C"]
        C2 --> D2["D"]
        D2 --> B2["B"]
        B2 --> T2["tail"]
    end

    BEFORE --> AFTER

    style H1 fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style T1 fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style A1 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style B1 fill:#FEE2E2,stroke:#FCA5A5,color:#991B1B
    style C1 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style D1 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style H2 fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style T2 fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style A2 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style C2 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style D2 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style B2 fill:#FEF3C7,stroke:#FCD34D,color:#92400E

Internal method afterNodeAccess(Node e):

1. Unlink e from its current position (e.before.after = e.after)
2. Link e after current tail
3. Set tail = e

removeEldestEntry() — The LRU Hook

LinkedHashMap calls removeEldestEntry() after every put()/putAll(). By default it returns false. Override it to auto-evict:

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

How it works internally:

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart TD
    PUT["put(key, value)"] --> INSERT["Insert into HashMap"]
    INSERT --> LINK["Link at tail of DLL"]
    LINK --> CHECK{"removeEldestEntry(head)?"}
    CHECK -->|"true"| EVICT["Remove head entry<br/>(eldest)"]
    CHECK -->|"false"| DONE["Done"]

    style PUT fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style INSERT fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style LINK fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style CHECK fill:#FEF3C7,stroke:#FCD34D,color:#92400E
    style EVICT fill:#FEE2E2,stroke:#FCA5A5,color:#991B1B
    style DONE fill:#ECFDF5,stroke:#6EE7B7,color:#065F46

LRU Cache with LinkedHashMap (Production Approach)

Basic LRU Cache

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

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

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

Usage:

LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
// Cache: {1=A, 2=B, 3=C}

cache.get(1);       // Access "A" — moves to tail
// Cache: {2=B, 3=C, 1=A}

cache.put(4, "D");  // Evicts eldest (key=2)
// Cache: {3=C, 1=A, 4=D}

Thread-Safe LRU Cache

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

public class ConcurrentLRUCache<K, V> {
    private final Map<K, V> cache;

    public ConcurrentLRUCache(int capacity) {
        this.cache = Collections.synchronizedMap(
            new LinkedHashMap<K, V>(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > capacity;
                }
            }
        );
    }

    public V get(K key) {
        return cache.get(key);
    }

    public void put(K key, V value) {
        cache.put(key, value);
    }

    public void remove(K key) {
        cache.remove(key);
    }

    public int size() {
        return cache.size();
    }
}

LRU Cache from Scratch (Interview Approach)

This is what interviewers expect you to code in 20-25 minutes for LeetCode #146:

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

class LRUCache {

    // Doubly-linked list node
    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;
    private final Node head; // dummy head — eldest side
    private final Node tail; // dummy tail — newest side

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

        // Sentinel nodes to avoid null checks
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

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

        // Move to most-recently-used position (before tail)
        moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);

        if (node != null) {
            // Update existing
            node.value = value;
            moveToTail(node);
        } else {
            // Insert new
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addBeforeTail(newNode);

            // Evict if over capacity
            if (map.size() > capacity) {
                Node eldest = head.next;
                removeNode(eldest);
                map.remove(eldest.key);
            }
        }
    }

    private void moveToTail(Node node) {
        removeNode(node);
        addBeforeTail(node);
    }

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

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

Why sentinel (dummy) nodes?

Without them, you need null-checks everywhere when removing the first or last real node. Sentinels eliminate edge cases — head.next is always the eldest real entry, tail.prev is always the newest.

Data Structure Diagram (Interview Version)

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph HASHMAP["HashMap<Key, Node>"]
        direction TB
        K1["key=1 -> Node(1,A)"]
        K2["key=2 -> Node(2,B)"]
        K3["key=3 -> Node(3,C)"]
    end

    subgraph DLL["Doubly-Linked List"]
        direction LR
        DH["dummy head"] --> N1["Node(1,A)<br/>eldest"]
        N1 --> N2["Node(2,B)"]
        N2 --> N3["Node(3,C)<br/>newest"]
        N3 --> DT["dummy tail"]
    end

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

    style DH fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style DT fill:#DBEAFE,stroke:#93C5FD,color:#1E40AF
    style N1 fill:#FEE2E2,stroke:#FCA5A5,color:#991B1B
    style N2 fill:#FEF3C7,stroke:#FCD34D,color:#92400E
    style N3 fill:#D1FAE5,stroke:#6EE7B7,color:#065F46
    style K1 fill:#EFF6FF,stroke:#93C5FD,color:#1E40AF
    style K2 fill:#EFF6FF,stroke:#93C5FD,color:#1E40AF
    style K3 fill:#EFF6FF,stroke:#93C5FD,color:#1E40AF

Eviction: Remove head.next (eldest) from both the linked list and the HashMap.
Access: Unlink node, re-link before tail (most recently used).

Comparison: LinkedHashMap vs Guava Cache vs Caffeine

Time & Space Complexity

Common Pitfalls

Quick Recall

Interview Answer Template

Bonus: LRU with ReentrantReadWriteLock (High-Concurrency)

import java.util.*;
import java.util.concurrent.locks.*;

public class ConcurrentLRU<K, V> {
    private final int capacity;
    private final Map<K, V> cache;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();

    public ConcurrentLRU(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }

    public V get(K key) {
        writeLock.lock();  // write lock because access-order modifies structure
        try {
            return cache.get(key);
        } finally {
            writeLock.unlock();
        }
    }

    public void put(K key, V value) {
        writeLock.lock();
        try {
            cache.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }
}