LRUCache.java

package dev.mrpato;

import java.util.*;

/**
 * Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
 * <p>
 * Problem: https://leetcode.com/problems/lru-cache
 */
public class LRUCache {

    final Node tail;
    final Node head;
    final Map<Integer, Node> nodes;
    final int capacity;

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

        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);

        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public int get(final int key) {
        final Node found = nodes.get(key);
        if (Objects.isNull(found)) {
            return -1;
        }
        final int value = found.value;
        moveToFront(found);
        return value;
    }

    public void put(int key, int value) {
        final Node existing = nodes.get(key);
        if (Objects.nonNull(existing)) {
            existing.value = value;
            nodes.put(key, existing);
            moveToFront(existing);
        } else {
            if (nodes.size() == capacity) {
                final var keyToBeRemoved = this.tail.prev.key;
                final Node tempPrev = this.tail.prev.prev;
                tempPrev.next = this.tail;
                this.tail.prev = tempPrev;
                nodes.remove(keyToBeRemoved);
            }
            final Node newNode = new Node(key, value);
            add(newNode);
            nodes.put(key, newNode);
        }
    }

    private void moveToFront(final Node node) {
        final Node tempPrev = node.prev;
        final Node tempNext = node.next;

        node.prev.next = tempNext;
        tempNext.prev = tempPrev;

        add(node);
    }

    private void add(final Node node) {
        final Node tempHead = this.head.next;
        node.prev = this.head;
        node.next = tempHead;
        tempHead.prev = node;
        this.head.next = node;
    }

    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;

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

}