Untitled

public class Solution {
    
    class Node{
        int key;
        int val;
        Node next;
        Node prev;
        
        public Node(int k, int v){
            this.key = k;
            this.val = v;
            this.next = null;
            this.prev = null;
        }
    }
    
    int size;
    int cap;
    Node head;
    Node tail;
    HashMap<Integer, Node> map;
    
    public Solution(int capacity) {
        size = 0;
        cap = capacity;
        head = new Node(-1, -1);
        tail = new Node(-2, -2);
        head.next = tail;
        tail.prev = head;
        map = new HashMap<>();
    }
    
    public void addToTail(Node x){
        x.next = tail;
        x.prev = tail.prev;
        tail.prev = x;
        x.prev.next = x;
    }
    
    public void remove(Node y){
        y.prev.next = y.next;
        y.next.prev = y.prev;
    }
    
    public void removeFromHead(){
        map.remove(head.next.key);
        remove(head.next);
        size--;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }else{
            Node x = map.get(key);
            int ans = x.val;
            remove(x);
            addToTail(x);
            return ans;
        }
    }
    
    public void set(int key, int value) {
        if(map.containsKey(key) == true){
            // hit
            Node x = map.get(key);
            remove(x);
            addToTail(x);
            x.val = value;
        }else{
            //miss
            if(size < cap){
                Node nn = new Node(key, value);
                map.put(key, nn);
                addToTail(nn);
                size++;
            }else if(size == cap){
                removeFromHead();
                Node nn = new Node(key, value);
                map.put(key, nn);
                addToTail(nn);
                size++;
            }
        }
    }
}