{{Infobox data structure
|name=跳跃列表
|type=列表
|invented_by=W. Pugh
|invented_year=1989
|
|space_avg=O(n)
|space_worst=O(n log n)
|search_avg=O(log n)
|search_worst=O(n)或确定性选择，其中前者更为常见。
描述
；底部的编号框（黄色）表示有序的数据序列。查找从顶部最稀疏的子序列向下进行, 直至需要查找的元素在该层两个相邻的元素中间。]]
跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的「快速通道」，这里在第i层中的元素按某个固定的概率p（通常为\frac{1}{2}或\frac{1}{4}）出现在第i+1 层中。每个元素平均出现在\frac{1}{1 - p}个列表中，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在\log_{1/p} n个列表中出现。
在查找目标元素时，从顶层列表、头元素起步。算法沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。每层链表中预期的查找步数最多为\frac{1}{p}，而层数为\log_{1/p} n，所以查找的总体步数为-\frac{\log_{p} n}{p}，由于p是常数，查找操作总体的时间复杂度为\mathcal{O}(\log n)\,。而通过选择不同p值，就可以在查找代价和存储代价之间取得平衡。
跳跃列表不像平衡树等数据结构那样提供对最坏情况的性能保证：由于用来建造跳跃列表采用随机选取元素进入更高层的方法，在小概率情况下会生成一个不平衡的跳跃列表（最坏情况例如最底层仅有一个元素进入了更高层，此时跳跃列表的查找与普通列表一致）。但是在实际中它通常工作良好，随机化平衡方案也比平衡二叉查找树等数据结构中使用的确定性平衡方案容易实现。跳跃列表在并行计算中也很有用：插入可以在跳跃列表不同的部分并行地进行，而不用对数据结构进行全局的重新平衡。
实现细节
因为跳跃列表中的元素可以在多个列表中，所以每个元素可以有多于一个指针。
跳跃列表的插入和删除的实现与普通的链表操作类似，但高层元素必须在进行多个链表中进行插入或删除。
跳跃列表的最坏时间性能具有一定随机性，但是可以通过时间复杂度为\mathcal{O}(n)的遍历操作（例如在打印列表全部内容时）以无随机的算法重整列表的结构，从而使跳跃列表的实际查找时间复杂度尽量符合理论平均值\mathcal{O}(\log n)。
除了使用无随机算法之外，我们可以以下面的准随机方式地生成每一层：
make all nodes level 1
j ← 1
while the number of nodes at level j > 1 do
for each i'th node at level j do
if i is odd
if i is not the last node at level j
randomly choose whether to promote it to level j+1
else
do not promote
end if
else if i is even and node i-1 was not promoted
promote it to level j+1
end if
repeat
j ← j + 1
repeat
类似无随机版本，准随机重整仅在需要执行一个\mathcal{O}(n)操作（访问每个节点）的时候伴随进行。
历史
跳跃列表由发明。发明者对跳跃列表的评价是：“跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。”
参见
- 布隆过滤器
*
参考文献
外部链接
*[http://nist.gov/dads/HTML/skiplist.html Description] from the Dictionary of Algorithms and Data Structures
*[https://web.archive.org/web/20081018112547/http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_skl.htm skip lists] by Thomas Niemann
*[http://dsqiu.iteye.com/blog/1705530 Skip List（跳躍表）原理詳解與實現 - One thing I know,that is I know nothing.(Socrates Greek) - ITeye技術網站]
评论 (0)