How can we implement an LRU (Least Recently Used) cache using a LinkedList?

An LRU (Least Recently Used) cache stores a limited number of items and automatically removes the item that has not been accessed for the longest time when the cache reaches its capacity. Using a LinkedList, recently accessed elements are moved to the front, while the least recently used element remains at the end and can be removed when space is needed.

Key Points: • The most recently used item is always placed at the beginning of the LinkedList, while the least recently used item stays at the end. • A HashMap is typically used alongside the LinkedList to provide O(1) lookups, since searching a LinkedList alone is O(n). • When an item is accessed, it is removed from its current position and moved to the front of the list to mark it as recently used.

Example: Consider a cache with a capacity of 3 storing pages A, B, and C. If page A is accessed, it becomes the most recently used item. When page D is added and the cache is full, page B (the least recently used item) is removed automatically.

Code Example:

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

class LRUCache<K, V> {

    private final int capacity;

    private final LinkedList<K> list = new LinkedList<>();
    private final Map<K, V> cache = new HashMap<>();

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

    public void put(K key, V value) {

        if (cache.containsKey(key)) {
            list.remove(key);
        } else if (cache.size() >= capacity) {

            K lruKey = list.removeLast();
            cache.remove(lruKey);
        }

        list.addFirst(key);
        cache.put(key, value);
    }

    public V get(K key) {

        if (!cache.containsKey(key)) {
            return null;
        }

        list.remove(key);
        list.addFirst(key);

        return cache.get(key);
    }
}

Interview Tip: A concise interview answer is: An LRU cache using a LinkedList keeps recently used items at the front and least recently used items at the end. On every access, the item is moved to the front, and when the cache reaches capacity, the last element is removed. In practice, a HashMap is used with the LinkedList to achieve efficient lookups and updates.