在计算机科学领域,跳跃链表是一种数据结构,允许快速查询一个有序连续元素的数据链表。快速查询是通过维护一个多层次的链表,且每一层链表中的元素是前一层链表元素的子集(见右边的示意图)。一开始时,算法在最稀疏的层次进行搜索,直至需要查找的元素在该层两个相邻的元素中间。这时,算法将跳转到下一个层次,重复刚才的搜索,直到找到需要查找的元素为止。被挑过的元素可能被随机性地选择或确定性地选择,其中前者更为常见。[1]
跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”,这里在第i层中的元素按某个固定的概率p(通常为1/2或1/4)出现在第i+1层中。平均起来,每个元素都在 个列表中出现,而最高层的元素(通常是在跳跃列表前端的一个特殊的头元素)在 (即基于1/p的n的对数)个列表中出现。
要查找一个目标元素,起步于头元素和顶层列表,并沿着每个链表搜索,直到到达小于或着等于目标的最后一个元素。通过跟踪起自目标直到到达在更高列表中出现的元素的反向查找路径,在每个链表中预期的步数显而易见最多为1/p。所以查找的总体代价是 ,当p是常数时是 。通过选择不同p值,就可以在查找代价和存储代价之间作出权衡。
插入和删除的实现非常像相应的链表操作,除了"高层"元素必须在多个链表中插入或删除之外。
跳跃列表不像某些传统平衡树数据结构那样提供绝对的最坏情况性能保证,因为用来建造跳跃列表的扔硬币方法总有可能(尽管概率很小)生成一个糟糕的不平衡结构。但是在实际中它工作的很好,随机化平衡方案比在平衡二叉查找树中用的确定性平衡方案容易实现。跳跃列表在并行计算中也很有用,这里的插入可以在跳跃列表不同的部分并行的进行,而不用全局的数据结构重新平衡。
我们可以以下面的方式准随机地生成每一层:[2]
近似于无随机版本,准随机仅在需要运行一个{\displaystyle {\mathcal {O}}(n)}操作(访问每个节点)的时候进行。
跳跃列表由William Pugh发明。他在Communications of the ACMJune 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees,在其中详细描述了他的工作。
引用发明者的话:
跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。