146. LRU Cache

Time complexity : O(1) both for put and get since all operations with ordered dictionary :
get/in/set/move_to_end/popitem (get/containsKey/put/remove) are done in a constant time.

Space complexity : O(capacity) since the space is used only for
an ordered dictionary with at most capacity + 1 elements.

notice: init head, map operation do first

class LRUCache {
    class DoubleLinkedListNode {     
        int key;
        int val;        
        DoubleLinkedListNode prev, next;        
        DoubleLinkedListNode(int key, int val) {    
            this.key = key;
            this.val = val;            
            this.prev = null;            
            this.next = null;        
        }    
    }
    
    private Map<Integer, DoubleLinkedListNode> map;
    private DoubleLinkedListNode head;
    private DoubleLinkedListNode tail;
    private int capacity;
    
    public LRUCache(int capacity) {
        this.head = new DoubleLinkedListNode(-1, -1); // dummy node, remember init       
        this.tail = head;
        this.map = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        DoubleLinkedListNode curr = map.get(key);
        remove(curr);
        moveToFront(curr);
        return curr.val;
    }
    
    public void put(int key, int value) {
        // just reuse get()
        if (get(key) != -1) {
            map.get(key).val = value;
            return;
        }
        if (map.size() == capacity) {		//超出缓存上限
            //map.remove(head.next.key);		//刪除 tail data
            // head.next = head.next.next;
            // head.next.prev = head;
            map.remove(tail.key); // map operation do first
            remove(tail);
        }

        DoubleLinkedListNode insert = new DoubleLinkedListNode(key, value);		//新建节点
        map.put(key, insert);
        moveToFront(insert);
    }
    // 2 cases
    // node1 <->  node2
    // node1 -> node -> null
    public void remove(DoubleLinkedListNode node) {
        DoubleLinkedListNode prev = node.prev;        
        prev.next = node.next;        
        if (node.next != null) {            
            node.next.prev = prev;        
        } else {            
            tail = prev;        
        }
    }
    // 2 cases
    // head -> new node -> node1
    // head -> new node -> null
    private void moveToFront(ListNode node) {
        if (head.next == null) {
            head.next = node;
            node.prev = head;
            tail = node;
        } else {
            node.next = head.next;
            node.next.prev = node;
            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);
 
 
 if > capacity, evict last, 
 
 if (key in middle or last, ) delete by linkedlist O(1), find use hashmapO(1)
 if (key exist update it, move to last
 
 add new to last
 
 
 */