题目描述
思路解析
一句话答案：LeetCode 146 LRU 缓存的标准解是哈希表加双向链表：哈希表负责用 key 一步定位到链表节点，双向链表按使用先后排新旧，靠尾的最新、靠头的最旧，让 get 和 put 都做到 O(1) 时间，空间 O(capacity)。淘汰时两个结构必须同步删除，少删一边就出 bug。
LRU 缓存到底要实现什么
LRU（Least Recently Used，最近最少使用）是一种淘汰策略：缓存容量有限，装满之后再写入新键，就把最久没被用过的那个键扔掉。题目要求实现 get 和 put 两个操作，get 未命中返回 -1，并且两个操作都必须 O(1)。难点不在语义，而在这个 O(1)——它同时要求「按 key 查得快」和「随时知道谁最旧」，任何单一数据结构都做不到。
为什么哈希表和链表单独用都不够
只用哈希表，查任何 key 都是 O(1)，但哈希表不记录使用顺序，容量满了不知道该淘汰谁，除非 O(n) 遍历一遍。只用链表，可以把节点按使用先后排好，最旧的永远在头部，但想找到某个 key 对应的节点得从头扫，get 退化成 O(n)。两者的短板恰好互补，解法于是自然成形：哈希表存「key 到链表节点」的映射负责定位，双向链表负责排新旧，每次操作两边同步维护。
链表为什么必须双向，哨兵节点是干什么的
每次 get 或 put 命中，都要把节点从当前位置摘下来、接到链表尾部表示「刚用过」。摘除一个节点需要同时改它前驱和后继的指针，单向链表拿不到前驱、得再花 O(n) 去找，而双向链表两头都有引用，摘除只改固定几根指针，O(1) 完成。
再在头尾各放一个不存数据的哨兵节点 HEAD 和 TAIL，任何真实节点就都有左右邻居，删除和插入不必判空，边界代码大幅简化；「最旧的节点」也永远等于 head.next，一步锁定，淘汰不需要任何查找。
get 和 put 的每一步为什么这么设计
get 命中后不能只返回值：这个 key 刚被使用过，必须把节点摘下再接到尾部刷新新旧顺序，否则它会被误当成旧数据提前淘汰。put 时若 key 已存在，同样先摘掉旧节点再把新节点接到尾部——更新值也算一次使用，这是最容易被忽略的规则。
插入后如果超出容量，取 head.next 这个最旧节点，把它从链表摘掉，同时从哈希表里删掉对应的 key。链表和哈希表必须同步增删：只删链表不删哈希表，之后 get 会命中一个已经脱链的僵尸节点，数据从此不一致，还会泄漏内存。
复杂度怎么算，有没有现成的写法
get 与 put 各由「哈希定位 + 常数次指针改动」构成，均为 O(1)；空间是哈希表和双向链表各存至多 capacity 个节点，O(capacity)。Python 的 collections.OrderedDict 内置了同一套「哈希 + 双向链表」组合，用 move_to_end 和 popitem 几行就能写完，但面试通常要求手写，考察的正是这两个结构如何咬合。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住分工：哈希表管「查得快」，双向链表管「排新旧」。两者必须同步增删，少改一边就出 bug。
HEAD / TAIL 是不存数据的哨兵，专门用来省掉边界判断。下面每一帧，链表第一行画顺序，第二行画哈希表。
初始化 capacity=2：哨兵 HEAD 和 TAIL 先牵手：一开始链表里只有两个哨兵 HEAD 和 TAIL 手拉手，哈希表是空的。中间两个空槽只是占位，方便后面节点填进来时位置不跳。
put(1,1)：新节点接到 TAIL 前面，成为最新：新 key 一律插到 TAIL 前面，表示它刚被用过。同时哈希表登记 key=1 指向这个节点，下次查它就能一步命中。
put(2,2)：容量正好填满，顺序是 1 → 2：再放 2，容量正好满。链表从左到右是 1、2，所以一旦还要插新键，下一个被淘汰的就是 HEAD 后面最旧的 1。
get(1)：哈希表 O(1) 直接定位到节点 1：get 先查哈希表：cache[1] 一步就拿到节点 1，不用从 HEAD 一个个走过去。命中后还要刷新它的使用顺序，下面三帧慢放摘除与重接。
remove(节点1) 第1刀：左邻 HEAD 越过 1 指向右邻 2：删一个节点要断它左右两根指针。第一刀：让它的左邻 HEAD 的 next 跳过 1、直接指向右邻 2。注意 HEAD 通向 1 的箭头已经断开。
remove(节点1) 第2刀：右邻 2 的 prev 回指 HEAD，1 脱链：第二刀：让右邻 2 的 prev 回指 HEAD。现在节点 1 左右都被绕过去，彻底脱链，但 cache[1] 还指着它，所以数据不会丢，等下原封不动接到尾部。
add_to_tail(节点1) 第3刀：把摘下的 1 缝回 TAIL 前面：把节点 1 接到 TAIL 前面要接四根指针：原尾巴 2 的 next 指向 1、1 的 prev 指向 2、1 的 next 指向 TAIL、TAIL 的 prev 指向 1。get(1) 返回 1，顺序刷新完成。
put(3,3) 第1步：先接到 TAIL 前，临时超容量 [2,1,3]：put 一律先把新节点接到 TAIL 前。链表临时变成 2、1、3 三个真实节点，超过容量 2。所以下一步必须淘汰 HEAD 后面那个最旧的 2。
put(3,3) 第2步：lru = head.next，锁定要淘汰的最旧节点 2：淘汰谁不用找，HEAD 后面第一个就是最旧的 LRU，这里是 2。哨兵让「最旧」永远等于 head.next，O(1) 定位。
淘汰 LRU=2：删 head.next 并从 cache 抹掉 key=2：超容量时 lru = head.next，就是 HEAD 后面最旧的 2。链表用同一套指针手术摘掉它，再 del cache[2]，链表和哈希表必须同步删，少删一个就内存泄漏或数据不一致。
get(2)：哈希表里查不到，直接返回 -1：2 早被淘汰了，cache 里查不到，直接返回 -1。未命中的 get 不碰链表顺序，这就是官方输出里的第一个 -1。
put(4,4) 第1步：接到 TAIL 前，临时超容量 [1,3,4]：和插 3 是同一套：先把 4 接到 TAIL 前，临时变成 1、3、4 三个。超容量就要删 HEAD 后面最旧的 1。
put(4,4) 第2步：lru = head.next，锁定最旧节点 1：同样 lru = head.next，这次最旧的是 1。下一帧把它从链表摘掉、再从哈希表 del 掉。
淘汰 LRU=1：剩下 [3, 4]：删掉 HEAD 后最旧的 1 并 del cache[1]，链表只剩 3、4。1 没了，所以下一步 get(1) 又是 -1。
get(1)：已被淘汰，返回 -1：1 在上一步插 4 时被淘汰了，cache 查不到，返回 -1。这是官方输出里的第二个 -1。
get(3)：哈希表命中节点 3，准备移到最新端：查 3 命中。它现在靠 HEAD 一侧、属于较旧，按 LRU 规则访问后要变最新。下面摘下它、接到 TAIL 前。
get(3)：remove(节点3)，把它从当前位置摘下：和前面 get(1) 同一套手术：先把 3 从链表摘下来，它暂时脱链但被 cache[3] 抓着不会丢。
get(3)：add_to_tail(节点3)，3 成为最新，返回 3：把 3 接到 TAIL 前面，它变成最新、4 变最旧。get(3) 返回 3。
get(4)：哈希表命中节点 4，准备移到最新端：再查 4，命中。它此刻在 HEAD 一侧属较旧，访问后同样要挪到最新端。
get(4)：摘下再接到 TAIL 前，4 重新最新，返回 4：同样摘下再接尾，4 又回到最右端成为最新。官方序列最后两个返回值就是 3 和 4，整套样例演完。
三个高频追问：两个结构的分工、put 已存在 key 的处理、以及 OrderedDict 速成法。
参考代码
class Node: def __init__(self, k=0, v=0): self.k, self.v = k, v self.prev = self.next = Noneclass LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = {} # key -> Node self.head, self.tail = Node(), Node() # 哨兵 self.head.next = self.tail self.tail.prev = self.head def _remove(self, n): # 摘下一个节点 n.prev.next, n.next.prev = n.next, n.prev def _add_to_tail(self, n): # 接到 TAIL 前(最新) n.prev, n.next = self.tail.prev, self.tail self.tail.prev.next = n; self.tail.prev = n def get(self, key): if key not in self.cache: return -1 n = self.cache[key] self._remove(n); self._add_to_tail(n) # 刷新为最新 return n.v def put(self, key, value): if key in self.cache: self._remove(self.cache[key]) n = Node(key, value); self.cache[key] = n self._add_to_tail(n) if len(self.cache) > self.cap: # 超容,淘汰最旧 lru = self.head.next; self._remove(lru) del self.cache[lru.k]复杂度
- 时间：O(1)，get/put 都靠哈希表一步定位节点，链表的摘除与接尾只改固定四根指针，与缓存大小无关
- 空间：O(capacity)，哈希表和双向链表各存最多 capacity 个节点，外加两个哨兵
易错点
面试追问把动画讲成自己的话
追问哈希表和双向链表各自负责什么？
追问put 一个已经存在的 key 会怎样？
追问Python 能不能不手写链表？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
合并 K 个升序链表
LeetCode 23 · 困难 · 沿着 链表 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题