数据结构:跳表

一、跳表是什么

跳表（Skip List）是一种支持快速查找、插入和删除的有序数据结构。

它的底层仍然是链表，但额外建立了多层“索引链表”，让查找时可以跳过大量节点。

可以把它理解成：

普通链表：

逐个节点寻找

跳表：

先大步跳跃，接近目标后再小步查找思想类似二分查找，但更适合动态插入和删除

二、为什么普通链表查找很慢

假设有一个有序链表：

1 → 3 → 5 → 7 → 9 → 11 → 13 → 15

查找13时，只能从头开始逐个比较：

1 → 3 → 5 → 7 → 9 → 11 → 13

时间复杂度是：

O(n)

数组可以使用二分查找达到O(log n)，但数组中间插入或删除元素通常需要移动大量数据，复杂度为O(n)。

跳表希望同时获得：

查找：O(log n) 插入：O(log n) 删除：O(log n)

这些是期望时间复杂度。

三、跳表的基本结构

在原始链表上建立多级索引：

Level 3: HEAD ----------------------→ 13 Level 2: HEAD --------→ 7 ----------→ 13 Level 1: HEAD → 3 ----→ 7 → 9 -----→ 13 Level 0: HEAD → 1 → 3 → 5 → 7 → 9 → 11 → 13 → 15

其中：

Level 0保存全部节点

越高层的节点越少

高层用于快速定位

底层用于找到精确位置

每个节点可能同时存在于多层中

例如节点7的逻辑结构可能是：

7.forward[0] → Level 0 的下一个节点 7.forward[1] → Level 1 的下一个节点 7.forward[2] → Level 2 的下一个节点

实际上它通常是一个节点持有多个前向指针，并不是复制出多个节点。

四、查找过程

以上面的跳表为例，查找11。

第一步：从最高层开始

HEAD → 13

因为13 > 11，不能前进，于是下降一层。

第二步：在较低层前进

HEAD → 7

7 < 11，移动到7。

下一个节点是13，超过目标，于是再次下降。

第三步：继续逼近目标

在 Level 1：

7 → 9

9 < 11，移动到9。下一步会超过目标，所以继续下降。

第四步：在底层精确查找

9 → 11

找到目标。

核心规则是：

如果右侧节点小于目标：向右移动 如果右侧节点大于等于目标：下降一层

伪代码：

current = head 从最高层向下遍历: while current.forward[level] != null and current.forward[level].value < target: current = current.forward[level] current = current.forward[0] 如果 current.value == target: 返回 current 否则: 返回不存在

这个过程很像在二维结构中不断“向右、向下”移动。

五、插入过程

假设要插入8。

5.1 找到每一层的前驱节点

查找插入位置时，记录每一层最后一个小于8的节点：

update[2] = 7 update[1] = 7 update[0] = 7

update数组表示新节点在每一层应该插到哪个节点后面

5.2 随机生成节点高度

跳表通常通过随机算法决定新节点拥有多少层

以概率p = 1/2为例：

level = 0 只要抛硬币成功: level += 1

可能产生：

50% 的节点：只有 Level 0 25% 的节点：拥有 Level 0～1 12.5% 的节点：拥有 Level 0～2 6.25% 的节点：拥有 Level 0～3

因此，层数越高，节点越少。

5.3 修改指针

假设8被随机为两层节点：

new.forward[0] = update[0].forward[0] update[0].forward[0] = new new.forward[1] = update[1].forward[1] update[1].forward[1] = new

插入后：

Level 1: ... → 7 → 8 → 9 ... Level 0: ... → 7 → 8 → 9 ...

重要的是：寻找插入位置需要O(log n)，修改指针本身只需要O(level)

六、删除过程

删除节点时，同样先找到目标节点在每一层的前驱：

update[level]

然后逐层检查：

如果 update[level].forward[level] 是目标节点: update[level].forward[level] = target.forward[level]

例如：

删除前：7 → 8 → 9 删除后：7 ─────→ 9

如果删除后最高层已经没有任何数据节点，可以降低跳表当前的最大层数。

七、为什么随机层数能提高效率

如果人为固定每隔两个节点建立一层索引：

Level 2: 1 -------→ 9 Level 1: 1 → 5 ---→ 9 → 13 Level 0: 1 → 3 → 5 → 7 → 9 → 11 → 13

查找很快，但插入节点后可能需要重新调整大量索引。

跳表不维护严格的索引间隔，而是随机决定节点高度。虽然局部结构不完全均匀，但从概率上看：

第 0 层约有 n 个节点 第 1 层约有 n × p 个节点 第 2 层约有 n × p² 个节点 第 k 层约有 n × pᵏ 个节点

当p = 1/2时：

n, n/2, n/4, n/8, ...

这与二分查找不断缩小范围的效果类似，所以期望查找复杂度为：

O(log n)

八、时间和空间复杂度

这里k是范围查询返回的元素数量

最坏情况可能是所有节点都只有最底层，跳表退化成普通链表。不过在合理随机化和最大层数限制下，这种情况概率很低

当p = 1/2时，每个节点的期望指针数量为：

1 + 1/2 + 1/4 + 1/8 + ... = 2

所以总空间仍然是O(n)。

九、跳表和其他结构的对比

相比哈希表

跳表支持：

查找大于等于 x 的第一个元素 查询 [left, right] 范围内的元素 按顺序遍历

普通哈希表通常不能高效完成这些操作。

相比平衡树

跳表的优点：

不需要旋转操作

插入、删除逻辑相对直观

范围遍历自然

某些并发场景更容易设计

平衡树的优点：

最坏时间复杂度有严格的O(log n)保证

通常不依赖随机数

每个节点的结构更加固定