跳表删除详解（手把手教你用Python实现跳表的删除操作）

跳表删除的基本思路

要删除一个值，我们需要：

1. 从最高层开始向下搜索目标值；
2. 记录每层中目标值前一个节点（称为 update 数组）；
3. 如果找到目标节点，就从所有包含它的层级中将其移除；
4. 必要时缩减跳表高度（比如最顶层变空）。

这个过程的关键在于维护好每一层的前驱节点，确保删除后链表依然连贯。

Python 实现跳表删除

我们先定义跳表节点类和跳表主类，再重点实现删除方法。

import randomclass SkipListNode:    def __init__(self, value, level):        self.value = value        self.forward = [None] * (level + 1)  # 每一层的下一个节点class SkipList:    def __init__(self, max_level=16, p=0.5):        self.max_level = max_level        self.p = p        self.header = SkipListNode(-1, max_level)  # 头节点        self.level = 0  # 当前跳表实际层数    def _random_level(self):        level = 0        while random.random() < self.p and level < self.max_level:            level += 1        return level    def delete(self, value):        # 1. 创建 update 数组，记录每层待删除节点的前驱        update = [None] * (self.max_level + 1)        current = self.header        # 2. 从顶层往下搜索        for i in range(self.level, -1, -1):            while current.forward[i] and current.forward[i].value < value:                current = current.forward[i]            update[i] = current        # 3. 检查下一层是否就是目标节点        current = current.forward[0]        if current and current.value == value:            # 4. 从所有层级中删除该节点            for i in range(self.level + 1):                if update[i].forward[i] != current:                    break                update[i].forward[i] = current.forward[i]            # 5. 调整跳表高度（如果顶层变空）            while self.level > 0 and self.header.forward[self.level] is None:                self.level -= 1            print(f"成功删除值: {value}")            return True        else:            print(f"未找到值: {value}")            return False

代码解析

- update 数组保存了每一层中目标节点的前一个节点。

- 删除时，我们只在那些确实指向目标节点的层级中进行断链操作。

- 删除完成后，如果最高层不再有任何节点，我们就降低 self.level，避免浪费空间。

测试删除功能

# 简单测试sl = SkipList()# 假设已插入 10, 20, 30# （此处省略 insert 方法，重点在 delete）sl.delete(20)  # 应输出“成功删除值: 20”sl.delete(25)  # 应输出“未找到值: 25”

为什么跳表值得学习？

相比红黑树等复杂结构，跳表逻辑清晰、易于实现，且在并发场景下更容易加锁优化。Redis 的有序集合（ZSET）就使用了跳表！掌握Python跳表和跳表删除算法，能让你在面试和项目中脱颖而出。

总结

本教程详细讲解了跳表的删除操作，包括原理、步骤和完整代码。希望你现在已经理解如何在 Python 中实现这一关键操作。记住，数据结构教程的核心不仅是记住代码，更是理解背后的逻辑。

继续练习，你也能写出高效的跳表实现！