本文共 7173 字，大约阅读时间需要 23 分钟。
文章目录
数据结构 - 跳跃链表
作者今年大三，正在准备明年的春招，文章中有写得不对的，希望大家及时指出文章中的错误的地方，大家一起努力!
一，为什么会有跳表？
以下图片均来自：
对于一个普通的单链表，如图：
如果我们想要查找55号节点，那么我们需要从头结点依次遍历到尾节点，那么对于单链表的节点查询来说，如果链表节点数量很大的情况下，那么需要遍历的节点数量也会越多，时间复杂度是O(N)
这样我们就会想，有什么方法会让我们访问链表某一节点的速度加快？
如果我们尝试另一条访问路径，比如
这样我们访问55号节点就会相比之前访问的节点数减少了，头结点 ->2 -> 21 -> 37 -> 55
如果我们还想更快呢？
根据上图的思路，我们也许还可以开辟一条路出来
此时访问55号节点就只要经过头结点，21号节点，55号节点，访问速度大大加快
可以想象，当链表节点达到很多的时候，比如：
使用跳表的查询方式比普通链表的遍历要快的多
这种思想其实和二分查找法的思想很相似
所以，这种查询的时间复杂度可以达到O(logN)
对比平衡树？
AVL平衡树的插入和删除，查询操作都可以在O(logN)的复杂度完成，但是AVL平衡树的插入和删除需要通过左旋或者右旋去调整树的节点，相对跳表来说是要复杂的。跳表也是支持动态插入和删除的一种动态的数据结构，其查找，插入和删除的时间复杂度也能做到和AVL平衡树媲美的O(logN)，是一种以空间换时间的做法。跳表在redis中是sort set的底层实现
二，跳表结构
跳表的最底层可以是双向链表也可以单链表，看情况而定，但是索引层一般是单链表
节点类
class ListNode: def __init__(self, data: Optional[int] = None): self._data = data # 数值域 self._forwards = [] # 向前指针
跳表：
class SkipList: # 最大层数 _MAX_LEVEL = 16 def __init__(self): self._level_count = 1 self._head = ListNode() self._head._forwards = [None] * type(self)._MAX_LEVEL
三，跳表元素查询
其实上面已经对跳表元素查询做了一个简单的介绍了，接下来讲具体讲讲
接下来用到的图片来自：https://blog.csdn.net/pcwl1206/article/details/83512600#commentBox
如果我需要查询13号节点
此时，我们只需要在level2（第二级索引层）遍历1,7,13便找到了13号节点
又如果我想要查找11号节点
我会先遍历level2（第二级索引层）发现13号节点比我要查找的11号节点大，那么我会退回7号节点，从7号节点往下一层，到达level1（第一级索引层）从7号节点往前遍历，遍历9，又发现13号节点比我要查找的11号节点大，此时从9号节点往下一层，到达level0（最底层）从9开始往前遍历，遍历10，发先10前边是13，没有我们所需要的节点11
代码实现：
# 查询跳表节点 def find(self, value: int) -> Optional[ListNode]: p = self._head # 从头结点开始查找 for i in range(self._level_count - 1, -1, -1): # 从最高层开始，一层一层查找 while p._forwards[i] and p._forwards[i]._data < value: # 每一层中向前查找 p = p._forwards[i] # 现在找到的是最接近这个value的节点，可以这么说：node.data <= value return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None
四，跳表元素插入
对于纯粹的单链表，需要遍历每个结点，来找到插入的位置。但是对于跳表来说，查找的时间复杂度为O(logn)，所以这里查找某个数据应该插入的位置的时间复杂度也是O(logn)，如下图所示：
节点插入不单单是最后底层的链表插入节点而已，还需要调整层级level
# 插入节点 def insert(self, value: int): # 生成随机level level = self._random_level() # 如果原level小于生成的随机level则更新level为刚生成的level if self._level_count < level: self._level_count = level # 构造新增节点 new_node = ListNode(value) new_node._forwards = [None] * level # forwards指向每层第一个节点 update = [self._head] * level # update数组保存每层插入节点的前驱节点 p = self._head # 寻找插入位置 for i in range(level - 1, -1, -1): while p._forwards[i] and p._forwards[i]._data < value: p = p._forwards[i] update[i] = p # update数组保存每层插入节点的前驱节点 # 插入节点，调整节点间指向关系 for i in range(level): # 相当于 newNode.next = pre.next new_node._forwards[i] = update[i]._forwards[i] # 相当于 pre.next = newNode update[i]._forwards[i] = new_node
随机函数：
最理想的情况就是，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：50%的概率返回 1， 25%的概率返回 2，12.5%的概率返回 3 …
# 随机函数，在redis中，概率是取到1/4 def _random_level(self, p: float = 0.5) -> int: level = 1 while random.random() < p and level < type(self)._MAX_LEVEL: level += 1 return level
五，跳表元素删除
在跳表中删除某个结点时，如果这个结点在索引中也出现了，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到删除结点的前驱结点，然后再通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点（双向链表除外）。因此跳表的删除操作时间复杂度即为O(logn)。
# 删除跳表节点 def delete(self, value): update = [None] * self._level_count p = self._head for i in range(self._level_count - 1, -1, -1): while p._forwards[i] and p._forwards[i]._data < value: p = p._forwards[i] update[i] = p # 要删除节点的前驱节点 # 判断是否符合删除条件 if p._forwards[0] and p._forwards[0]._data == value: for i in range(self._level_count - 1, -1, -1): if update[i]._forwards[i] and update[i]._forwards[i]._data == value: update[i]._forwards[i] = update[i]._forwards[i]._forwards[i] # 相当于pre.next = pre.next.next
六，完整代码
from typing import Optionalimport randomclass ListNode: def __init__(self, data: Optional[int] = None): self._data = data # 数值域 self._forwards = [] # 向前指针class SkipList: # 最大层数 _MAX_LEVEL = 16 def __init__(self): self._level_count = 1 self._head = ListNode() self._head._forwards = [None] * type(self)._MAX_LEVEL # 查询跳表节点 def find(self, value: int) -> Optional[ListNode]: p = self._head # 从头结点开始查找 for i in range(self._level_count - 1, -1, -1): # 从最高层开始，一层一层查找 while p._forwards[i] and p._forwards[i]._data < value: # 每一层中向前查找 p = p._forwards[i] # 现在找到的是最接近这个value的节点，可以这么说：node.data <= value return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None # 插入跳表节点 def insert(self, value: int): # 生成随机level level = self._random_level() # 如果原level小于生成的随机level则更新level为刚生成的level if self._level_count < level: self._level_count = level # 构造新增节点 new_node = ListNode(value) new_node._forwards = [None] * level # forwards指向每层第一个节点 update = [self._head] * level # update数组保存每层插入节点的前驱节点 p = self._head # 寻找插入位置 for i in range(level - 1, -1, -1): while p._forwards[i] and p._forwards[i]._data < value: p = p._forwards[i] update[i] = p # update[i]是要插入位置的前驱节点 # 插入节点，调整节点间指向关系 for i in range(level): # 相当于 newNode.next = pre.next new_node._forwards[i] = update[i]._forwards[i] # 相当于 pre.next = newNode update[i]._forwards[i] = new_node # 删除跳表节点 def delete(self, value): update = [None] * self._level_count p = self._head for i in range(self._level_count - 1, -1, -1): while p._forwards[i] and p._forwards[i]._data < value: p = p._forwards[i] update[i] = p # 要删除节点的前驱节点 # 判断是否符合删除条件 if p._forwards[0] and p._forwards[0]._data == value: for i in range(self._level_count - 1, -1, -1): if update[i]._forwards[i] and update[i]._forwards[i]._data == value: update[i]._forwards[i] = update[i]._forwards[i]._forwards[i] # 相当于pre.next = pre.next.next ''' 最理想的情况就是，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ： 50%的概率返回 1 25%的概率返回 2 12.5%的概率返回 3 ... ''' # 随机函数，在redis中，概率是取到1/4 def _random_level(self, p: float = 0.5) -> int: level = 1 while random.random() < p and level < type(self)._MAX_LEVEL: level += 1 return level def __repr__(self) -> str: values = [] p = self._head while p._forwards[0]: values.append(str(p._forwards[0]._data)) p = p._forwards[0] return "->".join(values)if __name__ == "__main__": l = SkipList() for i in range(10): l.insert(i) print(l) p = l.find(7) print(p._data) l.delete(3) print(l)