LRU缓存通过哈希表和双向链表实现O(1)操作，最近访问节点移至头部，超出容量时删除尾部节点。
LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。在 C++ 中，我们可以通过 哈希表 + 双向链表 的组合高效实现 LRU 缓存，使得 get 和 put 操作的时间复杂度都为 O(1)。
基本设计思路
使用以下两个数据结构协同工作：
- std::unordered_map：用于快速查找缓存中的键，映射 key 到链表中的节点指针。
- 双向链表：维护访问顺序，最近使用的放在头部，最久未使用的在尾部，便于快速删除和插入。
每次访问某个 key，就将其移动到链表头部；插入新元素时，若超出容量，则删除尾部节点。
节点结构与类定义
struct ListNode {
int key;
int value;
ListNode* prev;
ListNode* next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
定义 LRU 缓存类：
立即学习“C++免费学习笔记（深入）”；
class LRUCache {
private:
int capacity;
std::unordered_map cache;
ListNode* head; // 哨兵头节点
ListNode* tail; // 哨兵尾节点
void removeNode(ListNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(ListNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
void moveToHead(ListNode* node) {
removeNode(node);
addToHead(node);
}
ListNode* removeTail() {
ListNode* node = tail->prev;
removeNode(node);
return node;
}public:
LRUCache(int cap) : capacity(cap) {
head = new ListNode(0, 0);
tail = new ListNode(0, 0);
head->next = tail;
tail->prev = head;
}
~LRUCache() {
while (head) {
ListNode* temp = head;
head = head->next;
delete temp;
}
}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
ListNode* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
ListNode* node = cache[key];
node->value = value;
moveToHead(node);
} else {
ListNode* newNode = new ListNode(key, value);
cache[key] = newNode;
addToHead(newNode);
if (cache.size() > capacity) {
ListNode* tailNode = removeTail();
cache.erase(tailNode->key);
delete tailNode;
}
}
}};
使用示例
简单测试代码：
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
std::cout << lru.get(1) << std::endl; // 输出 1
lru.put(3, 3); // 淘汰 key=2
std::cout << lru.get(2) << std::endl; // 输出 -1
return 0;
}
这个实现中，get 和 put 都是 O(1) 时间复杂度，符合高频访问场景的需求。通过哨兵节点简化了边界判断，代码更清晰稳定。
基本上就这些，核心是理解哈希表定位 + 双向链表维护顺序的协作机制。不复杂但容易忽略细节，比如指针连接、内存释放等。实际项目中也可考虑用 std::list 替代手动管理链表，进一步简化逻辑。
