Untitled

class LRUCache {
        int capacity;
        CacheNode head;
        CacheNode tail;
        HashMap<Integer, CacheNode> map;

        public LRUCache(int capacity) {
            head = new CacheNode(-1, -1);
            tail = new CacheNode(-1, -1);
            head.next = tail ;
            tail.prev = head;
            this.map = new HashMap<>(capacity);
            this.capacity = capacity;
        }
        

        private void addNode(CacheNode node){
                      // always add to first
            CacheNode temp = head.next;
            head.next = node;
            node.prev = head;
            node.next = temp;
            temp.prev = node;
        }

        private void removeNode(CacheNode node){
           // connect pre and next of the node
            CacheNode pre = node.prev;
            CacheNode next = node.next;
            pre.next = next;
            next.prev = pre;

        }
        public int get(int key) {
            //check the value then move it to top
            if ( !map.containsKey(key) ) {
                return -1;
            }
            //if exist
            CacheNode node = map.get(key);
            int ans = node.value;
            // move to the first
            map.remove(key);
            removeNode(node);
            addNode(node);
            
            map.put(key, head.next);
            return ans;

        }

        public void put(int key, int value) {
            if ( !map.containsKey(key) ) {
                // not exist
                // check if full
                if( map.size() >= capacity){
                    CacheNode delete = tail.prev;
                    map.remove(delete.key);
                    delete.prev.next = tail;
                    tail.prev = delete.prev;
                    // add new one to head
                    CacheNode newNode = new CacheNode(key, value);
                    addNode(newNode);
                    map.put(key, newNode);
                }else{
                    // not full
                    CacheNode newNode = new CacheNode(key, value);
                    addNode(newNode);
                    map.put(key, newNode);
                }
          }else{
                // key exist, update it
                CacheNode node = map.get(key);
                node.value = value;
                removeNode(node);
                addNode(node);
            }

        }
}

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

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