跳表是一种基于多层链表的动态数据结构，通过随机化层数实现平均O(log n)的查找、插入和删除性能；其核心由带前向指针数组的节点构成，利用头节点简化操作，从最高层开始逐层跳跃查找，插入时记录路径并更新各层指针，删除时断开连接并回收内存，同时可优化当前最大层数；相比平衡树，跳表代码更简洁、易于维护，且在并发场景下表现良好。
跳表（Skip List）是一种基于概率的动态数据结构，能够以较低的实现复杂度达到与平衡树相近的性能。相比红黑树、AVL树等复杂的自平衡二叉搜索树，跳表在插入、删除和查找操作上平均时间复杂度均为 O(log n)，且代码更简洁、易于理解和维护。它通过多层链表实现快速“跳跃”，从而提升查询效率。
跳表的基本原理
跳表本质上是一个多层有序链表。底层（第0层）包含所有元素，每一层都是下一层的“快速通道”。每个节点有一定概率向上提升一层（通常为50%），形成索引。查找时从最高层开始，像二分查找一样向右、向下移动，直到找到目标值。
主要特点：
- 随机化层数：新节点的层数由随机函数决定，避免严格平衡带来的复杂调整。
- 前向指针数组：每个节点维护一个指针数组，指向每一层的下一个节点。
- 头节点简化操作：设置一个虚拟头节点，统一处理边界情况。
核心结构设计
定义跳表节点和主类结构：
立即学习“C++免费学习笔记（深入）”；
// 跳表节点 struct SkipListNode { int val; std::vector// 跳表主类 class SkipList { private: static const int MAX_LEVEL = 16; // 最大层数 SkipListNode* head; // 头节点 int currentLevel; // 当前最大有效层数
// 随机生成节点层数
int randomLevel() {
int level = 1;
while (rand() % 2 == 0 && level < MAX_LEVEL) {
++level;
}
return level;
}public: SkipList() : currentLevel(1) { head = new SkipListNode(-1, MAX_LEVEL); }
查找操作实现
从最高层开始，向右直到下一个节点值大于目标，然后下降一层继续，最终在底层判断是否存在。
bool search(int target) { SkipListNode* curr = head; for (int i = currentLevel - 1; i >= 0; --i) { while (curr->forward[i] && curr->forward[i]->val forward[i]; } } curr = curr->forward[0]; return curr && curr->val == target; }插入操作实现
先查找路径并记录每层最后访问的节点，再随机生成新节点层数，更新各层指针。
void add(int num) { std::vector
// 查找插入位置，记录每层最后一个小于num的节点
for (int i = currentLevel - 1; i >= 0; --i) {
while (curr->forward[i] && curr->forward[i]->val < num) {
curr = curr->forward[i];
}
update[i] = curr;
}
int newNodeLevel = randomLevel();
SkipListNode* newNode = new SkipListNode(num, newNodeLevel);
// 更新各层指针
for (int i = 0; i < newNodeLevel; ++i) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
// 更新当前最大层数
if (newNodeLevel > currentLevel) {
currentLevel = newNodeLevel;
}}
删除操作实现
查找目标节点，若存在则逐层断开连接，并回收内存。同时检查是否需要降低当前最大层数。
bool erase(int num) { std::vectorfor (int i = currentLevel - 1; i >= 0; --i) {
while (curr->forward[i] && curr->forward[i]->val < num) {
curr = curr->forward[i];
}
update[i] = curr;
}
curr = curr->forward[0];
if (!curr || curr->val != num) return false;
// 断开各层指针
for (int i = 0; i < currentLevel; ++i) {
if (update[i]->forward[i] != curr) break;
update[i]->forward[i] = curr->forward[i];
}
delete curr;
// 降低当前层数（可选优化）
while (currentLevel > 1 && head->forward[currentLevel-1] == nullptr) {
--currentLevel;
}
return true;}
完整的析构函数可以遍历底层链表释放所有节点，防止内存泄漏。
跳表作为平衡树的替代方案，优势在于实现简单、并发友好（如ConcurrentSkipListMap）、支持范围查询高效。虽然最坏情况性能不如严格平衡树，但平均表现足够优秀，适合大多数场景。
基本上就这些。不复杂但容易忽略细节，比如随机层数控制和指针更新顺序。写好后多测几个边界用例即可稳定使用。
