Mastering LRU Cache: Hand‑Write a Least Recently Used Algorithm in Java

What is LRU?

LRU stands for Least Recently Used, a cache eviction strategy that removes the least recently accessed items.

Implementation Idea

Use a hash map for O(1) key lookup and a doubly linked list to maintain access order, with the most recently used items at the head and the least at the tail.

Data Structures

Node class stores key, value, and pointers to previous and next nodes.

<code>class Node {
    int key;
    int value;
    Node prev;
    Node next;
    Node() {}
    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}</code>

LRUCache Class

Contains size, capacity, a hash map cache, and dummy head and tail nodes.

<code>class LRUCache {
    private int size;
    private int capacity;
    private Map<Integer, Node> cache;
    private Node head; // dummy head
    private Node tail; // dummy tail

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                Node tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
}</code>

Why Store Key in Node?

The key is needed to locate and delete the corresponding entry in the hash map when removing the tail node.