线性数据结构之跳跃列表（Skip List）详解及其Java实现

一、跳跃列表（Skip List）简介

列表（List）是最基本的数据结构之一。与数组（Array）类似，它们都是相同元素的集合。然后列表的查找效率并不理想，与树形结构（在前面提到了平衡二叉树相关的数据结构如AVL树和红黑树等查找效率都很高，但是需要旋转或者变色的等操作保持自平衡。）相比，列表虽然简单，但是对元素的查找需要比对列表中的每个元素，查找速度较慢。为了兼顾列表的简单易用，并提高查找效率，William Pugh在1990年发表了一篇论文（Skip lists: a probabilistic alternative to balanced trees），提出了跳跃列表（Skip List）数据结构，以空间换时间的方式，构造了一个层次的列表为数据建立索引，以提高列表的查找效率。

具体来说，Skip List是允许在有序的元素序列内快速搜索（量化）的数据结构。 通过维持子序列的链接层次结构，可以实现快速搜索，每个连续的子序列跳过比前一个更少的元素（参见下图）。 搜索从最稀疏的子序列（就是从最上层）开始，直到找到两个连续的元素，一个较小，一个大于或等于搜索的元素。 通过链接层次结构，这两个元素链接到下一个最稀疏子序列的元素，其中继续搜索，直到最后我们在完整序列中搜索。 跳过的元素可以概率地或确定性地选择，前者更常见。

如下图所示，是一个常见的跳跃列表实现情况：