对于一个有序数组，如果要查找其中的一个数，我们可以使用二分查找(Binary Search)算法，将它的时间复杂度降低为O(logn).那查找一个有序链表，有没有办法将其时间复杂度也降低为O(logn)呢？
跳表(skip list),全称为跳跃链表，实质上就是一种可以进行二分查找的有序链表，它允许快速查询、插入和删除有序链表。
跳表使用的前提是链表有序，就像二分查找也要求有序数组
怎么理解跳表比如我们有一个原始有序链表，如下图所示。
要查找其中值为20的元素，之前都是采取按顺序进行遍历的方法，但这样做时间复杂度就变成了O(n).怎样才能提高效率呢？我们可以通过对链表建立一级索引，查找的时候先遍历索引，通过索引找到原始层继续遍历。索引如下图所示
那么查找20的过程就变成了先使用索引遍历 2 -> 7 -> 12 -> 20，然后顺着索引链表的结点向下找到原始链表的结点20.之前需要遍历7次，现在需要遍历5次。在数据量小的时候跳表性能优化并不明显，但当有序链表包含大量数据时，结点的访问次数大致会减少一半。
现在我们添加两层索引，基于第一层的索引再添加一层，如下图所示
要查找20，先在第二层索引上遍历 2 -> 12 ,然后向下转到第一层索引遍历 12 - > 20，最后向下找到原始链表的结点20.
这个例子中，原始有序链表的结点数量很少，当结点数量很多时，可以抽出更多的索引层级，每一层索引结点的数量都是低层索引的一半。
跳表复杂度分析 时间复杂度算法的执行效率可以通过时间复杂度来衡量，跳表的时间复杂度是多少呢？我们来分析一下。
前面我们每两个结点抽一个结点作为上一级索引的结点，那么假设原始链表的长度为n，第一层索引的结点个数为n/2,第二层索引的个数为n/4,第k级的索引结点个数就是n/(2k)。假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到 n/(2h)=2，从而求得 h=log2n-1。如果包含原始链表这一层，整个跳表的高度就是 log2n。我们在跳表中查询某个数据的时候，如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。
m的值怎么计算呢？在上面的例子中，每一层最多只需要遍历三个元素，因此m=3，根据时间复杂度的计算规则，高阶的常数项也可以省略，因此跳表中查询任意数据的时间复杂度就是O(logn)
空间复杂度每两个结点中抽一个结点作为上级索引，很明显，它的空间复杂度为O(n).