引言
跳表（Skip List）是一种动态数据结构，由 William Pugh 于 1989 年提出。它本质上是对传统链表的优化，通过在链表上建立多层索引，将查找时间复杂度从 O(n) 降低到 O(log n)。这种设计在保持链表简单性的同时，实现了接近平衡树的查找效率，且无需维护复杂的旋转操作。
在传统链表中，由于只能顺序遍历，处理大规模数据时效率低下。跳表通过引入随机化策略构建多层索引结构，每一层都是下一层的'加速'版本。查找时从顶层开始逐层向下，快速缩小搜索范围。这种结构特别适合需要频繁插入、删除及查找的动态场景，如数据库索引和缓存系统。
核心思想
跳表的核心在于多层链表与概率性分布。最底层是包含所有数据的完整有序链表，上层链表则是下层节点的子集。每个节点被提升到上一层的概率通常是固定的（例如 50%），这使得高层节点数量随层级指数级减少。
这种设计带来了几个显著特点：
- 查找效率高：平均时间复杂度为
O(log n)，接近平衡树。 - 动态性强：插入和删除操作只需调整指针，无需像红黑树那样进行复杂的平衡旋转。
- 空间消耗灵活：空间复杂度为
O(n)，可通过调整提升概率控制内存占用。 - 并发友好：基于局部指针修改，较容易实现无锁或细粒度锁的并发控制。
结构设计
节点定义
每个节点除了存储数据值外，还需要一个指针数组来指向不同层级的下一个节点。节点的层数是随机生成的，决定了它在哪些层级存在。
struct SkipListNode {
int _val;
std::vector<SkipListNode *> _nextV;
SkipListNode(int val, int level) : _val(val), _nextV(level, nullptr) {}
};
跳表类封装
跳表类负责管理头节点、最大层数以及随机层数的生成逻辑。头节点作为哨兵，不存储有效数据，仅用于简化边界处理。
class SkipList {
private:
typedef SkipListNode Node;
size_t _maxLevel = 32;
double _p = 0.25; // 提升概率
Node *_head;
// 辅助函数：记录每层的前驱节点
std::vector<Node *> FindPrevNode(int value);
;
:
() { (()); _head = (, ); }
~() { }
;
;
;
};
