What collection should be used for an LRU cache that removes the oldest element on overflow?

To implement an LRU cache in Java, the LinkedHashMap class is often used with an overridden removeEldestEntry method. This class maintains the insertion or access order of elements, making it easy to remove the oldest (least recently used) item when the cache is full.

Example:

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) {
        super(capacity, 0.75f, true); // true for access order
        this.capacity = capacity;
    }

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

Here, LinkedHashMap with the accessOrder=true parameter maintains access order, and the removeEldestEntry method automatically removes the oldest element when the cache exceeds its size.