跳表（Skip List） 跳表是一种基于并联链表的数据结构，它通过添加多级索引来实现快速查找、插入和删除操作，时间复杂度为O(log n)。跳表可以看作是二叉搜索树的一种替代方案，实现相对简单，且性能稳定。 一、跳表的基本概念 想象一个有序链表，查找时需要从头到尾遍历，时间复杂度为O(n)。跳表的核心思想是"空间换时间"：通过建立多级索引（即额外的有序链表），每级索引跳过部分节点，从而加速查找。 二、跳表的结构 节点结构 ：每个节点包含值（key）和多个指向后续节点的指针（通常称为"forward"指针数组） 层级（Level） ：跳表有多个层级，最底层（第0层）是包含所有元素的有序链表 索引层 ：从下往上，每层索引都是下层索引的子集，节点间隔逐渐增大 三、查找操作过程 以在跳表中查找值"23"为例（假设跳表包含1, 3, 7, 12, 19, 23, 26, 30, 35, 39）： 从最高层索引开始 ：假设最高层是第3层 向右遍历 ：在当前层向右移动，比较节点值与目标值 如果下一个节点值 ≤ 目标值，继续向右 如果下一个节点值 > 目标值或为NULL，则下降一层 逐层下降 ：重复步骤2，直到最底层（第0层） 最终检查 ：在最底层找到的节点值如果等于目标值，则查找成功 具体查找路径示例： 第3层：从头节点开始，发现下一个节点值(19) < 23，向右移动 第3层：下一个节点值(35) > 23，下降至第2层 第2层：从19开始，下一个节点值(35) > 23，下降至第1层 第1层：从19开始，下一个节点值(26) > 23，下降至第0层 第0层：从19开始，下一个节点值(23) = 23，查找成功 四、插入操作过程 插入操作需要两个步骤：查找插入位置和确定新节点的层级。 查找前驱节点 ： 从最高层开始，记录每层中最后一个小于插入值的节点（前驱节点） 这些前驱节点指针需要更新，以指向新节点 随机确定层级 ： 使用随机方法（如抛硬币）决定新节点的层级 从第1层开始，每次有50%概率增加一层，直到达到最大层级限制 这种随机性保证了跳表的平衡性 更新指针 ： 从第0层到新节点的最高层，更新前驱节点的指针 新节点的指针指向原来前驱节点的后续节点 五、删除操作过程 删除操作与插入类似： 查找目标节点 ：同时记录每层中最后一个小于目标值的节点 更新指针 ：将各层中指向目标节点的指针，更新为指向目标节点的后续节点 释放内存 ：如果目标节点被找到，释放其占用的内存 六、复杂度分析 空间复杂度 ：O(n)，索引节点数约为n/2 + n/4 + n/8 + ... ≈ n 时间复杂度 ： 查找：O(log n) 插入：O(log n)（包含查找时间） 删除：O(log n)（包含查找时间） 七、跳表的优势 实现相对红黑树等平衡二叉树更简单 支持范围查询（找到起始点后，底层链表顺序遍历） 并发环境下更容易实现线程安全 跳表被广泛应用于各种系统中，如Redis的有序集合、LevelDB的MemTable等都采用跳表作为底层数据结构。