上篇：《跳表上篇：单链表的逆袭 —— 多层索引如何告别 O (n)》

跳表Skip List是一种随机化平衡的有序数据结构本质是对有序单链表的多层索引升级。它通过 “空间换时间” 的思路将单链表 O (n) 的查找效率提升至平均 O (log n)同时保留链表插入、删除的灵活性是 Redis 有序集合、LevelDB 等工业级项目的核心底层结构。一、为什么需要跳表单链表的天生瓶颈有序单链表是最基础的线性结构但存在一个致命缺陷查找元素必须从头节点逐个遍历时间复杂度 O (n)即使数据完全有序也无法像数组那样执行二分查找想要提升查找效率核心思路是给链表加「索引」每隔几个节点提取一个代表节点形成上层稀疏链表查找时先在高层快速定位大致区间再下沉到低层精准查找。1 层索引查找步数约 n/22 层索引查找步数约 n/4每多一层索引查找范围就减半当索引层数达到 log₂n 时查找效率就接近二分查找跳表就是将这个 “多层索引” 思想系统化、工程化的产物。二、跳表的结构定义跳表是由多层有序链表叠加而成的结构遵循以下规则第 0 层底层完整的有序单链表包含所有数据节点高层索引第 k 层是第 k-1 层的子集节点数量按固定比例递减有序性每一层链表都严格保持升序 / 降序排列节点结构每个节点包含多个指针分别指向其在不同层级的后继节点头节点一个虚拟哨兵节点拥有最高层数作为所有层级的起点节点的抽象结构每个节点有两个核心部分数据域存储节点的键值用于排序指针数组forward[]forward[i]表示该节点在第 i 层的下一个节点节点的层数 指针数组的长度。一个层数为 k 的节点会同时出现在第 0 层到第 k-1 层的所有链表里。三、核心操作 1查找查找规则从当前最高层的头节点出发遵循「能右移就右移不能右移就下沉」的原则若当前节点的下一个节点值小于目标值直接向后跳跃若当前节点的下一个节点值大于等于目标值停止当前层遍历下沉到下一层重复上述过程直到下沉至第 0 层第 0 层的下一个节点若等于目标值则查找成功否则失败直观理解这个过程等价于二分查找每一层都能排除掉大量不可能的节点逐层缩小搜索范围最终在底层精准定位。示例演示在包含 1~7 的跳表中查找 5从最高层出发跳过 1、3发现下一个节点 7 5下沉中间层继续遍历跳过 3发现下一个节点 7 5下沉底层从 3 向后走一步找到 5查找结束四、核心操作 2插入插入操作比查找多两个步骤记录前驱节点、生成随机层数。完整步骤定位前驱节点执行类似查找的流程在每一层都记录下最后一个小于目标值的节点即插入位置的前一个节点生成随机层数通过概率算法随机生成新节点的层数保证整体结构的概率平衡更新指针从第 0 层到最高层依次将新节点插入到对应层的前驱节点之后类似单链表插入逻辑更新跳表最大层数如果新节点层数超过当前跳表最高层更新全局最大层数关键细节插入的核心难点是「如何保证插入后跳表依然平衡」。 平衡树AVL、红黑树通过旋转、变色来强制维持平衡逻辑复杂而跳表采用随机化策略每个新节点的层数由概率决定不需要调整已有节点从统计意义上保证结构均衡。五、核心操作 3删除删除操作与插入互为逆过程定位目标节点同样记录每一层的前驱节点校验节点存在下沉到第 0 层后确认目标节点存在逐层断链从第 0 层到最高层依次让前驱节点跳过目标节点直接指向目标节点的后继更新最大层数如果删除的是最高层唯一的节点需要逐层降低跳表的最大层数注意点删除只需要修改各层指针不需要移动数据天然保留了链表删除的高效性同时因为多层索引的存在定位目标节点的速度远快于普通单链表。六、上篇小结跳表的核心逻辑可以一句话概括给有序链表加多层稀疏索引用随机概率替代强制旋转实现概率平衡下的 O (log n) 操作。到这里我们已经建立了跳表的完整直观认知下篇会深入它最精髓的随机化平衡原理、严格的复杂度证明、完整 C 工程实现以及 Redis 等工业场景的落地细节。谢谢