雙向鏈表版本：

#include <bits/stdc++.h>
using namespace std;
struct Node{int key, value;Node* prev;Node* next;Node():key(0), value(0), prev(nullptr), next(nullptr){}Node(int k, int v):key(k), value(v), prev(nullptr), next(nullptr){}
};
class LRUCache{
private:int capacity_;int size_;Node* head;Node* tail;unordered_map<int, Node*> cache_;
public:LRUCache(int capacity): capacity_(capacity), size_(0){head = new Node();tail = new Node();head->next = tail;tail->prev = head;}void removeNode(Node* node){node->prev->next = node->next;node->next->prev = node->prev;}void addToHead(Node* node){node->next = head->next;node->prev = head;head->next->prev = node;head->next = node;}void moveToHead(Node* node){removeNode(node);addToHead(node);}Node* removeTail(){auto node = tail->prev;removeNode(node);return node;}int get(int key){if(cache_.find(key) != cache_.end()){moveToHead(cache_[key]);return cache_[key]->value;}return -1;}void put(int key, int value){if(cache_.find(key) != cache_.end()){moveToHead(cache_[key]);cache_[key]->value = value;}else{if(size_ == capacity_){auto node = removeTail();cache_.erase(node->key);delete node;--size_;}auto node = new Node(key, value);addToHead(node);cache_.insert({key, node});++size_;}}~LRUCache(){while(head){auto node = head;head = head->next;delete node;}}void print(){cout << "=================" << endl;auto node = head->next;while(node != tail){cout << "[" << node->key << " " << node->value << "]" << endl;node = node->next;}}
};
int main(){auto lru = new LRUCache(2);lru->put(1, 1);lru->put(2, 2);lru->print();lru->put(3, 3);lru->print();cout << lru->get(2) << endl;lru->print();lru->put(4, 4);lru->print();cout << lru->get(1) << endl;lru->print();cout << lru->get(3) << endl;return 0;
}

手寫雙向鏈表版本比較簡單，在紙上畫一畫就能想通！

STL的list版本：

using pi = pair<int, int>;
class LRUCache {
public:LRUCache(int capacity):capacity_(capacity){}/*** 根據給定的鍵獲取緩存中的值。* 如果鍵存在于緩存中，則將該鍵值對移動到緩存的前端，并返回對應的值。* 如果鍵不存在于緩存中，則返回-1。* * @param key 要查詢的鍵。* @return 存儲在緩存中的鍵對應的值，如果鍵不存在則返回-1。*/int get(int key) {// 檢查鍵是否存在于緩存中if(key_table_.count(key)){// 獲取鍵對應的節點auto node = key_table_[key];// 從節點中提取值int value = node->second;// 從緩存中刪除節點，因為它即將被移動到前端cache_.erase(node);// 將鍵值對移動到緩存的前端cache_.push_front({key, value});// 更新鍵在映射表中的指針，指向移動到前端的新節點key_table_[key] = cache_.begin();// 返回鍵對應的值return value;}// 如果鍵不存在，返回-1return -1;}/*** 將鍵值對(key, value)放入緩存。* 如果鍵已經存在，則更新對應的值，并從緩存中移除該鍵值對，以便重新插入以維護LRU順序。* 如果緩存已滿，則移除最不常訪問的鍵值對，為新鍵值對騰出空間。* * @param key 要放入緩存的鍵。* @param value 要放入緩存的值。*/void put(int key, int value) {// 如果鍵已經存在，則獲取對應的節點if(key_table_.count(key)){auto node = key_table_[key];int value = node->second;// 從緩存中移除該節點，因為待會要重新插入以維護LRU順序cache_.erase(node);}else{// 如果緩存已滿，則移除最不常訪問的鍵值對if(cache_.size() == capacity_){auto kv = cache_.back();int k = kv.first, v = kv.second;cache_.pop_back();key_table_.erase(k);}}// 將新的鍵值對插入到緩存的前端，并更新鍵映射表cache_.push_front({key, value});key_table_[key] = cache_.begin();}
private:unordered_map<int, list<pi>::iterator> key_table_; list<pi> cache_;   // 緩存int capacity_;   
};

主要用了迭代器，對于初學者可能難以理解。可以看我的下一篇博客，詳細闡述了迭代器設計思想！