从有序链表的问题开始
第一次看到 Skip List，也就是跳表时，我觉得它的结构有一点奇怪。它不像二叉搜索树那样有明确的左右子树，也不像哈希表一样通过哈希函数直接定位元素，而是在普通链表上面又增加了很多层链表。
要理解 Skip List，可以先从一个普通的有序链表开始。
假设链表中保存：
1 → 3 → 7 → 12 → 18 → 25 → 31 → 40
如果要查找 31，只能从头开始不断向后移动：
1 → 3 → 7 → 12 → 18 → 25 → 31
虽然数据已经有序，但是链表本身不能像数组一样通过下标直接访问中间位置，因此有序并没有让查找快很多。
最坏情况下仍然需要遍历整个链表，时间复杂度是：
O(n)
Skip List 的核心想法就是：既然每次一个节点一个节点地走太慢，那么能不能在链表上增加一些“快速通道”？
给链表增加索引
例如从原始链表中抽出一部分节点：
Level 1:
1 -------- 7 -------- 18 -------- 31
Level 0:
1 → 3 → 7 → 12 → 18 → 25 → 31 → 40
现在查找 31 时，可以先沿着 Level 1 向右走。
从 1 跳到 7，再跳到 18，再跳到 31，就不需要访问底层所有节点。
如果数据更多，还可以继续往上建立索引：
Level 2:
1 ---------------- 18
Level 1:
1 -------- 7 ----- 18 -------- 31
Level 0:
1 → 3 → 7 → 12 → 18 → 25 → 31 → 40
这时候 Skip List 已经有点类似二分查找的感觉了。
查找时先从最高层开始。如果下一个节点还没有超过目标值，就向右移动；如果继续向右会超过目标值，就下降一层继续查找。
因此整个过程可以概括为：
能向右就向右
不能向右就向下
直到到达最底层。
为什么不用固定规则建立索引
这里还有一个很有意思的问题：
哪些节点应该出现在上一层？
一种直观的做法是每隔两个节点抽一个节点，但是这样一来，每次插入或删除节点后，都可能需要重新调整大量索引。
Skip List 选择了另一种方式：随机。
当插入一个新节点时，它首先一定出现在最底层，然后通过随机过程决定它是否继续出现在更高一层。
例如可以规定：
50% 的概率升到 Level 1
50% 的概率继续升到 Level 2
50% 的概率继续升到 Level 3
……
因此一个节点的层数可能是：
1 层
2 层
3 层
4 层
……
层数越高的节点通常越少。
从整体来看，就会形成一种逐渐稀疏的结构：
Level 3: 1 ------------------------------ 31
Level 2: 1 ------------- 18 ------------- 31
Level 1: 1 ----- 7 ----- 18 ----- 25 ---- 31
Level 0: 1 → 3 → 7 → 12 → 18 → 25 → 31 → 40
它并不保证每一层绝对均匀，但是从概率上看，通常可以保持比较合理的分布。
这也是 Skip List 和 AVL Tree、Red-Black Tree 一个很大的区别。
平衡树通过旋转等操作严格维持结构平衡，而 Skip List 不强制维护严格平衡，而是依赖随机概率得到一个“总体上足够好”的结构。
查找复杂度
如果这些索引层分布比较合理，那么每下降一层，都可以排除掉相当一部分节点。
因此 Skip List 的平均查找复杂度可以达到：
O(log n)
插入和删除也类似。
首先通过 Skip List 找到目标位置，然后只需要调整对应层上的指针，所以平均时间复杂度同样为：
查找：O(log n)
插入：O(log n)
删除：O(log n)
不过这里需要注意一个关键词：平均。
Skip List 是一种概率型数据结构。
极端情况下，如果所有节点都没有生成高层索引，那么它就会退化成一条普通链表，此时查找复杂度会变成：
O(n)
只是这种情况出现的概率通常很低。
插入一个节点发生了什么
例如现在要插入 20。
首先按照正常查找过程找到：
18 < 20 < 25
所以底层变成：
18 → 20 → 25
接下来随机决定 20 能达到多少层。
假设它最终拥有三层，那么还需要把它插入 Level 1 和 Level 2：
Level 2: 18 ------ 20 -------- 31
Level 1: 18 ------ 20 -- 25 -- 31
Level 0: 18 → 20 → 25 → 31
实际上 Skip List 在查找插入位置时，通常会顺便记录每一层最后一个小于目标值的节点。
插入时就可以直接修改这些节点的 next 指针，而不需要重新遍历一遍。
Skip List 和其他结构的区别
Skip List、Hash Table 和平衡搜索树解决的问题有一些重叠，但是特点并不完全一样。
Hash Table 的平均查找速度通常可以达到 O(1)，非常适合根据一个确定的 key 查找数据，但是它天然不擅长维护数据的有序关系。
例如：
找 key = 100
哈希表非常适合。
但是如果问题变成：
找到 100 到 200 之间的所有元素
有序结构通常更加方便。
而 Skip List 本身就是按照 key 的顺序组织节点，所以范围查询比较自然。
和平衡树相比，Skip List 的理论最坏情况没有那么漂亮，但是它的实现思路比较直接。主要操作基本都是：
比较 key
移动指针
修改 next
不需要处理复杂的树旋转和重新平衡。
我的理解
我现在更愿意把 Skip List 看成一种“用空间换跳跃距离”的结构。
普通链表只有一条路：
一个一个往后走
Skip List 则在原链表上建立了多级高速通道：
先走高速层
→ 接近目标
→ 下到更细的一层
→ 最后进入底层定位
它最有意思的地方并不是“多层链表”本身，而是它没有通过复杂规则维护绝对平衡，而是利用概率获得接近 O(log n) 的平均性能。
这也是一种很值得学习的数据结构设计思想：
有时候并不需要维护一个严格完美的结构，只需要保证它在概率意义上足够好，就可以用更简单的实现得到很不错的性能。