Simple LRU Cache in Java: Solution, Explanation & Practice

Problem summary

Implement a cache that removes least recently used item when capacity is exceeded.

Starter code

import java.util.*;

// Use LinkedHashMap with access order

public class Main {
    public static void main(String[] args) {
        // Cache with capacity 3
        // Add items and show eviction
    }
}

Expected output and test cases

• A evicted when D added

  Cache: {B=2, C=3, D=4}

• B evicted, A accessed

  Cache: {A=1, C=3, D=4}

• Single item cache

  Cache: {X=1}

Hints

1. LinkedHashMap with accessOrder=true
2. Override removeEldestEntry()
3. Return true when size > capacity

Validated solution

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

class LruCache extends LinkedHashMap<String, Integer> {
    private final int capacity;
    LruCache(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) { return size() > capacity; }
}
public class Main {
    public static void main(String[] args) {
        LruCache cache = new LruCache(3);
        cache.put("A", 1); cache.put("B", 2); cache.put("C", 3); cache.get("B"); cache.put("D", 4);
        System.out.println("Cache: " + cache);
    }
}

How to approach the problem

LinkedHashMap in access-order mode moves a key to the end whenever it is read. Overriding removeEldestEntry then evicts the least recently used key immediately after an insert exceeds capacity.

Approach

1. Enable access-order in the LinkedHashMap constructor.
2. Store the capacity.
3. Evict only when size exceeds capacity.

Time and space complexity

Time: O(1) expected per get or put. Space: O(capacity).

Edge cases to test

• A get changes recency even though it does not change a value.
• Capacity should be positive.

Common mistakes

• Using insertion order, which implements FIFO rather than LRU.
• Evicting when size is equal to capacity and losing one entry too early.

Follow-up challenge

Implement the same policy with HashMap plus a custom doubly linked list.

Related Collections exercises

• Practice Sort Map by Value in Java
• Practice Group By Property in Java
• Practice Priority Queue with Custom Order in Java

Practice all Collections exercises · Run this idea in the Java compiler