我们知道，不借助额外空间的情况下，在链表中查找一个值，需要按照顺序一个个查找，时间复杂度为 O(N)，其中 N 为链表长度。

当链表长度很大的时候， 这种时间是很难接受的。 一种常见的的优化方式是建立哈希表，将所有节点都放到哈希表中，以空间换时间的方式减少时间复杂度，这种做法时间复杂度为 O(1)，但是空间复杂度为 O(N)。

为了防止链表中出现重复节点带来的问题，我们需要序列化节点，再建立哈希表，这种空间占用会更高，虽然只是系数级别的增加，但是这种开销也是不小的 。更重要的是，哈希表不能解决查找极值的问题，其仅适合根据 key 来获取内容。

为了解决上面的问题，跳表（skip list）应运而生。

如下图所示，我们从链表中每两个元素抽出来，加一级索引，一级索引指向了原始链表，即：通过一级索引 7 的 down 指针可以找到原始链表的 7 。那怎么查找 10 呢？

注意这个算法要求链表是有序的。

我们可以：

通过现在一级跳表中搜索到 7，发现下一个 18 大于 10 ，也就是说我们要找的 10 在这两者之间。

通过 down 指针回到原始链表，通过原始链表的 next 指针我们找到了 10。

这个例子看不出性能提升。但是如果元素继续增大， 继续增加索引的层数，建立二级，三级……索引，使得链表能够实现二分查找，从而获得更好的效率。但是相应地，我们需要付出额外空间的代价。

理解了上面的点，你可以形象地将跳表想象为玩游戏的存档。

一个游戏有 10 关。如果我想要玩第 5 关的某一个地方，那么我可以直接从第五关开始，这样要比从第一关开始快。我们甚至可以在每一关同时设置很多的存档。这样我如果想玩第 5 关的某一个地方，也可以不用从第 5 关的开头开始，而是直接选择离你想玩的地方更近的存档，这就相当于跳表的二级索引。

跳表的时间复杂度和空间复杂度不是很好分析。由于时间复杂度 = 索引的高度 * 平均每层索引遍历元素的个数，而高度大概为 logn，并且每层遍历的元素是常数，因此时间复杂度为 logn，和二分查找的空间复杂度是一样的。

在单链表中，一旦定好要插入的位置，时间复杂度是很低的为O(1)，但是，为了保持原始链表中数据的有序性，通常需要遍历链表找到需要插入的位置，这个查找操作会比较耗时。但是在跳表中，时间复杂度为O(logn)。

空间复杂度就等同于索引节点的个数，以每两个节点建立一个索引为例，大概是 n/2 + n/4 + n/8 + … + 8 + 4 + 2 ，因此空间复杂度是 O(n)。当然你如果每三个建立一个索引节点的话，空间会更省，但是复杂度不变。

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。跳表的空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。跳表可以用来实现堆（区别于基于链表的实现，另一种是基于数组的实现 - 二叉堆）。

当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。

作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。

而跳表是通过随机函数来维护前面提到的“平衡性”。当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

如果一个节点存在K个向前的指针的话，那么该节点就是K层的节点。跳表的最大层数为节点中所以节点中最大的层数。

#define SKIP_LIST_MALLOC(size)   rt_malloc(size);
#define SKIP_LIST_CALLOC(n,size) rt_calloc(n,size);
#define SKIP_LIST_FREE(p)        rt_free(p);
 
struct skip_list_node
{
	/*key是唯一的*/
	int key;       
	/*存储的内容*/
	int value;     
	/*当前节点最大层数*/
	int max_level; 
	/*柔性数组,根据该节点层数的不同指向大小不同的数组
	 *next[0]表示该节点的第一层下一节点的索引地址
	 *next[1]表示该节点的第二层下一节点的索引地址
	 *next[n]表示该节点的第n层下一节点的索引地址
	 */
	struct skip_list_node *next[];
};
 
struct skip_list
{
	int level; /*跳表的索引层数*/
	int num;   /*节点数目*/
	struct skip_list_node *head;
};
 
extern struct skip_list* skip_list_creat(int max_level);
extern int skip_list_insert (struct skip_list *list, int key, int value);
extern int skip_list_delete (struct skip_list *list, int key);
extern int skip_list_modify (struct skip_list *list, int key, int value);
extern int skip_list_search (struct skip_list *list, int key, int *value);
extern int skip_list_destroy(struct skip_list *list);

ref:

https://blog.csdn.net/m0_37845735/article/details/103691814

https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/heap#tiao-biao

－End－