LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

/*

LinkedHashMap = DoublyLinkedList + HashMap.

Newest node append to tail and eldest node remove from head.

Notice: 

1. When use DoublyLinkedList, ListNode head and tail should be initialized at first.

2. In the ListNode, key should be added. 

*/

public class Solution {

    private class ListNode {

        ListNode prev;

        ListNode next;

        int key;

        int value;

        public ListNode(int key, int value) {

            this.key = key;

            this.value = value;

            prev = null;

            next = null;

        }

    }

    

    private int capacity;

    private Map<Integer, ListNode> map = new HashMap<>();

    private ListNode head = new ListNode(-1, -1);

    private ListNode tail = new ListNode(-1, -1);

    

    public Solution(int capacity) {

        this.capacity = capacity;

        head.next = tail;

        tail.prev = head;

    }

    public int get(int key) {

        if (!map.containsKey(key)) {

            return -1;

        }

        ListNode temp = map.get(key);

        temp.prev.next = temp.next;

        temp.next.prev = temp.prev;

        moveToTail(temp);

        

        return map.get(key).value;

    }

    public void set(int key, int value) {

        if (get(key) != -1) {

            map.get(key).value = value;

            return;

        }

        if (map.size() == capacity) {

            //This is why key should be added to the ListNode.

            map.remove(head.next.key);  

            head.next = head.next.next;

            head.next.prev = head;

        }

        

        ListNode node = new ListNode(key, value);

        map.put(key, node);

        moveToTail(node);

    }

    

    private void moveToTail(ListNode node) {

        node.prev = tail.prev;

        node.next = tail;

        tail.prev = node;

        node.prev.next = node;

    }

}