本文共 4604 字，大约阅读时间需要 15 分钟。
数据结构 - 跳跃链表
为什么会有跳表？
在处理普通单链表时，我们需要从头节点依次遍历到目标节点，这种方法在节点数量较多时效率较低，时间复杂度为 O(N)。为了加快查找速度，我们可以尝试使用跳表的思想。
跳表的基本原理类似于二分查找法，通过建立多个索引层，每个索引层包含链表中的一部分节点。例如，假设我们有一个普通单链表，当我们想要查找55号节点时，可以通过跳表的多个索引层快速定位到目标节点，减少遍历的节点数量，实现 O(logN) 的查询时间复杂度。
跳表的结构
跳表的最底层通常是双向链表或单链表，而索引层一般是单链表。节点类的定义如下：
class ListNode: def __init__(self, data=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] * self._MAX_LEVEL
跳表元素查询
要查询13号节点，可以从最高层开始查找。如果当前层没有找到目标节点，就向下一层继续查找，直到找到目标节点或确定不存在该节点。
如果要查找11号节点，我们可以从最高层开始，发现13号节点比我们要找的11号节点大，于是退回7号节点，再从下一层查找，直到找到目标节点或确定不存在该节点。
查询实现代码如下：
def find(self, value): 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] return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None
跳表元素插入
在跳表中插入节点时，需要先找到插入位置，然后根据随机生成的层数调整节点间的指向关系。
插入实现代码如下：
def insert(self, value): level = self._random_level() if self._level_count < level: self._level_count = level new_node = ListNode(value) new_node._forwards = [None] * level update = [self._head] * level 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 for i in range(level): new_node._forwards[i] = update[i]._forwards[i] update[i]._forwards[i] = new_node
随机层数生成函数如下：
def _random_level(self, p=0.5): level = 1 while random.random() < p and level < self._MAX_LEVEL: level += 1 return level
跳表元素删除
删除节点时，需要找到目标节点的前驱节点，并通过指针操作删除节点，确保索引层的正确性。
删除实现代码如下：
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]
完整代码
from typing import Optionalimport randomclass ListNode: def __init__(self, data=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] * self._MAX_LEVEL def find(self, value): 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] return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None def insert(self, value): level = self._random_level() if self._level_count < level: self._level_count = level new_node = ListNode(value) new_node._forwards = [None] * level update = [self._head] * level 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 for i in range(level): new_node._forwards[i] = update[i]._forwards[i] 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] def _random_level(self, p=0.5): level = 1 while random.random() < p and level < self._MAX_LEVEL: level += 1 return level def __repr__(self): values = [] p = self._head while p._forwards[0]: values.append(str(p._forwards[0]._data)) p = p._forwards[0] return "-".join(values) if values else ""
示例使用代码：
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)
如需了解更多关于跳跃链表的详细内容，可以参考相关技术文档或资料。
转载地址：http://fxvp.baihongyu.com/