02.3.1.4 双向链表 LRU 与跳表
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.1 链表
02.3.1.4-001 双向链表节点结构是什么?
一句话结论
节点含 val、prev、next 三个字段;前驱后继都可直达,删除已知节点无需找前驱;头尾通常用哑节点简化边界。
概念解释
- prev:前驱。
- next:后继。
- 双向遍历:两个方向均可。
原理流程
- 定义 prev/next。
- 插入同时维护两条链接。
- 删除同时更新两侧。
代码 / 示例
class DNode {
int key, val;
DNode prev, next;
DNode(int k, int v) { key = k; val = v; }
}
常见误区
- 误区:只改 next 不改 prev;正解:双向链两条链接都要维护。
- 误区:头尾不设哨兵;正解:哑头哑尾省去空判断。
追问
- Q:双向链表随机访问? A:仍 O(n)。
- Q:节点为什么存 key? A:LRU 淘汰时要从哈希表删对应键。
02.3.1.4-002 双向链表中间插入怎么改指针?
一句话结论
在节点 prev 与 next 之间插入 x:x.prev=prev、x.next=next、prev.next=x、next.prev=x;顺序保证不断链。
概念解释
- 先连新节点两侧。
- 再改旧节点指向。
- 四条指针缺一不可。
原理流程
- 定位前驱 p 与后继 n。
- 新节点接 p、n。
- p.next、n.prev 指向新节点。
代码 / 图示
p ↔ n
插入 x:
x.prev = p; x.next = n;
p.next = x; n.prev = x;
常见误区
- 误区:先改 p.next 丢失 n;正解:先把新节点两侧接好。
- 误区:忘记更新 n.prev;正解:反向链接也要维护。
追问
- Q:头/尾插入? A:哑节点下与中间插入同构。
- Q:插入排序用双向链表? A:可行,前驱回溯找插入点。
02.3.1.4-003 双向链表删除已知节点为什么 O(1)?
一句话结论
节点自带 prev,直接令 prev.next=next、next.prev=prev 即可摘除,无需遍历找前驱;这是 LRU 选双向链表的关键原因。
概念解释
- 已知节点:持有引用。
- 前驱直达。
- 常数摘除。
原理流程
- 取节点 prev、next。
- 两侧互连。
- 断开被删节点。
代码 / 示例
void remove(DNode x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
常见误区
- 误区:单链表也能 O(1) 删已知节点;正解:单链表无前驱,需值覆盖或 O(n) 找前驱。
- 误区:删除后节点引用未清;正解:断开链接即可,GC 回收。
追问
- Q:删头节点? A:哑节点下 prev 为哑头,规则统一。
- Q:删除后哈希表怎么办? A:同步移除对应键。
02.3.1.4-004 为什么 LRU 选择哈希表 + 双向链表?
一句话结论
哈希表按键 O(1) 定位节点;双向链表 O(1) 摘除与移到头部;两者结合使 get/put 都 O(1),兼顾快速查找与顺序维护。
概念解释
- 哈希:键 → 节点引用。
- 链表:访问顺序,头最近、尾最久。
- 互补:哈希不维护顺序,链表不支持按键查找。
原理流程
- 查:哈希定位节点。
- 维护顺序:节点移到链表头。
- 淘汰:删链表尾,同步删哈希。
代码 / 图示
HashMap: key → DNode
双向链: 头(最近使用) ↔ … ↔ 尾(最久未用)
常见误区
- 误区:只用链表实现 LRU;正解:查找 O(n),不满足 O(1)。
- 误区:只用哈希表;正解:哈希无序,无法判断淘汰谁。
追问
- Q:为什么不用单链表? A:删节点需前驱,单链表 O(n)。
- Q:链表顺序代表什么? A:最近访问程度,头新尾旧。
02.3.1.4-005 LRU 的淘汰规则是什么?
一句话结论
容量满时淘汰最久未使用的节点,即链表尾部;新访问/新插入节点放到头部;get 与 put 命中都算一次使用,需刷新到头部。
概念解释
- 最近使用:头部。
- 最久未用:尾部。
- 刷新:命中后移头。
原理流程
- 访问命中 → 移到头部。
- 插入新节点 → 头部,哈希登记。
- 超容量 → 删尾部,同步删哈希。
代码 / 图示
容量 2:
put(1) → [1]
put(2) → [2,1]
get(1) → [1,2]
put(3) → 淘汰 2 → [3,1]
常见误区
- 误区:put 更新值不算使用;正解:更新也刷新到头部。
- 误区:淘汰头部;正解:头部最近,淘汰尾部。
追问
- Q:访问顺序如何定义? A:get 与 put 命中都更新。
- Q:容量为 0? A:按题目口径,不可存节点。
02.3.1.4-006 手写 LRU 缓存(LC 146)怎么组织?
一句话结论
内部维护哈希表与双向链表(带哑头哑尾);实现 get(命中移头)、put(命中更新移头 / 未命中插头,超容量删尾);均摊 O(1)。
概念解释
- 节点存 key 便于淘汰时删哈希。
- 辅助方法:移头、删尾、插入头。
- 哑节点统一边界。
原理流程
- 初始化容量、哈希、双向链。
- get:查哈希,命中移头返回值。
- put:命中更新移头;未命中建节点插头登记,超容量删尾。
代码 / 示例
class LRUCache {
private static class Node {
int key, val; Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
private final int cap;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0), tail = new Node(0, 0);
LRUCache(int cap) {
this.cap = cap;
head.next = tail; tail.prev = head;
}
public int get(int key) {
Node n = map.get(key);
if (n == null) return -1;
moveToHead(n);
return n.val;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) {
n.val = value; moveToHead(n);
} else {
Node fresh = new Node(key, value);
map.put(key, fresh); addToHead(fresh);
if (map.size() > cap) {
Node removed = tail.prev;
remove(removed);
map.remove(removed.key);
}
}
}
private void addToHead(Node n) {
n.prev = head; n.next = head.next;
head.next.prev = n; head.next = n;
}
private void remove(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void moveToHead(Node n) {
remove(n); addToHead(n);
}
}
常见误区
- 误区:节点不存 key;正解:删尾时要拿 key 删哈希。
- 误区:淘汰时只删链表不删哈希;正解:两处同步。
追问
- Q:get 未命中返回什么? A:按题目常见 -1。
- Q:线程安全吗? A:基础版非线程安全,并发需加锁或并发结构。
02.3.1.4-007 LRU 中链表头尾语义怎么定?
一句话结论
约定头部为最近使用、尾部为最久未用;插入新节点与刷新节点都到头部;淘汰从尾部;方向一旦约定全程一致,避免接反。
概念解释
- 头:最近。
- 尾:最久。
- 移动:摘除后插头。
原理流程
- 初始化哑头哑尾。
- 新节点插头。
- 淘汰删尾前驱。
代码 / 图示
head ↔ 最近 ↔ … ↔ 最久 ↔ tail
常见误区
- 误区:头尾语义与代码相反;正解:先写清约定再实现。
- 误区:刷新节点留在原位;正解:命中必须移头。
追问
- Q:可以头存最久吗? A:可以,方向反过来即可,淘汰取头。
- Q:哑尾作用? A:尾部删除与插入边界统一。
02.3.1.4-008 借助 LinkedHashMap 怎么实现 LRU?
一句话结论
LinkedHashMap 开启 accessOrder=true 后,访问会把节点移到尾部;重写 removeEldestEntry 在超容量时删除最旧节点;是 Java 内置的快捷实现。
概念解释
- accessOrder:按访问顺序维护链表。
- 尾部:最近或最旧按实现口径。
- 淘汰钩子:插入后判断是否删最旧。
原理流程
- 构造器传 accessOrder=true。
- get/put 触发顺序调整。
- 重写淘汰条件。
代码 / 示例
class LRUCache extends LinkedHashMap<Integer, Integer> {
private final int cap;
LRUCache(int cap) {
super(cap, 0.75f, true);
this.cap = cap;
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > cap;
}
}
常见误区
- 误区:默认插入顺序也会按访问移动;正解:必须 accessOrder=true。
- 误区:不重写淘汰钩子;正解:超容量不会自动删最旧。
追问
- Q:LinkedHashMap 底层结构? A:哈希表 + 双向链表。
- Q:面试要求手写还是可继承? A:通常要求手写哈希 + 双向链表,继承版作为对照。
02.3.1.4-009 LRU 与 LFU 有什么区别?
一句话结论
LRU 按最近使用时间淘汰;LFU 按使用频率淘汰,频率相同再按时间;LFU 需维护频率桶与最小频率,结构更复杂。
概念解释
- LRU:时间维度。
- LFU:频率维度。
- LFU:同频率内再按时间排序。
原理流程
- LRU:链表顺序即时间。
- LFU:计数 + 频率分组。
- 淘汰低频,同频淘汰最久。
代码 / 图示
LRU:淘汰最久未用
LFU:淘汰使用次数最少;并列看时间
常见误区
- 误区:LRU 就是按频率;正解:LRU 只看时间,不看次数。
- 误区:LFU 实现与 LRU 相同;正解:需频率桶与频次维护。
追问
- Q:LFU 怎么 O(1)? A:哈希 + 频率双向链表 + 最小频率记录。
- Q:各自缺点? A:LRU 偶发批量访问可能冲掉热点;LFU 冷门数据长期滞留。
02.3.1.4-010 双向链表删除节点的两条链接为什么都要改?
一句话结论
只改 next 会让前驱链断开反向引用,只改 prev 同理;必须 prev.next=next 与 next.prev=prev 同时更新,链表才双向一致。
概念解释
- 正向链:prev → next。
- 反向链:next → prev。
- 摘除两侧互连。
原理流程
- 取 prev、next。
- 正向互连。
- 反向互连。
代码 / 图示
p ↔ x ↔ n
p.next = n; n.prev = p;
常见误区
- 误区:单向改完即可;正解:反向链残留指向被删节点。
- 误区:被删节点 prev/next 未清;正解:逻辑断开即可,引用清不清不影响结构。
追问
- Q:删除头尾节点? A:哑节点下同样两条链接。
- Q:删除后遍历会漏吗? A:两侧互连后不会经过被删节点。
02.3.1.4-011 跳表是什么结构?
一句话结论
跳表是有序链表 + 多层索引:上层链表跳过下层部分节点,查询时从顶层向下二分式缩小范围;查询、插入、删除平均 O(log n),空间 O(n)。
概念解释
- 底层:完整有序链表。
- 索引层:稀疏上层链。
- 随机层数:节点晋升概率。
原理流程
- 顶层出发向右比较。
- 过大则下降一层。
- 到底层定位插入/查找位置。
代码 / 图示
L2: head ──────────→ 30
L1: head ──→ 10 ──→ 30 ──→ 50
L0: head →5→10→20→30→40→50
常见误区
- 误区:跳表是数组;正解:基于链表加索引层。
- 误区:跳表保证最坏 O(log n);正解:平均对数,层数随机。
追问
- Q:跳表用于什么? A:有序集合、键值排序结构,如部分缓存与数据库。
- Q:跳表需要比较键吗? A:需要,节点按键有序。
02.3.1.4-012 跳表查询流程怎么走?
一句话结论
从最高层起点,当前节点后继键小于目标则右移,否则下降一层;到底层后比较命中或未命中;每层向右不回退,平均 O(log n)。
概念解释
- 层内右移。
- 过大下降。
- 底层定位。
原理流程
- 顶层出发。
- 后继 ≤ 目标右移。
- 否则降层。
- 底层判等。
代码 / 示例
// cur 从顶层头节点开始
while (cur != null) {
while (cur.next != null && cur.next.key < key) cur = cur.next;
if (cur.next != null && cur.next.key == key) return cur.next;
cur = cur.down;
}
常见误区
- 误区:每层从头重新走;正解:上层位置延续到下层。
- 误区:下降后向右回退;正解:层内单调右移。
追问
- Q:查询比较次数? A:层数 log n,每层节点数有限。
- Q:未命中怎么判断? A:底层后继键大于目标或到尾。
02.3.1.4-013 跳表插入怎么做?
一句话结论
先查找到插入路径,记录各层前驱;随机决定节点层数,在各层插入节点并维护横向链接;平均 O(log n)。
概念解释
- 路径:查找经过的各层前驱。
- 晋升:随机层数。
- 插入:各层挂接。
原理流程
- 查找并记录前驱数组。
- 随机生成层数。
- 自底向上插入链接。
代码 / 图示
查路径:update[level] = 各层前驱
随机层数 k
新建节点,前 k 层插入
常见误区
- 误区:所有节点同层;正解:随机晋升形成稀疏索引。
- 误区:插入后未维护下层指针;正解:跨层 down 链接也要接。
追问
- Q:层数随机概率? A:通常每层 1/2 概率晋升,参数可调。
- Q:重复键怎么处理? A:按实现覆盖或挂同键节点。
02.3.1.4-014 跳表删除怎么做?
一句话结论
查找路径记录各层前驱,找到目标后在所有出现层摘除横向链接;节点只存在于其晋升层数内;平均 O(log n)。
概念解释
- 多层出现:目标节点在若干层都有副本。
- 各层摘除。
- 路径前驱定位。
原理流程
- 查找记录前驱。
- 命中后逐层改 next。
- 高层空层可保留或清理。
代码 / 图示
各层前驱 update[l].next = target.next
target 出现在哪层就改哪层
常见误区
- 误区:只删底层;正解:所有索引层副本都要摘除。
- 误区:删除后断 down 链;正解:横向链接先改好。
追问
- Q:高层变空怎么办? A:可降低最高层,不影响正确性。
- Q:删除节点引用? A:断开链接即可回收。
02.3.1.4-015 跳表层数与概率怎么控制?
一句话结论
新节点以固定概率(如 1/2)向上晋升一层,层数期望有限;最高层数按 n 估算上限;概率决定索引稀疏度与查询效率。
概念解释
- 晋升概率 p。
- 期望层数 O(log n)。
- 上限保护极端情况。
原理流程
- 随机掷点决定层数。
- 达到概率或上限停止。
- 建对应层节点。
代码 / 图示
层数 1 起步
每次以 p 概率 +1 层
层数上限 ≈ log_(1/p) n
常见误区
- 误区:层数固定为 log n;正解:随机生成,期望对数。
- 误区:概率越低越好;正解:过低索引稀疏,查询退化。
追问
- Q:p=1/2 空间代价? A:期望总节点 O(n),每层约半。
- Q:如何保证最坏可接受? A:层数上限与随机种子控制。
02.3.1.4-016 跳表复杂度怎么推?
一句话结论
平均查询/插入/删除 O(log n):每层前进常数步,层数 O(log n);空间 O(n):底层全量 + 期望一半索引节点。
概念解释
- 层间下降对数层。
- 层内右移有限。
- 空间期望线性。
原理流程
- 层数期望 O(log n)。
- 每层访问常数节点。
- 合计 O(log n);空间 Σ 层节点 O(n)。
代码 / 图示
时间:O(log n) 平均
空间:O(n)
常见误区
- 误区:跳表最坏保证 O(log n);正解:随机结构,平均口径。
- 误区:索引层额外 O(n log n);正解:几何递减,期望 O(n)。
追问
- Q:与二分查找比? A:跳表支持动态插入删除,二分依赖有序数组。
- Q:跳表为什么不用平衡树? A:实现与并发友好,链表局部修改。
02.3.1.4-017 跳表与红黑树怎么对比?
一句话结论
两者都 O(log n) 有序结构;跳表基于链表与随机层数,实现简单、范围遍历方便;红黑树是平衡树,最坏保证严格,结构维护更复杂。
概念解释
- 跳表:多层链表,随机平衡。
- 红黑树:着色旋转,确定平衡。
- 场景:范围查询、并发实现偏好不同。
原理流程
- 比较复杂度口径。
- 看实现难度与并发要求。
- 选结构。
代码 / 图示
跳表:链表索引,平均 log n
红黑树:平衡二叉,最坏 log n
常见误区
- 误区:跳表是平衡树;正解:随机化链表结构。
- 误区:红黑树插入只改指针;正解:需旋转与着色维护。
追问
- Q:Redis 有序集合用什么? A:跳表 + 哈希表,具体实现以官方版本为准。
- Q:范围查询谁方便? A:跳表底层有序链表顺序遍历自然。
02.3.1.4-018 双向链表哨兵头尾怎么布置?
一句话结论
哑头 head 与哑尾 tail 互相连接,真实节点夹在中间;插入删除永远有前驱后继,边界条件与中间节点一致。
概念解释
- 哨兵不存数据。
- 首尾操作同构。
- 避免 null 判断分支。
原理流程
- 初始化 head.next=tail,tail.prev=head。
- 节点插在两哨兵之间。
- 真实链为空时两哨兵互连。
代码 / 示例
head ↔ tail(空)
head ↔ n1 ↔ tail(一个节点)
常见误区
- 误区:只有哑头没有哑尾;正解:尾部删除仍需处理尾节点前驱。
- 误区:哨兵被当真实节点淘汰;正解:淘汰只动 tail.prev。
追问
- Q:单哨兵行不行? A:可以,但边界分支更多。
- Q:哨兵需要入哈希吗? A:不需要。
02.3.1.4-019 LRU/跳表有哪些边界用例?
一句话结论
容量 1、重复 put 同键、get 未命中、插入即淘汰、访问尾部节点、空缓存;跳表:空表、单节点、重复键、边界键值。
概念解释
- 容量边界:1 与满。
- 命中/未命中分支。
- 淘汰触发点。
原理流程
- 初始化不同容量。
- 构造命中、未命中、更新。
- 检查淘汰与链表一致。
代码 / 图示
cap=1 / cap=2
重复 put 同键
get 不存在
插新即淘汰
常见误区
- 误区:超容量才淘汰;正解:插入后 size>cap 即淘汰最旧。
- 误区:未命中 get 改变顺序;正解:不存在节点不进入链表。
追问
- Q:同键 put 更新值会增加节点吗? A:不增加,只更新值并移头。
- Q:跳表查最小/最大? A:底层头后/尾前节点。
02.3.1.4-020 本知识域复杂度怎么汇报?
一句话结论
双向链表摘除已知节点 O(1);LRU get/put 均摊 O(1),空间 O(capacity);跳表平均 O(log n) 增删查,空间 O(n)。
概念解释
- LRU:哈希 O(1) + 链表 O(1)。
- 跳表:对数层访问。
- 空间:容量/节点数。
原理流程
- 标注哈希与链表各自代价。
- 跳表按层数与空间。
- 区分平均与最坏口径。
代码 / 图示
LRU:get/put O(1),空间 O(cap)
双向链表删已知节点:O(1)
跳表:平均 O(log n),空间 O(n)
常见误区
- 误区:LRU 是 O(log n);正解:哈希 + 双向链均摊 O(1)。
- 误区:跳表最坏 O(log n) 可保证;正解:随机化平均口径。
追问
- Q:LFU 复杂度? A:理想实现 O(1),结构比 LRU 复杂。
- Q:缓存淘汰还有哪些策略? A:FIFO、LFU、ARC 等,按访问模式选型。