---

📖 推荐阅读：《Yocto项目实战教程:高效定制嵌入式Linux系统》
🎥 更多学习视频请关注 B 站：嵌入式Jerry

---

---

LRU缓存机制完全实战：链表的工程落地与面试通关

前言

“链表会了，真能写好LRU吗？”——LRU缓存机制是算法和工程面试的超高频考题，也是链表+哈希表综合应用的经典场景。本文以实战为主，手把手讲透核心实现思路与关键技巧，让你从“会链表”迈向“能设计高效缓存”。

---

一、什么是LRU缓存机制？

LRU（Least Recently Used）意为“最近最少使用”。在限定容量的缓存中，每次数据被访问，都认为它“最新”；容量满时，要踢掉最久没用的数据。

典型需求

• **get(key)：**查找key的值，若命中，则成为最新（移动到队头）。
• **put(key, value)：**写入key，若容量超，踢掉最旧的key。

要求：

• get 和 put 操作都要 O(1) 完成！

---

二、为何必须用链表+哈希表？

• 哈希表：O(1)查找节点。
• 双向链表：O(1)插入/删除/移动节点，随时把任意节点挪到表头或表尾。

这两个结构组合起来，完美满足 LRU 所有需求，是工程界公认的标准方案！

---

三、实战代码：手写LRU缓存机制（C++完整版）

1. 设计思路图

哈希表 key -> 双向链表节点
双向链表：head <-> node1 <-> node2 <-> ... <-> nodeN <-> tail
- 最新的节点在 head 后面
- 最旧的节点在 tail 前面

2. 双向链表节点定义

struct Node {int key, value;Node *prev, *next;Node(int k, int v): key(k), value(v), prev(nullptr), next(nullptr) {}
};

3. 核心成员变量与辅助操作

class LRUCache {
private:unordered_map<int, Node*> cache; // key -> 节点映射int capacity;Node *head, *tail; // 虚拟头尾节点，简化插入/删除逻辑// 把节点从链表中摘除void remove(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;}// 把节点插入到链表头（head后面）void insertToHead(Node* node) {node->next = head->next;node->prev = head;head->next->prev = node;head->next = node;}
public:// 构造函数LRUCache(int cap): capacity(cap) {head = new Node(0,0);tail = new Node(0,0);head->next = tail;tail->prev = head;}

---

4. 核心操作 get & put 实现

get操作

• 查找哈希表，若存在：

  • 将节点挪到链表头，返回值；
  • 否则返回-1。

    int get(int key) {if (cache.count(key)) {Node* node = cache[key];remove(node);insertToHead(node); // 访问后变最新return node->value;}return -1; // 不存在}

put操作

• key已存在：更新值，并挪到链表头；

• key不存在：

  • 如已满，则删掉最旧节点（链表尾部）。
  • 新建节点插入到头，并加入哈希表。

    void put(int key, int value) {if (cache.count(key)) {Node* node = cache[key];node->value = value;remove(node);insertToHead(node);} else {if (cache.size() == capacity) {Node* last = tail->prev;remove(last);cache.erase(last->key);delete last;}Node* node = new Node(key, value);cache[key] = node;insertToHead(node);}}
};

---

四、通俗易懂的代码逻辑小结

• 双向链表，解决“随时挪动、删除”——只需前后指针，时间O(1)。
• 哈希表，解决“查找节点”——不遍历链表，直接定位。
• 虚拟头尾节点，让边界操作不写特判，更简洁安全。

---

五、工程应用思考与面试拓展

LRU 是链表的“综合应用大题”

• 本质考查你能否把“数据结构的优点组合”到实际问题。
• 实际开发中，缓存、消息队列、内存管理、进程调度等大量用到链表的灵活性。

LRU 变形练习

1. 简易单链表实现LRU，体验删除节点的尴尬与低效
2. 扩展为 LFU（最不常用缓存），引入多级链表
3. 配合多线程，探究线程安全链表实现方案
4. 工程系统分析：STL的list、Java LinkedHashMap的底层实现与线程安全问题

---

六、手写小练习题目推荐

1. 单链表反转（加深对指针的理解）
2. 双向链表手写实现（训练基本操作，尤其插入/删除）
3. LRU缓存机制（综合运用链表与哈希表，亲手实现至少一遍）
4. 删除链表中的倒数第k个节点（快慢指针技巧）
5. 合并两个有序链表（链表归并）
6. 环形链表检测（快慢指针）

---

七、结语

LRU 不是“链表应用的尽头”，但一定是你成为链表高手的必经之路。
建议每位同学都要手写实现一次完整的LRU，真正体会链表和哈希表的威力——
不仅仅为了面试，更为了以后能把“合适的数据结构”用到最合适的场景！

---

---