对于一个单链表即便在链表中存储的数据是有序的情况下，我们要想在其中查找某个数据，也只能从头到尾遍历链表，如下如图所示单链表：

如上的链表的查找数据的时间复杂度O(n)，如果我们想要提高其查找效率，可以考虑在链表上建索引，这就是我们今天要聊的跳跃表。

1、认识跳跃表

跳跃表是由表头、表尾、层级和跳跃表的节点组成，各个部分的作用如下所示：

（a）表头：负责维护跳跃表的节点指针

（b）跳跃表的节点：保存元素值以及多少层

（c）层级：保存指向其他的元素的指针，我们都是先从高层级开始访问，然后随着元素的范围值的缩小而慢慢降低层级

（4）表尾：全部是null组成的，表示跳跃表的末尾

跳跃表实质是在一个链表的基础上增加多层索引，这个层数是随机的，每一层索引都是原始链表的子集，并且索引元素的间隔逐层增大，这样就可以实现在一个高层级向下层级进行快速的搜索数据。

2、跳跃表如何查询数据

在上图的跳跃表中我们想要查询元素9，查询的过程如下所示：

（a）我们最开始是从最高层L4层开始查询，L4层第一个节点值为1，此时1是小于9的，则取当前点的下一个节点值，也即是12，但是12是大于9，这时以节点1为基础降层到L3层查找（查找值处于当前节点的值和当前节点下一节点的值之间时，降层查询）。

（b）L3层的第一个节点是1，此时1小于9，那么取其L3层的下一节点，也就是元素4，但是4小于9，同理在继续比较下一个节点，经过在L3上一轮比较后发现9位于L3层元素8和12之间，这时候以L3层元素8为基础继续降到L2层查询。

（c）L2层的比较的第一个节点是8，此时8是小于9的，再去L2层的下一个节点值，也就是10，此时元素10是大于9的，我们继续以元素8为基础降到L1层查找。

（d）L1层的第一个查询节点8，取其下一节点元素与9比较，发现正是我们要找的元素，那么直接结束并且返回结果。

正常情况下跳跃表的查询是从最高层逐层向下查询，每次查询都是从当前的层中找到小于目标元素的最大值，然后再跳转到下一层继续查找，如果最后找到了目标元素就返回元素所在的节点，否则返回空。

跳跃表的平均时间复杂度为O(logN)，链表在节点数量少的情况下，性能的提升不明显，当节点在1万以上的时候性能提升将会非常明显。

总结：

（1）跳跃表基于单链表加索引的方式实现，它是以空间换时间的方式提升了查找速度，在处理大量数据时具有很高的效率。

（2）跳跃表的实现相对简单，相比于平衡树来讲，跳跃表不需要进行复杂的旋转和平衡操作。

（3）跳跃表支持有序操作，如获取最小值、最大值或进行范围查找。

（4）跳跃表的空间复杂度是O(N)，每个元素都需要存储在跳跃表中，这可能会占用较多的内存。