146.LRU Cache

1.The key to solve this problem is using a double linked list which enables us to quickly move nodes.

2.The LRU cache is a hash table of keys and double linked nodes. The hash table makes the time of get() to be O(1). The list of double linked nodes make the nodes adding/removal operations O(1).

class LRUCache {
    Map<Integer, Node> nodeMap;
    int capacity;
    //A double end linked List
    Node head;
    Node tail;
    public LRUCache(int capacity) {
        nodeMap = new HashMap<>();
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        //If don't have such key;
        if(!nodeMap.containsKey(key)){
            return -1;
        }
        else{
            Node currentNode = nodeMap.get(key);
            //Move currentNode to tail
            currentNode.next.prev = currentNode.prev;
            currentNode.prev.next = currentNode.next;

            currentNode.prev = tail.prev;
            tail.prev = currentNode;
            currentNode.prev.next = currentNode;
            currentNode.next = tail;

            return currentNode.value;
        }
    }

    public void put(int key, int value) {
        if(!nodeMap.containsKey(key)){
            //If reach max capacity
            if(nodeMap.size() == capacity){
                nodeMap.remove(head.next.key);

                head.next = head.next.next;
                head.next.prev = head;
            }

            Node currentNode = new Node(key, value);
            nodeMap.put(key, currentNode);

            currentNode.prev = tail.prev;
            tail.prev = currentNode;
            currentNode.prev.next = currentNode;
            currentNode.next = tail;

        }
        else{
            Node currentNode = nodeMap.get(key);
            currentNode.value = value;
            //Move currentNode to tail
            currentNode.next.prev = currentNode.prev;
            currentNode.prev.next = currentNode.next;

            currentNode.prev = tail.prev;
            tail.prev = currentNode;
            currentNode.prev.next = currentNode;
            currentNode.next = tail;
        }
        return;
    }
    class Node{
        Node prev;
        Node next;
        int key;
        int value;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */