开启掘金成长之旅！这是我参与「掘金日新计划 · 2 月更文挑战」的第 27 天，点击查看活动详情
跳表可以达到和红黑树一样的时间复杂度O(logN)，且实现简单，Redis中的有序集合对象的底层数据结构就使用了跳表。本篇文章将对跳表的实现进行学习。
跳表，即跳跃表（Skip List），是基于并联的链表数据结构，操作效率可以达到O(logN)，对并发友好。跳表的示意图如下所示。
跳表的特点，可以概括如下。
- 跳表是多层（level）链表结构；
- 跳表中的每一层都是一个有序链表，并且按照元素升序（默认）排列；
- 跳表中的元素会在哪一层出现是随机决定的，但是只要元素出现在了第k层，那么k层以下的链表也会出现这个元素；
- 跳表的底层的链表包含所有元素；
- 跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数；
- 跳表中的节点包含两个指针，一个指针指向同层链表的后一节点，一个指针指向下层链表的同元素节点。
以上图中的跳表为例，如果要查找元素71，那么查找流程如下图所示。
从顶层链表的头节点开始查找，查找到元素71的节点时，一共遍历了4个节点，但是如果按照传统链表的方式（即从跳表的底层链表的头节点开始向后查找），那么就需要遍历7个节点，所以跳表以空间换时间，缩短了操作跳表所需要花费的时间。
已知跳表中的节点，需要有指向当前层链表后一节点的指针，和指向下层链表的同元素节点的指针，所以跳表中的节点，定义如下。
上述是跳表中的节点的最简单的定义方式，存储的元素data为整数，节点之间进行比较时直接比较元素data的大小。
跳表初始化时，将每一层链表的头尾节点创建出来并使用集合将头尾节点进行存储，头尾节点的层数随机指定，且头尾节点的层数就代表当前跳表的层数。初始化后，跳表结构如下所示。
跳表初始化的相关代码如下所示。
每一个元素添加到跳表中时，首先需要随机指定这个元素在跳表中的层数，如果随机指定的层数大于了跳表的层数，则在将元素添加到跳表中之前，还需要扩大跳表的层数，而扩大跳表的层数就是将头尾节点的层数扩大。下面给出需要扩大跳表层数的一次添加的过程。
初始状态时，跳表的层数为2，如下图所示。
现在要往跳表中添加元素120，并且随机指定的层数为3，大于了当前跳表的层数2，此时需要先扩大跳表的层数，如下图所示。
将元素120插入到跳表中时，从顶层开始，逐层向下插入，如下图所示。
跳表的添加方法的代码如下所示。
在跳表中搜索一个元素时，需要从顶层开始，逐层向下搜索。搜索时遵循如下规则。
- 目标值大于当前节点的后一节点值时，继续在本层链表上向后搜索；
- 目标值大于当前节点值，小于当前节点的后一节点值时，向下移动一层，从下层链表的同节点位置向后搜索；
- 目标值等于当前节点值，搜索结束。
下图是一个搜索过程的示意图。
跳表的搜索的代码如下所示。
当在跳表中需要删除某一个元素时，则需要将这个元素在所有层的节点都删除，具体的删除规则如下所示。
- 首先按照跳表的搜索的方式，搜索待删除节点，如果能够搜索到，此时搜索到的待删除节点位于该节点层数的最高层；
- 从待删除节点的最高层往下，将每一层的待删除节点都删除掉，删除方式就是让待删除节点的前一节点直接指向待删除节点的后一节点。
下图是一个删除过程的示意图。
跳表的删除的代码如下所示。
跳表完整代码如下所示。
跳表的时间复杂度与AVL树和红黑树相同，可以达到O(logN)，但是AVL树要维持高度的平衡，红黑树要维持高度的近似平衡，这都会导致插入或者删除节点时的一些时间开销，所以跳表相较于AVL树和红黑树来说，省去了维持高度的平衡的时间开销，但是相应的也付出了更多的空间来存储多个层的节点，所以跳表是用空间换时间的数据结构。
开启掘金成长之旅！这是我参与「掘金日新计划 · 2 月更文挑战」的第 27 天，点击查看活动详情
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/6130.html