跳表通过多层链表实现，查找、插入、删除平均时间复杂度为O(log n)；其结构由带指针数组的节点组成，每层为上层快照，随机决定层数以控制索引密度；c++实现包含头节点、最大层数、当前层数及随机生成器；查找从顶层开始逐层下降定位目标；插入时记录路径并更新各层指针，新节点层数由randomLevel()按50%概率递增确定；若新节点层数超过当前层数，则补全更新数组并将当前层数提升；删除时先查找节点，断开其在各层连接，同时检查并降低空层的当前层数；整体实现简单高效，适合有序数据操作且优于平衡树的复杂性，但需注意边界处理与重复值判断。
跳表（Skip List）是一种基于链表的数据结构，通过多层索引提升查找效率，平均时间复杂度为 O(log n)。相比平衡树，跳表实现更简单，且易于插入和删除。下面介绍 C++ 中跳表的结构设计与查找、插入、删除算法的实现。
跳表的基本结构
跳表由多层链表组成，底层是有序链表，每一层是上一层的“快照”，包含部分节点。每个节点有多个指针，指向同一层的下一个节点。
定义节点结构时，需要存储值和一个指针数组，用于指向每一层的下一个节点：
template <typename T> struct skiplistnode { T value; std::vector<SkipListNode*> next; <pre class='brush:php;toolbar:false;'>SkipListNode(T val, int level) : value(val), next(level, nullptr) {}
};
立即学习“C++免费学习笔记（深入）”；
跳表类的设计与参数
跳表类包含最大层数、当前层数、头节点以及随机数生成器。插入时通过随机函数决定节点层数，控制索引密度。
template <typename T> class SkipList { private: int maxLevel; int currentLevel; SkipListNode<T>* head; std::default_random_engine generator; std::uniform_int_distribution<int> distribution; <pre class='brush:php;toolbar:false;'>int randomLevel();
public: SkipList(int maxLvl = 16); ~SkipList();
void insert(T value); bool search(T value); bool remove(T value);
};
立即学习“C++免费学习笔记（深入）”；
template <typename T> SkipList<T>::SkipList(int maxLvl) : maxLevel(maxLvl), currentLevel(1), distribution(0, 1) { head = new SkipListNode<T>(T(), maxLevel); }
查找操作实现
从最高层开始，向右移动直到下一个节点值大于目标，然后下降一层继续，直到找到目标或到达底层。
template <typename T> bool SkipList<T>::search(T value) { SkipListNode<T>* current = head; <pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) { while (current->next[i] != nullptr && current->next[i]->value < value) { current = current->next[i]; } } current = current->next[0]; return current != nullptr && current->value == value;
}
插入操作与随机层数
先查找插入位置，记录每层最后访问的节点，再创建新节点并链接到各层。
randomLevel() 函数以 50% 概率增加一层：
template <typename T> int SkipList<T>::randomLevel() { int lvl = 1; while (distribution(generator) == 0 && lvl < maxLevel) { lvl++; } return lvl; }
insert() 实现：
template <typename T> void SkipList<T>::insert(T value) { std::vector<SkipListNode<T>*> update(maxLevel, nullptr); SkipListNode<T>* current = head; <pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) { while (current->next[i] != nullptr && current->next[i]->value < value) { current = current->next[i]; } update[i] = current; } current = current->next[0]; if (current != nullptr && current->value == value) { return; // 已存在 } int newNodeLevel = randomLevel(); if (newNodeLevel > currentLevel) { for (int i = currentLevel; i < newNodeLevel; i++) { update[i] = head; } currentLevel = newNodeLevel; } SkipListNode<T>* newNode = new SkipListNode<T>(value, newNodeLevel); for (int i = 0; i < newNodeLevel; i++) { newNode->next[i] = update[i]->next[i]; update[i]->next[i] = newNode; }
}
删除操作
查找节点并断开其在每一层的连接，若某层无节点则降低当前层数。
template <typename T> bool SkipList<T>::remove(T value) { std::vector<SkipListNode<T>*> update(maxLevel, nullptr); SkipListNode<T>* current = head; <pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) { while (current->next[i] != nullptr && current->next[i]->value < value) { current = current->next[i]; } update[i] = current; } current = current->next[0]; if (current == nullptr || current->value != value) { return false; } for (int i = 0; i < currentLevel; i++) { if (update[i]->next[i] != current) break; update[i]->next[i] = current->next[i]; } delete current; while (currentLevel > 1 && head->next[currentLevel - 1] == nullptr) { currentLevel--; } return true;
}
基本上就这些。跳表用空间换时间，实现比红黑树简单，适合需要有序数据但不想写复杂平衡逻辑的场景。注意随机层数策略影响性能稳定性，实际使用可调整概率。不复杂但容易忽略边界条件，比如空指针和重复值处理。