一个有序的链表，我们选取它的一半的节点用来建索引，这样如果插入一个节点，我们比较的次数就减少了一半。这种做法，虽然增加了50%的空间，但是性能提高了一倍。如上图。
既然，我们已经提取了一层节点索引，那么，可以在第一层索引上再提取索引。如下图。(二级索引应去掉node2节点)
对于node5来说，它的next：
node5->next[2] = tailNode; node5->next[1] = node7; node5->next[0] = node6; 对于node7来说，它的next：
node7->next[1] = node9; node7->next[0] = node8; 对于node3来说，它的next：
node3->next[0] = node4; 查找
如果我们要找node6节点，(二级索引应去掉node2节点)
第一次比较headerNode->next[2]的值，也就是node5的值。显然node5小于node6（跳表的数据是有序的），所以，下一次应该从第2级的node5开始查询，也就是令targetNode = targetNode->next[2];
第二次应该比较node5->next[2]的值，也就是tailNode的值。tailNode的值是最大的。所以结果是大于，下一次应该从第1级的node5开始查询。这里从第2级跳到第1级。但是没有改变targetNode。
第三次我们应该比较node5->next[1]的值，也就是node7的值。因为node7大于node6，所以，下一次应该从第0级的node5开始查询。这里从第1级跳到第0级。也没有改变targetNode。
插入
当有2级索引时，新的节点先和2级索引比较，再和1级索引比较，最后和原链表比较，最终插到原链表中。当节点很多时，比较次数是原来的四分之一。
当然，当节点足够多的时候，我们还可以继续加索引，保证每一层索引数是低级索引的一半。当这一层只剩两个节点时，就没有必要再建索引了，因为一个节点没有比较的意义。
当很多节点插入时，上层索引节点已经不够用，我们需要在新节点中选取一部分节点提到上一层，跳表的设计者用“抛硬币”的方法选取节点是否提拔，也就是随机的方式，每个节点有50%概率会提拔。这样虽然不会让索引绝对均匀分布，但也会大体上是均匀的。
综上,插入的步骤：
- 新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
- 把索引插入到原链表。O（1）
- 利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
总体上，跳表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。
删除
- 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
- 删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳表删除操作的时间复杂度是O（N）。
应用
Redis当中的Sorted-set这种有序的集合，正是对于跳表的改进和应用。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176496.html原文链接：https://javaforall.net
