关于跳表的一些知识可以参考这篇文章,最好是先看完这篇文章再看详细的思路->代码的复现步骤:
Redis内部数据结构详解(6)——skiplist
关于跳表的插入、删除基本操作其实也就是链表的插入和删除，所以如果不熟悉的话还得先回顾链表的插入以及删除是怎样的，可以参考：
【数据结构基础笔记】【链表】
相关代码以及其他语言的写法或者其他思路可以参考：
1206. 设计跳表
代码参考链接：
https://leetcode-cn.com/problems/design-skiplist/solution/can-kao-redisshi-xian-by-bakezq/
https://www.iteye.com/blog/kenby-
跳表采用随机法决定链表中哪些节点应该增加向前指针以及在该节点中应增加多少个指针。
跳表结构的头节点需要有足够的指针域，以满足可能构造最大级数的需求，而尾节点不需要指针域。
跳表在原有的有序链表上增加了多级索引，通过索引来实现快速查找。
1、首先在最高级索引上查找最后一个小于当前查找元素的位置
2、调到次高级索引继续查找，直到调到最底层为止，如果查找元素存在的话，此刻已经十分接近要查找的元素的位置了。
你需要了解的内容：
1、指定head为左上角
2、初始化prevs数组(转折点数组)
3、查找只有 right 和 down 两个方向
4、maxlevel是当前跳表的最大层数，并非一开始人为限制的MAXLEVEL。maxlevel可能会随着插入新的结点时的产生随机层数而更新。
但是总是有：maxlevel <= MAXLEVEL
以下面的图为例：从中你应该能清楚了解到prevs数组的含义。
从从顶层向下遍历到最底层：
根据这样的思路可以写出这样的代码：
插入步骤：
1、通过查找子函数获取最底层链表中<=num值的最近的节点，赋给prevs
2、随机产生该节点的层数
首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
节点最大的层数不允许超过一个最大值，记为MaxLevel。
randomLevel()的伪码中包含两个参数，一个是p，一个是MaxLevel。在Redis的skiplist实现中，这两个参数的取值为：
3、更新当前的跳表中的最大层数maxlevel，在新生成的层里，将prevs[]初始化为head结点：
如下图：当我们插入的数为2，随机出来的层数为5，那么新的一层中小于这个num的节点一定是头结点。
4、生成一个新的结点，值为num，层数为level
5、对于每一层来说，由于新插入了一个结点，于是原本的索引关系就得发生改变：
将原本prevs的在本层的后继作为cur在本层的后继，再将cur作为prevs的后继：
以第0层为例
由于这里的prevs[i]都是head结点，所以可以比较方便的看出关系，整理之后就是下面的样子：
代码：
1、通过查找子函数获取最底层链表中<= num值的最近的节点，赋给prevs
2、特殊情况处理：如果prevs在原链表中不存在(是指向空的节点) 或者 最近的节点的值不等于num（没有值为num的节点），返回错误
3、否则，说明存在值为nums的结点，且为prevs[0]->level[0]
4、接下来就是要通过修改节点之间的后继关系将值为num的前继后继节点相连。
prevs的后继为需要删除的del节点，则将del的后继连接到prevs后面，作为新的prevs的后继
5、将空间释放
6、删除掉一个结点可能需要更新当前最大层数（如果删除的结点是之前层数最多的话）
判断方法：如果头结点maxlevel-1层的结点没有后继，说明本层已经没有其他节点了
将成员数据和函数进行了私有公有的划分：
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/14567.html