• 🙋?♂? 作者：海碼007
• 📜 專欄：算法專欄
• 💥 標題：【Hot 100】 146. LRU 緩存
• ?? 寄語：書到用時方恨少，事非經過不知難！

引言

這題好像幾年前就是hard。后面變成medium了。感覺就是普通人只做1～2遍，都不能獨立記住整個實現過程。做到第3遍時大概能記得思路開始獨立寫代碼了，但是會遇到各種問題不能bug free的AC掉。需要練很多遍才能真的在面試中寫對的。這題應該就是靠代碼功底的，看能不能現場寫出bug free或者能debug出來。

上面的這個是別人寫的評論，看著確實是這么回事。今天能把這道題寫完就算ok了。這個相當于設計一個類了。

LRU 緩存

• 🎈 題目鏈接：
• 🎈 做題狀態：

官方解題

這道題涉及的知識面確實比較多，第一次做的話不容易ac。可以多寫幾次。

struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};class LRUCache {
private:unordered_map<int, DLinkedNode*> cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;public:LRUCache(int _capacity) : capacity(_capacity), size(0) {// 使用偽頭部和偽尾部節點head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {// 判斷當前key是否存在if (!cache.count(key)){return -1;}// 通過哈希表快速的找到節點DLinkedNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {// 判斷當前key是否存在if (!cache.count(key)){// 不存在，則創建一個新節點DLinkedNode* node = new DLinkedNode(key, value);// 將其添加到哈希表中cache[key] = node;// 將新的節點添加到雙向鏈表的頭部，因為是新使用的addToHead(node);++size;// 判斷當前鏈表大小是否超過容量，如果超出容量，則需要刪除尾部節點if (size > capacity){DLinkedNode* removed = removedTail();cache.erase(removed->key);delete removed;--size;}}else{// 如果當前key存在，先通過哈希表定位，再修改value，并移動到頭部DLinkedNode* node = cache[key];node->value = value;moveToHead(node);}}// 將節點添加到頭部void addToHead(DLinkedNode* node){node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}// 移除節點（不釋放節點內存）void removeNode(DLinkedNode* node){node->prev->next = node->next;node->next->prev = node->prev;}// 將節點移動到頭部void moveToHead(DLinkedNode* node){removeNode(node);addToHead(node);}// 將移除的節點返回給外部進行處理釋放DLinkedNode* removedTail(){DLinkedNode* node = tail->prev;removeNode(node);return node;}
};/*** 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);*/

LRU實現

我將把 LRU 緩存的實現拆解為 7 個清晰的步驟，并配以關鍵代碼片段。讓我們像搭積木一樣逐步構建這個數據結構：

---

📌 實現步驟分解

步驟 1：定義雙向鏈表節點

目的：創建存儲數據的基本單元

struct Node {int key;        // 用于刪除尾節點時反向查找哈希表int value;Node* prev;Node* next;Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

---

步驟 2：創建偽頭尾節點（關鍵設計）

目的：消除邊界條件判斷，簡化鏈表操作

class LRUCache {
private:Node* dummyHead; // 永遠指向虛擬頭部節點Node* dummyTail; // 永遠指向虛擬尾部節點// 初始化偽頭尾dummyHead = new Node(-1, -1);dummyTail = new Node(-1, -1);dummyHead->next = dummyTail;dummyTail->prev = dummyHead;

---

步驟 3：實現鏈表基礎操作

操作 1：添加節點到頭部

void addToHead(Node* node) {// 新節點的前后指針node->prev = dummyHead;node->next = dummyHead->next;// 調整原有鏈接dummyHead->next->prev = node;dummyHead->next = node;
}

操作 2：移除任意節點

void removeNode(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;
}

---

步驟 4：實現關鍵組合操作

操作 3：移動節點到頭部（訪問時調用）

void moveToHead(Node* node) {removeNode(node);  // 從當前位置移除addToHead(node);   // 添加到頭部
}

操作 4：移除尾部節點（淘汰時調用）

Node* removeTail() {Node* node = dummyTail->prev; // 真實尾節點removeNode(node);return node;
}

---

步驟 5：初始化緩存結構

class LRUCache {
private:unordered_map<int, Node*> cache; // 哈希表int capacity;                    // 容量限制public:LRUCache(int cap) : capacity(cap) {// 初始化偽頭尾（見步驟2）}
};

---

步驟 6：實現 get 操作

int get(int key) {if (!cache.count(key)) return -1; // 未命中Node* node = cache[key];moveToHead(node);    // 更新為最近使用return node->value;
}

---

步驟 7：實現 put 操作

void put(int key, int value) {if (cache.count(key)) { // 已存在Node* node = cache[key];node->value = value;    // 更新值moveToHead(node);       // 設為最新} else {                   // 新增數據Node* node = new Node(key, value);cache[key] = node;      // 記錄到哈希表addToHead(node);        // 添加到鏈表if (cache.size() > capacity) {Node* removed = removeTail();  // 淘汰最舊cache.erase(removed->key);     // 從哈希表刪除delete removed;                // 釋放內存}}
}

---

🔑 關鍵設計驗證點

測試場景	預期操作	驗證方法
緩存未滿時插入	新節點添加到頭部	檢查鏈表頭部是否為最新節點
緩存已滿時插入	淘汰尾節點后添加新節點到頭部	檢查鏈表長度是否保持 capacity
訪問已有節點	節點被移動到頭部	執行get后檢查節點位置
更新已有節點的值	值被更新且節點移到頭部	檢查值變化和節點位置

---

🚀 完整實現代碼

#include <unordered_map>
using namespace std;struct Node {int key, value;Node *prev, *next;Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};class LRUCache {
private:unordered_map<int, Node*> cache;Node *dummyHead, *dummyTail;int capacity;void addToHead(Node* node) {node->prev = dummyHead;node->next = dummyHead->next;dummyHead->next->prev = node;dummyHead->next = node;}void removeNode(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;}void moveToHead(Node* node) {removeNode(node);addToHead(node);}Node* removeTail() {Node* node = dummyTail->prev;removeNode(node);return node;}public:LRUCache(int cap) : capacity(cap) {dummyHead = new Node(-1, -1);dummyTail = new Node(-1, -1);dummyHead->next = dummyTail;dummyTail->prev = dummyHead;}int get(int key) {if (!cache.count(key)) return -1;Node* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {if (cache.count(key)) {Node* node = cache[key];node->value = value;moveToHead(node);} else {Node* node = new Node(key, value);cache[key] = node;addToHead(node);if (cache.size() > capacity) {Node* removed = removeTail();cache.erase(removed->key);delete removed;}}}
};

---

💡 實現要點總結

1. 雙數據結構協作：

   • 哈希表：O(1) 時間查找
   • 雙向鏈表：維護訪問順序

2. 偽節點的妙用：

   • 消除頭尾節點的特殊判斷
   • 統一所有節點的操作邏輯

3. 操作原子化：

   • 將鏈表操作分解為獨立方法
   • 提高代碼可讀性和可維護性

4. 內存管理：

   • 淘汰節點時需手動釋放內存
   • 插入新節點時動態分配內存

通過這種分步實現方式，可以更清晰地理解每個組件的作用，也便于在開發過程中逐步測試驗證每個功能的正確性。