罗罗编程学习记录
本页内容 展开查看

02.3.1.4 双向链表 LRU 与跳表

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.1 链表

02.3.1.4-001 双向链表节点结构是什么?

一句话结论

节点含 val、prev、next 三个字段;前驱后继都可直达,删除已知节点无需找前驱;头尾通常用哑节点简化边界。

概念解释

  • prev:前驱。
  • next:后继。
  • 双向遍历:两个方向均可。

原理流程

  1. 定义 prev/next。
  2. 插入同时维护两条链接。
  3. 删除同时更新两侧。

代码 / 示例

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;顺序保证不断链。

概念解释

  • 先连新节点两侧。
  • 再改旧节点指向。
  • 四条指针缺一不可。

原理流程

  1. 定位前驱 p 与后继 n。
  2. 新节点接 p、n。
  3. 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 选双向链表的关键原因。

概念解释

  • 已知节点:持有引用。
  • 前驱直达。
  • 常数摘除。

原理流程

  1. 取节点 prev、next。
  2. 两侧互连。
  3. 断开被删节点。

代码 / 示例

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),兼顾快速查找与顺序维护。

概念解释

  • 哈希:键 → 节点引用。
  • 链表:访问顺序,头最近、尾最久。
  • 互补:哈希不维护顺序,链表不支持按键查找。

原理流程

  1. 查:哈希定位节点。
  2. 维护顺序:节点移到链表头。
  3. 淘汰:删链表尾,同步删哈希。

代码 / 图示

HashMap: key → DNode
双向链: 头(最近使用) ↔ … ↔ 尾(最久未用)

常见误区

  • 误区:只用链表实现 LRU;正解:查找 O(n),不满足 O(1)。
  • 误区:只用哈希表;正解:哈希无序,无法判断淘汰谁。

追问

  • Q:为什么不用单链表? A:删节点需前驱,单链表 O(n)。
  • Q:链表顺序代表什么? A:最近访问程度,头新尾旧。

02.3.1.4-005 LRU 的淘汰规则是什么?

一句话结论

容量满时淘汰最久未使用的节点,即链表尾部;新访问/新插入节点放到头部;get 与 put 命中都算一次使用,需刷新到头部。

概念解释

  • 最近使用:头部。
  • 最久未用:尾部。
  • 刷新:命中后移头。

原理流程

  1. 访问命中 → 移到头部。
  2. 插入新节点 → 头部,哈希登记。
  3. 超容量 → 删尾部,同步删哈希。

代码 / 图示

容量 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 便于淘汰时删哈希。
  • 辅助方法:移头、删尾、插入头。
  • 哑节点统一边界。

原理流程

  1. 初始化容量、哈希、双向链。
  2. get:查哈希,命中移头返回值。
  3. 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 中链表头尾语义怎么定?

一句话结论

约定头部为最近使用、尾部为最久未用;插入新节点与刷新节点都到头部;淘汰从尾部;方向一旦约定全程一致,避免接反。

概念解释

  • 头:最近。
  • 尾:最久。
  • 移动:摘除后插头。

原理流程

  1. 初始化哑头哑尾。
  2. 新节点插头。
  3. 淘汰删尾前驱。

代码 / 图示

head ↔ 最近 ↔ … ↔ 最久 ↔ tail

常见误区

  • 误区:头尾语义与代码相反;正解:先写清约定再实现。
  • 误区:刷新节点留在原位;正解:命中必须移头。

追问

  • Q:可以头存最久吗? A:可以,方向反过来即可,淘汰取头。
  • Q:哑尾作用? A:尾部删除与插入边界统一。

02.3.1.4-008 借助 LinkedHashMap 怎么实现 LRU?

一句话结论

LinkedHashMap 开启 accessOrder=true 后,访问会把节点移到尾部;重写 removeEldestEntry 在超容量时删除最旧节点;是 Java 内置的快捷实现。

概念解释

  • accessOrder:按访问顺序维护链表。
  • 尾部:最近或最旧按实现口径。
  • 淘汰钩子:插入后判断是否删最旧。

原理流程

  1. 构造器传 accessOrder=true。
  2. get/put 触发顺序调整。
  3. 重写淘汰条件。

代码 / 示例

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:同频率内再按时间排序。

原理流程

  1. LRU:链表顺序即时间。
  2. LFU:计数 + 频率分组。
  3. 淘汰低频,同频淘汰最久。

代码 / 图示

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。
  • 摘除两侧互连。

原理流程

  1. 取 prev、next。
  2. 正向互连。
  3. 反向互连。

代码 / 图示

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)。

概念解释

  • 底层:完整有序链表。
  • 索引层:稀疏上层链。
  • 随机层数:节点晋升概率。

原理流程

  1. 顶层出发向右比较。
  2. 过大则下降一层。
  3. 到底层定位插入/查找位置。

代码 / 图示

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)。

概念解释

  • 层内右移。
  • 过大下降。
  • 底层定位。

原理流程

  1. 顶层出发。
  2. 后继 ≤ 目标右移。
  3. 否则降层。
  4. 底层判等。

