LRUCache.java

public class LRUCache {
    
    Node head;
    int capacity;
    
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.value = val;
        }
    }
    
    Map<Integer, Node> map = new HashMap<>();
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public Integer get(int key) {
        Integer value = poll(key);
        if (value != null) {
            insertToEnd(key, value);
        } else {
            value = -1;
        }
        return value;
    }
    
    public void set(int key, int value) {
        Integer val = poll(key);
        insertToEnd(key, value);
        if (map.size() > capacity) {
            removeFirst();
        }
    }
    
    void removeFirst() {
        map.remove(head.key);
        
        Node prev = head.prev;
        Node next = head.next;
        prev.next = next;
        next.prev = prev;
        head = next;
    }
    
    void insertToEnd(int key, int value) {
        if (head == null) {
            head = new Node(key, value);
            head.next = head;
            head.prev = head;
            
            map.put(key, head);
        } else {
            Node prev = head.prev;
            
            Node node = new Node(key, value);
            node.prev = prev;
            node.next = head;
            
            prev.next = node;
            head.prev = node;
            map.put(key, node);
        }
    }
    
    Integer poll(Integer key) {
        Node cur = map.get(key);
        if (cur == null) {
            return null;
        } else {
            Integer res = cur.value;
            Node prev = cur.prev; //1
            Node next = cur.next; //1
            
            if (head == cur) {
                head = next;
            }
            
            prev.next = cur.next; // 1
            next.prev = prev;
            map.remove(key);
            return res;
        }
    }
}