3.1 简介
在了解跳跃表之前，我们先了解一下有序链表。有序链表是所有元素以递增或递减方式有序排列的数据结构，其中每个节点都有指向下个节点的next指针，最后一个节点的next指针指向NULL。递增有序链表举例如图3-1所示。
图3-1 递增有序链表举例
如图3-1所示的有序链表，如果要查询值为51的元素，需要从第一个元素开始依次向后查找、比较才可以找到，查找顺序为1→11→21→31→41→51，共6次比较，时间复杂度为O(N)。有序链表的插入和删除操作都需要先找到合适的位置再修改next指针，修改操作基本不消耗时间，所以插入、删除、修改有序链表的耗时主要在查找元素上。
如果我们将有序链表中的部分节点分层，每一层都是一个有序链表。在查找时优先从最高层开始向后查找，当到达某节点时，如果next节点值大于要查找的值或next指针指向NULL，则从当前节点下降一层继续向后查找，这样是否可以提升查找效率呢？
分层有序链表如图3-2所示，我们再次查找值为51的节点，查找步骤如下。
图3-2 分层有序链表
1）从第2层开始，1节点比51节点小，向后比较。
2）21节点比51节点小，继续向后比较。第2层21节点的next指针指向NULL，所以从21节点开始需要下降一层到第1层继续向后比较。
3）第1层中，21节点的next节点为41节点，41节点比51节点小，继续向后比较。第1层41节点的next节点为61节点，比要查找的51节点大，所以从41节点开始下降一层到第0层继续向后比较。
4）在第0层，51节点为要查询的节点，节点被找到。
采用图3-2所示的数据结构后，总共查找4次就可以找到51节点，比有序链表少2次。当数据量大时，优势会更明显。
综上所述，通过将有序集合的部分节点分层，由最上层开始依次向后查找，如果本层的next节点大于要查找的值或next节点为NULL，则从本节点开始，降低一层继续向后查找，依次类推，如果找到则返回节点；否则返回NULL。采用该原理查找节点，在节点数量比较多时，可以跳过一些节点，查询效率大大提升，这就是跳跃表的基本思想。
跳跃表的实现过程如图3-3所示。
图3-3 跳跃表的实现过程
从图3-3中我们可以看出跳跃表有如下性质。
1）跳跃表由很多层构成。
2）跳跃表有一个头（header）节点，头节点中有一个64层的结构，每层的结构包含指向本层的下个节点的指针，指向本层下个节点中间所跨越的节点个数为本层的跨度（span）。
3）除头节点外，层数最多的节点的层高为跳跃表的高度（level），图3-3中跳跃表的高度为3。
4）每层都是一个有序链表，数据递增。
5）除header节点外，一个元素在上层有序链表中出现，则它一定会在下层有序链表中出现。
6）跳跃表每层最后一个节点指向NULL，表示本层有序链表的结束。
7）跳跃表拥有一个tail指针，指向跳跃表最后一个节点。
8）最底层的有序链表包含所有节点，最底层的节点个数为跳跃表的长度（length）（不包括头节点），图3-3中跳跃表的长度为7。
9）每个节点包含一个后退指针，头节点和第一个节点指向NULL；其他节点指向最底层的前一个节点。
跳跃表每个节点维护了多个指向其他节点的指针，所以在跳跃表进行查找、插入、删除操作时可以跳过一些节点，快速找到操作需要的节点。归根结底，跳跃表是以牺牲空间的形式来达到快速查找的目的。跳跃表与平衡树相比，实现方式更简单，只要熟悉有序链表，就可以轻松地掌握跳跃表。