必须用双向链表，因单向链表无法o(1)获取前驱节点，而lru需频繁将任意命中节点移至头部；哈希表存key→节点映射实现快速查找，双向链表维护访问时序以支持o(1)删尾和移头。

用链表实现LRU（Least Recently Used）缓存，核心是利用双向链表维护访问时序 + 哈希表实现O(1)查找，确保“最近使用”的节点总在头部，“最久未用”的节点总在尾部，淘汰时直接删尾。

为什么必须用双向链表，不能用单向？

单向链表无法在O(1)时间内删除中间节点——因为不知道前驱。而LRU在get或put命中时，需把对应节点移到头部，这就要求能快速摘下任意节点并重连。双向链表通过prev和next指针，配合节点自身，可完成常数时间的拆入操作。

哈希表与链表如何协同工作？

哈希表（如Java的HashMap、Python的dict）存储 key → 链表节点 的映射，解决“根据key快速定位节点”的问题；双向链表按访问时间排序，解决“谁该被淘汰”的问题。两者缺一不可：

• get(key)：查哈希表得节点 → 摘下该节点 → 插到头 → 返回值
• put(key, value)：若key存在 → 更新值 + 移至头部；若不存在 → 新建节点插头 → 若超容量 → 删尾节点 + 清除哈希表中对应key

关键操作的实现要点

所有链表操作必须维护头尾哨兵节点（dummy head / tail），避免空指针判断和边界特判：

• 插入头部：newNode.next = head.next；head.next.prev = newNode；head.next = newNode；newNode.prev = head
• 删除节点：node.prev.next = node.next；node.next.prev = node.prev
• 移动到头部：先删除，再插入头部（两步合并写更安全）

容量控制与节点清理

每次put后检查链表长度（或单独维护size变量），一旦超过capacity，立即执行：获取tail.prev（即最后一个有效节点）→ 从链表中删除 → 从哈希表中remove其key。注意：不要误删哨兵节点，tail.prev才是待淘汰目标。

不复杂但容易忽略：节点的prev/next指针更新必须成对、顺序正确，否则链表断裂；哈希表和链表的增删必须严格同步，否则出现“表里不一”导致bug。