【LeetCode雙向連結串列】LRU詳解，雙向連結串列實戰

LRU快取

請你設計並實現一個滿足 LRU (最近最少使用) 快取約束的資料結構。
實現 LRUCache 類：

LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 快取
int get(int key) 如果關鍵字 key 存在於快取中，則返回關鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關鍵字 key 已經存在，則變更其資料值 value ；如果不存在，則向快取中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該逐出最久未使用的關鍵字。

函數 get 和 put 必須以 O(1) 的平均時間複雜度執行。

範例：

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 快取是 {1=1}
lRUCache.put(2, 2); // 快取是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，快取是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，快取是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

思路

LRU 的全稱是 Least Recently Used，也就是「最近使用過的」，就是字面意思，這裡指的是快取中最近被使用過的資料。

我們都知道快取的大小是有限的，因此需要使用有效的方法去管理快取

LRU的思路很直接，就是以「最近是否被使用」為標準將快取中每個資料進行排序，被使用越頻繁的資料排序越靠前，相對的，不經常使用的資料會隨著時間推移，排序逐漸靠後，直到被丟棄（當有新資料要進快取而此時快取空間又不夠時，就會丟棄最不常使用的資料）

假設當前快取中只能存3個值，那麼根據LRU的規則會有以下情況：

現在我們有了一個"雜湊連結串列"，接下來開始實現取值函數get

get方法

在get方法中，首先在雜湊表中查詢是否存在指定的key。

如果存在，則將該節點從連結串列中原位置取出，然後將其插入到連結串列頭的後一個位置，以表示最近被存取過，最終返回該節點對應的value值。

如果不存在，則直接返回-1。

class LRUCache {
    struct ListNode{//定義節點結構體
        ...
    };
    ListNode* dummy;
    int maxSize;//最大快取數量
    int nodeNums;//當前快取中的節點數量
    //定義雜湊表，key是int，val是節點
    unordered_map<int, ListNode*> hash;
    
public:
    LRUCache(int capacity): maxSize(capacity), dummy(new ListNode){//不用參數列也行
        nodeNums = 0;
        //dummy的 next 和 prev 指標都指向自身，這樣當快取為空時，dummy既是頭節點也是尾節點
        dummy->next = dummy;
        dummy->pre = dummy;
    }
    
    int get(int key) {// 如果關鍵字 key 存在於快取中，則返回關鍵字的值，否則返回 -1 。
        if(hash.find(key) != hash.end()){
            //找到對應節點，取出
            ListNode* node = hash[key];
            //將node從當前位置移除
            node->pre->next = node->next;
            node->next->pre = node->pre;
            //把node插到dummy的後面，也就是連結串列頭部
            node->next = dummy->next;
            node->pre = dummy;
            dummy->next->pre = node;//令dummy後面節點的前面節點為node
            dummy->next = node;//令dummy的後面節點為node
            return node->val;      
        }
        return -1;//沒找到對應節點返回-1
    }
    
    void put(int key, int value) {
    }
};

這裡涉及雙向連結串列的節點CRUD，過程圖示如下：

刪除節點node

程式碼

雙向連結串列+雜湊表

class LRUCache {
    struct ListNode{//定義節點結構體
        ...
    };
    ListNode* dummy;
    int maxSize;//最大快取數量
    int nodeNums;//當前快取中的節點數量
    //定義雜湊表，key是int，val是節點
    unordered_map<int, ListNode*> hash;
    
public:
    LRUCache(int capacity): maxSize(capacity), dummy(new ListNode){//不用參數列也行
        nodeNums = 0;
        //dummy的 next 和 prev 指標都指向自身，這樣當快取為空時，dummy既是頭節點也是尾節點
        dummy->next = dummy;
        dummy->pre = dummy;
    }
    
    int get(int key) {
        ...
    }
    //如果關鍵字 key 已經存在，則變更其資料值 value ；如果不存在，則向快取中插入該組 key-value 
    void put(int key, int value) {
        //檢查是否存在對應鍵值
        if(hash.find(key) != hash.end()){//存在
            hash[key]->val = value;//鍵已經存在於雜湊表中，那麼需要更新這個鍵對應的節點的值
            get(key);//呼叫 get(key) 函數，將這個節點移動到連結串列頭部，表示最近存取過它
        }else{//不存在，新增進連結串列
            if(nodeNums < maxSize){//快取沒滿
                nodeNums++;//快取中當前節點數增加
                //建立新節點
                ListNode* node = new node;
                node->key = key;
                node->val = val;
                //雜湊表對應位置進行記錄
                hash[key] = node;
                //將新節點插到dummy後面，也就是連結串列頭部
                node->next = dummy->next;
                node->pre = dummy;
                dummy->next->pre = node;
                dummy->next = node;
            }else{//快取滿了，刪除此時連結串列末尾的節點
                //取連結串列最後一個節點，即dummy的pre指標指向的節點
                ListNode* node = dummy->pre;
                hash.erase(node->key);//在雜湊表中刪除對應節點
                hash[key] = node;//在雜湊表中新增新的鍵值對，其中 key 是快取節點的鍵，node 則是新的節點。
				node->key=key;//更新 node 節點的鍵值為新的 key。	
				node->val=value;
                get(key);
            }
        }      
    }
};

佇列+雜湊表

TBD