带你一步一步认识跳跃链表

「爱情、让人受尽委屈。」 2022-12-17 08:54 148阅读 0赞

### 一、前言 ###

单链表是一种很常见的数据结构，在其进行查找时，需要从头开始遍历，直到查找到指定的值，因此查找的时间复杂度为O（n）。

双链表在单链表的基础上，为每个结点增加前驱指针(pre)。那么在查找的时候，可以从两头开始遍历。因此双链表的查询效率高于单链表，不过其实在使用率上，单链表的使用率远远高于双链表。具体原因可以先移步我的另外一篇文章[谈谈单链表和双链表][Link 1]

单链表明显是不支持二分查找的，那么有什么骚操作，可以降低其查找的时间复杂度呢？

我们可以观察其他查询性能不错的数据结构，以二叉搜索树为例，也许可以从中学到些什么。

--------------------

### 二、借鉴二叉搜索树查询思路 ###

对于一颗二叉搜索树，左子树上所有结点都不大于它的根节点，右子树上的所有结点都不小于它的根结点。在树平衡的基础上，查询的复杂度可以达到O(logn)。

关于二叉搜索树，在Leetcode中有一些典型的题目。例如：[将有序数组转换为二叉搜索树][Link 2]、[二叉搜索树的最近公共祖先][Link 3]，也许可以帮助你们熟悉它的性质。

我们大可以将平衡二叉搜索树(AVL树)理解为一种分层结构，最底层是一个有序集合，上一层是对下一层的一个索引，上一层结点的个数基本上是下一层结点个数的一半。

因此，我们打算改造单链表，为其增加多级索引，且上一层索引结点个数为下一层索引节点个数的一半。期望改造后的单链表拥有更好的查询性能。

（为什么要改造单链表，我直接将链表转化为AVL树，之后的增加与删除结点直接在AVL树上操作，它不香吗？当然也是可以的，不过转化为AVL树后，增加与删除结点可能会导致树失衡，需要不断的左旋右旋，代码是复杂的。且在进行范围查找时，需要以中序遍历的方式查找不大于最大值的结点，也不省事。这一次改造单链表，我们期望增加与删除操作仅仅只在链表上操作，只需要动几个指针即可。与此同时，我们还期望查询有较低的时间复杂度。）

--------------------

### 三、为单链表增加索引 ###

我们随便从抽屉中拿出一条单链表

![20201023142530842.png][]

将其转为有序链表

![20201023145124737.png][]

将其置为最底层，标记为第L1层，使用一个包含空值的头结点head来串起它

![2020102314533949.png][]

从L1层随机抽出一半节点（当然你也可以每隔一个进行抽取），组成索引层，标记为L2层

![20201023145719705.png][]

在加索引前，当我们查询18这个结点时，我们需要遍历6个结点（3→7→9→12→16→18）；加了L2索引后，我们首先从L2层的头结点开始遍历，首先遍历到3，接着到9，再走一步的时候发现已经到了18，此时只需要遍历3个结点，查询效率提升明显。

我们继续增加L3层索引：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70][]

当最上层的结点只有两个时，就不再增加索引的层数，再加也没有太大的意义了。

以上的这种结构，查询结点并不是一步一步走的，而是跳来跳去的，所以被称为跳跃链表，即跳表。

相比于单链表，跳跃表拥有更高的查询效率。尤其在数据量大的情况下，提升的更为明显。那么它查询结点的时间复杂度又是多少呢？

--------------------

### 四、查询结点的时间复杂度分析 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70][]

因为最终都需要访问到原始链表（L2层的结点9和L1层的结点9其实不一样，只有L1层的结点9才真正指向一个对象），查询结点的时间复杂度=每层最多访问结点\*层高。

当原始链表总结点数为n，h为层高，且上一层索引结点个数为下一层的一半时，索引层LK的节点数=n/2^(k-1)，最顶层Lh的节点数=n/2^(h-1)=2，推得n=2^h，从而层高为logn。

