https://zh.wikipedia.org/wiki/%E8%B7%B3%E8%B7%83%E5%88%97%E8%A1%A8
概述
- 使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是
O(log n)，优于数组的O(n)复杂度 - 一个多层次的链表。与前一层（下面一层）链表元素的数量相比，每一层链表中的元素的数量更少。每一层是有序的
构造
跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速通道”，在第i层（下面的层）中的每个元素按某个固定的概率p（通常为1/2或1/4）出现在第i+1层（上面的层）中，直到当前层元素个数为1
每个元素平均出现在
1/1-p个列表中，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在log{1/p}n个列表中出现。
查找
在查找目标元素时，从顶层列表、头元素起步。
算法沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。
如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。
举例见插入
每层链表中预期的查找步数最多为
1/p，而层数为log{1/p}n，所以查找的总体步数为log{p}n/p，由于p是常数，查找操作总体的时间复杂度为O(logn)。而通过选择不同p值，就可以在查找代价和存储代价之间获取平衡。
插入
和查找类似
插入80
80<=30?
80<=30?no
80<=50?
80<=50?no
走到nil所以向下走
80<=70?
80<=70?no
80<=90?
80<=90?yes, insert
