LRU Cache Implementation Using a Doubly Linked List and HashMap

package io.thecodeforge.cache;

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

/**
 * LRU Cache using HashMap + Doubly Linked List.
 * O(1) get and put. Sentinel nodes eliminate null-check edge cases.
 */
public class LRUCache {

    // --- Internal node for the doubly linked list ---
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;

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

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head; // sentinel — head.next is MRU
    private final Node tail; // sentinel — tail.prev is LRU

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();

        // Sentinel nodes: never null, always present
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    // --- Remove a node from the DLL (O(1)) ---
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // --- Insert a node at the front (MRU position) (O(1)) ---
    private void insertFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * Get value by key. Moves accessed node to MRU position.
     * Returns -1 if key not found.
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);          // unlink from current position
        insertFront(node);     // promote to MRU
        return node.value;
    }

    /**
     * Insert or update key-value pair.
     * If cache is full, evicts the LRU item first.
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // Key exists: update value and promote to MRU
            Node existing = map.get(key);
            existing.value = value;
            remove(existing);
            insertFront(existing);
        } else {
            // New key: create node and insert at MRU
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            insertFront(newNode);

            // Evict if over capacity
            if (map.size() > capacity) {
                Node lru = tail.prev; // least recently used
                remove(lru);          // remove from DLL FIRST
                map.remove(lru.key);  // then remove from map
            }
        }
    }

    // --- Debug: verify DLL and map are in sync ---
    public int dllSize() {
        int count = 0;
        Node current = head.next;
        while (current != tail) {
            count++;
            current = current.next;
        }
        return count;
    }

    public boolean isConsistent() {
        return map.size() == dllSize();
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);

        cache.put(1, 100);
        cache.put(2, 200);
        cache.put(3, 300);
        System.out.println("After 3 puts: " + cache.map.keySet());
        System.out.println("DLL size: " + cache.dllSize() + ", Map size: " + cache.map.size());
        System.out.println("Consistent: " + cache.isConsistent());

        System.out.println("get(1): " + cache.get(1)); // promotes 1 to MRU

        cache.put(4, 400); // evicts 2 (LRU)
        System.out.println("After put(4): " + cache.map.keySet());
        System.out.println("get(2): " + cache.get(2)); // -1 (evicted)
        System.out.println("get(1): " + cache.get(1)); // 100 (was promoted)
        System.out.println("Consistent: " + cache.isConsistent());

        // Edge case: capacity 1
        LRUCache tiny = new LRUCache(1);
        tiny.put(1, 10);
        tiny.put(2, 20); // evicts 1
        System.out.println("\nCapacity 1 cache:");
        System.out.println("get(1): " + tiny.get(1)); // -1
        System.out.println("get(2): " + tiny.get(2)); // 20
        System.out.println("Consistent: " + tiny.isConsistent());
    }
}