資料結構和算法：實作LRU緩存機制

題目

題目連接配接

運用你所掌握的資料結構，設計和實作一個LRU(最近最少使用)緩存機制。它應該支援以下操作：擷取資料get和寫入資料put

1. 擷取資料get(key)：如果密鑰存在緩存中，則擷取密鑰的值(總是正數)，則傳回-1；
2. 寫入資料put(key，value)：如果密鑰不存在，則寫入其資料值，當緩存容量達到上限時，它應該在寫入新資料之前删除最近最少使用的資料，進而為新的資料值留出空間。

在實際複雜度O(1)時間複雜度内完成這兩種操作？

思路

可以使用哈希表，輔以雙向連結清單記錄鍵值對的資訊。是以可以在O(1)時間内完成put和get操作。

使用雙向連結清單的一個好處是不需要額外資訊删除一個節點，同時可以在常數時間内從頭部或尾部插入删除節點；

一個需要注意的是，在雙向連結清單實作中，這裡使用一個僞頭部标記界限，這樣在更新的時候就不需要檢查是否是null節點；

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

        private Node dummyHead = new Node();
        private Node dummyTail = new Node();
        private HashMap<Integer, Node> hashMap = new HashMap<>();
        private int capacity;
        private int size;
        
      	//add和del函數是留給LRU機制的，當get和put操作時，更新節點的位置
        public void add(Node node){
            Node original = dummyHead.next;
            dummyHead.next = node;
            node.pre=dummyHead;
            node.next = original;
            original.pre = node;
        }
        public void del(Node node){
            Node preNode = node.pre;
            Node nextNode = node.next;
            preNode.next = nextNode;
            nextNode.pre = preNode;
            node.next = null;
            node.pre = null;
        }

        public LRUCache(int capacity){
            dummyHead.next = dummyTail;
            dummyTail.pre = dummyHead;
            this.capacity = capacity;
            size = 0;
        }
        public int get(int key){
            Node node = hashMap.get(key);
            if(null == node){
                return -1;
            }else{
                del(node);
                add(node);
                return node.value;
            }
        }
        public void put(int key, int value){
            Node node = hashMap.get(key);
            if(node != null){
                //如果key對應節點存在，則重新指派
              	//并将節點更新到連結清單的頭部
                node.value = value;
                del(node);
                add(node);
            }else{
              	//如果節點不存在
              	//分位兩種情況：一種是容量已滿
              	//另外一種是未滿
                if(size < capacity){
                    size ++
                }else{
                    Node preTail = dummyTail.pre;
                    hashMap.remove(preTail.key);
                    del(preTail);
                }
                Node newNode = new Node(key, value);
                add(newNode);
                hashMap.put(key, newNode);
            }
        }

    }
}

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