什么是跳表
跳表是一种有序的数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问的目的。
核心思想
image.png
这是一个单向链表，我们要查询链表中某个元素的话，需要遍历整条链，所以链表查询的时间复杂度为O(N)。
O(N)，这个时间复杂度比较高，查询效率较低，于是就有人试图优化。
其中，William Pugh 受到二分查找的启发，就思考能不能通过二分法来跳过部分节点，直接锁定目标。于是，他做出了这样的假设。
如果是说链表是排序的，并且节点中还存储了指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
image.png
同理，如果节点中还存储指向前面第四个节点的指针的话，那么查找下一个节点时，仅仅需要遍历N/4个节点。
image.png
这就是跳表的核心思想，通过一个“空间来换取时间”的算法，通过在每个节点中增加了向前的指针，从而提升查找的效率，显然，它的查找时间复杂度为O(logN)。
其实，这只是理想状态下的跳表。
在这种理想状态下，每次插入或者删除节点时，新节点前面的所有节点都要重新关联，这显然不是我们想要的结果。
现实中的跳表是这样的。
image.png
跳表的性质
(1) 由很多层结构组成
(2) 每一层都是一个有序的链表
(3) 最底层(Level 1)的链表包含所有元素
(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
跳表的结构
跳跃表的节点有三部分构成：key值，value值，以及指向前向节点的指针数组，指针数组的大小由该节点的层数决定。
image.png
所以，节点的数据类型可以定义为
typedef struct nodeStructure {
keyType key; // key值
valueType value; // value值
node forward[1]; // 向前指针数组，根据该节点层数的不同指向不同大小的数组
};
定义跳表数据类型：
typedef struct listStructure {
int level; // 跳表的层数
struct nodeStructure * header; // 指向header节点的指针
} * list;
跳表的操作
查询
对于下图这个链表结构，假设我们要查询值为56的节点，我们需要比较10次。
image.png
使用跳表优化过的查询算法，我们只需要比较3次。
image.png
插入
同链表类似。
删除
同链表类似。
性能对比
我们对跳跃表、平衡树等进行比较，如下图()所示：
图片来自网络，未找到原出处
网友评论