LinkedHashMap First

What you should do next

Before you hand-write sixty lines of pointer management, say the Java answer out loud. LinkedHashMap with access order is the idiomatic single-threaded LRU. Show you know the library first; drop to manual doubly linked list only when the interviewer asks for custom eviction or finer locking.

What is LinkedHashMap

LinkedHashMap is a HashMap that additionally maintains a doubly-linked list through all its entries. It supports two ordering modes set at construction time:

• Insertion order (default) — entries are iterated in the order they were inserted.
• Access order (accessOrder = true) — every get and put moves the accessed entry to the tail of the internal list. This is exactly LRU order.

Java already ships the data structure you need. There is no reason to build a doubly-linked list manually when answering “implement LRU” — at least not until the interviewer asks you to.

Single-threaded LRU in five lines

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    LRUCache(int capacity) {
        super(capacity, 0.75f, true);   // true = access order
        this.capacity = capacity;
    }

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

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }
}

removeEldestEntry is called automatically by LinkedHashMap after every put. When it returns true, the eldest (LRU) entry is removed. No pointer management, no Node class, no eviction logic.

Making it thread-safe

Option 1 — Collections.synchronizedMap

Map<Integer, Integer> lru = Collections.synchronizedMap(
    new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
            return size() > capacity;
        }
    }
);

Collections.synchronizedMap wraps every method with synchronized(mutex). Correct for individual get and put calls.

Critical limitation: iteration requires external synchronization. If any code iterates the map (even implicitly, e.g. toString(), entrySet()) without holding the mutex, a ConcurrentModificationException or worse can occur:

synchronized (lru) {          // must hold mutex during full iteration
    for (var entry : lru.entrySet()) { ... }
}

Option 2 — Synchronized subclass (cleaner)

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

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

    @Override
    public synchronized Integer get(Object key) {
        return super.getOrDefault(key, -1);
    }

    @Override
    public synchronized Integer put(Integer key, Integer value) {
        return super.put(key, value);
    }
}

Explicit synchronized on the methods you control. Cleaner than wrapping because the synchronization is visible at the call site.

Why Collections.synchronizedMap is not truly safe for LRU

LinkedHashMap with access order calls afterNodeAccess inside get(), which rewires the linked list. Collections.synchronizedMap wraps the get() call with synchronized, so the rewire is protected. This is safe.

However, removeEldestEntry is called from inside put(), which is also synchronized. The eviction happens atomically with the insert. This is safe too.

The real danger is compound operations outside the map wrapper:

// NOT safe — two operations, not one atomic action
if (lru.get(key) == null) {        // step 1: read
    lru.put(key, computeValue());  // step 2: write — another thread may have inserted between steps
}

For compute-if-absent patterns, use Map.computeIfAbsent which is a single atomic operation on ConcurrentHashMap — but LinkedHashMap does not support ConcurrentHashMap.

LinkedHashMap vs manual DLL: when to use which

Interview strategy: always mention LinkedHashMap first. It shows awareness of the standard library. Then say “if we need finer concurrency control or custom eviction metadata, I’d implement the doubly-linked list manually.” Interviewers expect both answers.