加载中...
列表（List）是最基本的数据结构之一。与数组（Array）类似，它们都是相同元素的集合。然后列表的查找效率并不理想，与树形结构（在前面提到了相关的数据结构如和等查找效率都很高，但是需要旋转或者变色的等操作保持自平衡。）相比，列表虽然简单，但是对元素的查找需要比对列表中的每个元素，查找速度较慢。为了兼顾列表的简单易用，并提高查找效率，William Pugh在1990年发表了一篇论文（），提出了跳跃列表（Skip List）数据结构，以空间换时间的方式，构造了一个层次的列表为数据建立索引，以提高列表的查找效率。
欢迎关注 DataLearner 官方微信，获得最新 AI 技术推送
具体来说，Skip List是允许在有序的元素序列内快速搜索（量化）的数据结构。 通过维持子序列的链接层次结构，可以实现快速搜索，每个连续的子序列跳过比前一个更少的元素（参见下图）。 搜索从最稀疏的子序列（就是从最上层）开始，直到找到两个连续的元素，一个较小，一个大于或等于搜索的元素。 通过链接层次结构，这两个元素链接到下一个最稀疏子序列的元素，其中继续搜索，直到最后我们在完整序列中搜索。 跳过的元素可以概率地或确定性地选择，前者更常见。
如下图所示，是一个常见的跳跃列表实现情况：
Skip List是按层构建的。底层是普通有序链表。每个较高层充当下面列表的“快速通道”，其中图层$i$中的元素以一定的固定概率$p$出现在图层$i + 1$中，（p的两个常用值是1/2和1/4）。平均而言，每个元素都出现在1/(1-p)的列表中，以及最高的元素（通常是特殊的元素）所有列表中的跳过列表前面的元素。Skip List包含$\log_{1/p}n$个列表。注意，这里是说的构造的结果，不是构造过程。跳跃列表的构造过程见后面的插入操作。
搜索目标元素从顶部列表中的head元素开始，并水平前进，直到当前元素大于或等于目标。如果当前元素等于目标，则已找到它。如果当前元素大于目标，或者搜索到达链接列表的末尾，则在返回上一个元素并垂直下降到下一个下一个列表后重复该过程。每个链接列表中的预期步数最多为1/p，可以通过从目标向后追踪搜索路径来查看直到到达下一个更高列表中出现的元素或到达当前列表的开头。因此，搜索的总预期成本为：
\frac{\log_{1/p}n}{p}
p是一个常量。通过选择p的不同值，可以将搜索成本与存储成本进行交易。
我们通过旋转可以发现跳跃列表与二叉查找树很相似，上图旋转后如下：
总结一下，跳跃列表的特性如下：
在前面的叙述中，我们把跳跃列表旋转之后就可以使得跳跃列表像一个二叉搜索树，因此，跳跃列表的搜索和二叉查找树的搜索类似。一般最上面的层
以上图搜索30为例。
可以这么理解，上层的节点是下层节点的索引，从最上面节点开始搜索，找到待查节点所属的区域，然后向下层移动，一直到最底层即可。
之前也说过，跳跃列表是一个层次结构的有序列表。最底层（第0层）包含了所有的元素，如果某个元素在某一层出现，那么比该层低的所有层中都应当包含这个元素。每个节点要有一个指针，指向下一层包含相同值的节点。所以插入操作要主要是决定是待插入元素在第几层，然后把元素添加到这一层中，并在下面的层里也做相应的操作，并将这些节点连接起来。
一般来说最开始要确定一个Skip List的最大层数，在插入一个节点的时候，首先要以一定的概率确定这个节点在哪一层。确定好之后，也要把这个节点在所有的下层加上，并更新指针即可。删除也是类似的操作。