LRUCache

lrucache.java

public class LRUCache {

    private final Map<Integer, Node> map = new HashMap<>();
    private final int capacity;
    private Node head, tail;

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

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

        remove(node);
        add(node);

        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            remove(node);
        }

        node = new Node(key, value);
        map.put(key, node);
        add(node);

        if (map.size() > capacity) {
            map.remove(head.key);
            remove(head);
        }
    }

    private void add(Node node) {
        if (head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
            node.next = null;
        }
    }

    private void remove(Node node) {
        if (node == null) {
            throw new IllegalArgumentException();
        }

        if (head == node) {
            head = node.next;
            if (head != null) {
                head.prev = null;
            }
        }

        if (tail == node) {
            tail = node.prev;
            if (tail != null) {
                tail.next = null;
            }
        }

        if (node.prev != null) {
            node.prev.next = node.next;
        }

        if (node.next != null) {
            node.next.prev = node.prev;
        }

        node.next = null;
        node.prev = null;
    }
    
    private static class Node {
        final int key;
        final int value;
        private Node prev, next;

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

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    '}';
        }
    }
}