Implement an LRU cache from scratch without LinkedHashMap.

Combine a HashMap<K, Node> for O(1) lookup with a custom doubly-linked list for O(1) reorder and eviction. The hash map points to nodes; the list maintains recency order via dummy head/tail sentinels that simplify edge cases.

The full class

public final class LruCache<K, V> {

    private static final class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> index;
    private final Node<K, V> head; // sentinel before MRU
    private final Node<K, V> tail; // sentinel after LRU

    public LruCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
        this.index = new HashMap<>(capacity * 4 / 3 + 1);
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = index.get(key);
        if (node == null) return null;
        moveToFront(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> existing = index.get(key);
        if (existing != null) {
            existing.value = value;
            moveToFront(existing);
            return;
        }
        Node<K, V> node = new Node<>(key, value);
        index.put(key, node);
        addToFront(node);
        if (index.size() > capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            index.remove(lru.key);
        }
    }

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

    // --- list operations: all O(1) ---

    private void addToFront(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void unlink(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = node.next = null;
    }

    private void moveToFront(Node<K, V> node) {
        unlink(node);
        addToFront(node);
    }
}

Why sentinel nodes

The dummy head and tail mean every real node always has non-null prev and next. No null checks in unlink, no special "is this the only node" case in addToFront. The cost is two extra Node allocations at construction time — well worth it for cleaner code and zero branching in the hot path.

index:  k1 -> nodeA
      k2 -> nodeB
      k3 -> nodeC

list:  head <-> nodeC <-> nodeA <-> nodeB <-> tail
              ^                       ^
              MRU                     LRU

Complexity

Variations interviewers ask about

• Thread safety: wrap with ReentrantLock or a synchronized block. (Lock-free LRU is hard — for production, use Caffeine.)
• TTL eviction: store a timestamp on each node, lazily check on get, or use a DelayQueue.
• LFU instead of LRU: track frequency counts, maintain a frequency-to-list-of-keys structure. Different problem; not a tweak.