代码 / 示例

// 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)。

概念解释

  • 路径:查找经过的各层前驱。
  • 晋升:随机层数。
  • 插入:各层挂接。

原理流程

  1. 查找并记录前驱数组。
  2. 随机生成层数。
  3. 自底向上插入链接。

代码 / 图示

查路径:update[level] = 各层前驱
随机层数 k
新建节点,前 k 层插入

常见误区

  • 误区:所有节点同层;正解:随机晋升形成稀疏索引。
  • 误区:插入后未维护下层指针;正解:跨层 down 链接也要接。

追问

  • Q:层数随机概率? A:通常每层 1/2 概率晋升,参数可调。
  • Q:重复键怎么处理? A:按实现覆盖或挂同键节点。

02.3.1.4-014 跳表删除怎么做?

一句话结论

查找路径记录各层前驱,找到目标后在所有出现层摘除横向链接;节点只存在于其晋升层数内;平均 O(log n)。

概念解释

  • 多层出现:目标节点在若干层都有副本。
  • 各层摘除。
  • 路径前驱定位。

原理流程

  1. 查找记录前驱。
  2. 命中后逐层改 next。
  3. 高层空层可保留或清理。

代码 / 图示

各层前驱 update[l].next = target.next
target 出现在哪层就改哪层

常见误区

  • 误区:只删底层;正解:所有索引层副本都要摘除。
  • 误区:删除后断 down 链;正解:横向链接先改好。

追问

  • Q:高层变空怎么办? A:可降低最高层,不影响正确性。
  • Q:删除节点引用? A:断开链接即可回收。

02.3.1.4-015 跳表层数与概率怎么控制?

一句话结论

新节点以固定概率(如 1/2)向上晋升一层,层数期望有限;最高层数按 n 估算上限;概率决定索引稀疏度与查询效率。

概念解释

  • 晋升概率 p。
  • 期望层数 O(log n)。
  • 上限保护极端情况。

原理流程

  1. 随机掷点决定层数。
  2. 达到概率或上限停止。
  3. 建对应层节点。

代码 / 图示

层数 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):底层全量 + 期望一半索引节点。

概念解释

  • 层间下降对数层。
  • 层内右移有限。
  • 空间期望线性。

原理流程

  1. 层数期望 O(log n)。
  2. 每层访问常数节点。
  3. 合计 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) 有序结构;跳表基于链表与随机层数,实现简单、范围遍历方便;红黑树是平衡树,最坏保证严格,结构维护更复杂。

概念解释

  • 跳表:多层链表,随机平衡。
  • 红黑树:着色旋转,确定平衡。
  • 场景:范围查询、并发实现偏好不同。

原理流程

  1. 比较复杂度口径。
  2. 看实现难度与并发要求。
  3. 选结构。

代码 / 图示

跳表:链表索引,平均 log n
红黑树:平衡二叉,最坏 log n

常见误区

  • 误区:跳表是平衡树;正解:随机化链表结构。
  • 误区:红黑树插入只改指针;正解:需旋转与着色维护。

追问

  • Q:Redis 有序集合用什么? A:跳表 + 哈希表,具体实现以官方版本为准。
  • Q:范围查询谁方便? A:跳表底层有序链表顺序遍历自然。

02.3.1.4-018 双向链表哨兵头尾怎么布置?

一句话结论

哑头 head 与哑尾 tail 互相连接,真实节点夹在中间;插入删除永远有前驱后继,边界条件与中间节点一致。

概念解释

  • 哨兵不存数据。
  • 首尾操作同构。
  • 避免 null 判断分支。

原理流程

  1. 初始化 head.next=tail,tail.prev=head。
  2. 节点插在两哨兵之间。
  3. 真实链为空时两哨兵互连。

代码 / 示例

head ↔ tail(空)
head ↔ n1 ↔ tail(一个节点)

常见误区

  • 误区:只有哑头没有哑尾;正解:尾部删除仍需处理尾节点前驱。
  • 误区:哨兵被当真实节点淘汰;正解:淘汰只动 tail.prev。

追问

  • Q:单哨兵行不行? A:可以,但边界分支更多。
  • Q:哨兵需要入哈希吗? A:不需要。

02.3.1.4-019 LRU/跳表有哪些边界用例?

一句话结论

容量 1、重复 put 同键、get 未命中、插入即淘汰、访问尾部节点、空缓存;跳表:空表、单节点、重复键、边界键值。

概念解释

  • 容量边界:1 与满。
  • 命中/未命中分支。
  • 淘汰触发点。

原理流程

  1. 初始化不同容量。
  2. 构造命中、未命中、更新。
  3. 检查淘汰与链表一致。

代码 / 图示

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)。
  • 跳表:对数层访问。
  • 空间:容量/节点数。

原理流程

  1. 标注哈希与链表各自代价。
  2. 跳表按层数与空间。
  3. 区分平均与最坏口径。

代码 / 图示

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 等,按访问模式选型。