146. LRU Cache!

HashMap and Double LinkedList

class LRUCache {
    
    class Node{
        int key;
        int value;
        Node next;
        Node prev;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, Node> map;
    private Node head;
    private Node tail;
    private int capacity;
    public LRUCache(int capacity) {
        //initialize the doulbely linkedlist
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next=tail;
        tail.prev=head;
        
        map = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            moveToFirst(map.get(key));
            return map.get(key).value;
        }else{
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node node = map.get(key);
            node.value = value;
            moveToFirst(node);
        }else{
            if(map.size()==capacity){
                deleteLast();
            }
            addFirst(new Node(key, value));
        }
    }
    
    private void moveToFirst(Node node){
        node.prev.next=node.next;
        node.next.prev=node.prev;
        node.next=head.next;
        node.prev=head;
        head.next=node;
        node.next.prev=node;
    }
    
    private void deleteLast(){
        Node node = tail.prev;
        node.prev.next=tail;
        tail.prev=node.prev;
        map.remove(node.key);
    }
    
    private void addFirst(Node node){
        map.put(node.key, node);
        head.next.prev=node;
        node.next=head.next;
        head.next=node;
        node.prev=head;
    }
}

/**
 * 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);
 */