在上图中，访问结点19的路劲无疑是最长的。首先在L3层中访问（9、22），在L2层访问（9、18、22），在L3层中访问（18、19），因此每层最大访问次数为3次。

所以查找的时间复杂度为3logn，去掉常数，即O（logn）。

很明显，这是一种利用空间换取时间的思路，那么跳表使用的额外存储空间是多少呢？

--------------------

### 五、跳表的的额外存储空间 ###

这里我们只计算索引结点数，即L3与L2层的结点总数。

因此，如果原始链表长度为n时，索引结点个数=2+4+8+....+n/2，是一个等比数列，求出和=n-2，即需要n-2个额外索引结点，这些索引结点与真实结点的占用空间比较起来，索引结点占用极少的空间，毕竟不存储真实数据。

所以，在上个图中，跳表的空间复杂度为O（n）。

当然，我们可以每隔3个结点抽一个做索引结点，确实可以减少额外空间，但同时也降低了查找效率，应该根据实际需求调整这个阈值。

--------------------

### 六、跳表插入结点的过程 ###

插入结点的过程和查找结点基本上是同样的流程，沿着索引结点，在最底层找到插入位置后，插入即可。

但是当我们不停地往跳表中插入结点，却不更新索引时，倒数第二层中两个连续的索引结点间就会对应很多真实结点。因此，跳表可能会直接退化为链表，查找的时间复杂度由O（logn）变为O（n）。

那么，怎么去更新索引结点呢？

有一种“抛硬币”的方式，对于已经插入的结点，抛一次硬币，如果为正面，则将此结点增加到L2层索引中。继续抛硬币，如果仍仍然为正面，则将此结点增加到L3层索引中。如果一直为正面，则一直“提拔”，否则立即停止。

例如，下图是插入结点13的过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70 1][]

因此，插入结点的过程为：

1.  找到插入位置，时间复杂度为O（logn）
2.  插入结点，O（1）
3.  利用抛硬币进行提拔，O（logn）

所以，跳表插入结点的时间复杂度也为O（logn）。

跳表的比例是上一层结点数是下一层的一半，因此利用抛硬币的方式，能够在大体上保持比例关系，也能在一定程度上保持索引结点的均匀性。

--------------------

### 七、跳表删除结点的过程 ###

删除结点同样和查找结点类似，查找完成后，删除所有的索引结点与真实数据结点。

例如，下图是删除结点9的示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70 2][]

因此，删除结点的过程为：

1.  找到待删除的元素，包括索引结点与真实数据节点，时间复杂度为O（logn）。
2.  遍历每一层，删除该节点，时间复杂度为O（1）。

在最坏的情况下，每一层都有该结点，因此结点数等于层高，即一共需要删除logn个结点，因此删除节点的时间复杂度为O（logn）。

--------------------

### 八、尾语 ###

Redis的有序集合（sorted set）就是用了跳表这样的结构，不过同时又使用了哈希表。跳表用于执行范围型操作，哈希表用于依据成员查询分值的操作。

当然此处可以参考《redis设计与实现(第二版)》，其中有这样的片段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70][]

[Link 1]: https://blog.csdn.net/qq_33591903/article/details/105118685
[Link 2]: https://blog.csdn.net/qq_33591903/article/details/108772612
[Link 3]: https://blog.csdn.net/qq_33591903/article/details/108824069
[20201023142530842.png]: /images/20221122/f5246b2b4bac4418a0b719099db5d136.png
[20201023145124737.png]: /images/20221122/1593dcff80664e138fbc44f61d74298e.png
[2020102314533949.png]: /images/20221122/e2175867757a4f81b96f06157a714910.png
[20201023145719705.png]: /images/20221122/08f1bc5c0c764be5af064a4959e0bd8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70]: /images/20221122/a1403320e60a46a286ae6b7b3a9dc7c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70 1]: /images/20221122/d4b1cf7d8f5e49e7b6861e2f70686060.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70 2]: /images/20221122/bf283886a65b478596f2fbb2245b4676.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70]: /images/20221122/aa050c0923714baa8f6c17c01c8a3dbc.png