Grokking Newsletter 218

class LRUCache {

    int capacity;
    int size;

    Map<Integer, Node> table;
    Node dummyHead;
    Node dummyTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;

        table = new HashMap<Integer, Node>();

        // Use dummy head, dummy tail to reduce checking null conditions.
        dummyHead = new Node();
        dummyTail = new Node();

        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public int get(int key) {
        Node node = table.get(key);

        if (node == null) {
            return -1;
        }

        // node is most recently used value, so move to head of linked list
        moveToHead(node);

        return node.value;
    }

    public void put(int key, int value) {
        Node node = table.get(key);

        if (node == null) {
            // if key doesn't exist, put new value node head of linked list
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;

            table.put(key, newNode);
            addNodeToHead(newNode);

            ++size;

            // evict least recently used item if current size is greater than capacity
            if (size > capacity) {
                Node tail = removeTail();
                table.remove(tail.key);
                --size;
            }
        } else {
            // if key exists, just update value
            node.value = value;
            moveToHead(node);
        }
    }

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

    private void addNodeToHead(Node node) {
        node.next = dummyHead.next;
        node.prev = dummyHead;

        dummyHead.next.prev = node;
        dummyHead.next = node;
    }

    private Node removeTail() {
        Node ans = dummyTail.prev;
        removeNode(ans);

        return ans;
    }

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

    // Doubly linked-list node
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
    }

}