跳表基础
一句话总结
跳表（Skip List）通过空间换时间思想，在原始链表上构建多层索引，将查询、插入、删除操作的时间复杂度从 $O(N)$ 优化到 $O(\log N)$，实现难度远低于自平衡二叉搜索树。
核心原理
问题背景
普通单链表中，通过索引查询对应节点需要从头结点开始逐个遍历，时间复杂度为 $O(N)$。即使拿到目标节点后的增删改操作只需 $O(1)$，查找的瓶颈导致整体效率低下。
跳表设计
跳表在原始链表基础上增加多层索引：
- 每向上一层，索引节点数量减少一半，索引间隔变为 2 倍
- 索引高度为 $\log N$（$N$ 为链表元素个数）
示例结构：
indexLevel 0,,,,,,,--8,--10
indexLevel 0,,,--4,,,--8,--10
indexLevel 0,--2,--4,--6,--8,--10
indexLevel 0--1--2--3--4--5--6--7--8--9--10
nodeLevel a->b->c->d->e->f->g->h->i->j->k
查询过程（以查索引 7 为例）
- 最高层：区间
[0, 8]包含 7，从节点 0 进入下一层 - 第二层：从节点 0 开始，
[0, 4]不包含 7，移动到节点 4；[4, 8]包含 7，进入下一层 - 第三层：从节点 4 开始，
[4, 6]不包含 7，移动到节点 6；[6, 8]包含 7，进入下一层 - 第四层：从节点 6 开始，
[6, 7]包含 7，找到目标节点h
复杂度分析：经过 $\log N$ 层，每层移动不超过 2 次，总时间复杂度 $O(\log N)$。
时间复杂度对比
| 操作 | 普通链表 | 跳表 |
|---|---|---|
| 查询（按索引） | $O(N)$ | $O(\log N)$ |
| 插入 | $O(N)$（查找+$O(1)$插入） | $O(\log N)$ |
| 删除 | $O(N)$（查找+$O(1)$删除） | $O(\log N)$ |
| 修改 | $O(N)$ | $O(\log N)$ |
关键补充
- 动态索引调整：插入和删除时需动态调整索引层节点，保证每层索引区间尽可能二分，否则时间复杂度会退化
- 通用场景：跳表不仅可按索引查找，还可用于有序键值对的存储和查找，应用场景与二叉搜索树类似
- 实现复杂度：跳表的代码实现比自平衡二叉搜索树（如红黑树）简单很多
与二叉搜索树对比
| 维度 | 跳表 | 自平衡二叉搜索树 |
|---|---|---|
| 时间复杂度 | $O(\log N)$ 增删查 | $O(\log N)$ 增删查 |
| 实现难度 | 简单 | 复杂（需处理旋转等操作） |
| 适用场景 | 有序键值存储 | 有序键值存储 |
| 并发友好 | 较好（无需全局平衡） | 较差 |
相关概念
相关实体
- labuladong：算法学习平台作者