跳跃表是一种基于有序链表的拓展，简称跳表。
下面正式开始了哦，跟着思路来，非常简单理解:
一.基本思想
给定一个有序链表：1->2->3->5->6->7->8
跳表的思想就是利用了类似索引的思想，提取出链表中的部分关键节点，然后再用二分查找。
上面的有序链表，把奇数作为关键节点提取出来：
现在要插入一个值为4的节点，传统的做法是逐一比较，现在只需要比较关键节点，3，5，7。
确定了它在3和5之间的话就回原链表查找，迅速定位到对应的位置插入。
上面的过程体现了跳表另外一个思想：以空间换时间。在数据量特别大的时候效果非常明显。
二.进一步优化
上面只是介绍了基本思想，其实还可以继续优化，看到这别担心，难度不会增加，也非常好理解:
既然上面提取了一层节点作为索引，那是不是也可以进一步提取？
有了2级索引后，插入的节点可以先和2级索引比较，确定大体范围;然后再和1级索引比较;最后再回到原链表，找到并插入对应的位置。
节点多的时候还可以进一步提取，保证每一层是上一层节点的一半。提取的极限是同一层只有两个节点的时候，因为一个节点比较没有意义。
到这里，多层链表结构就提取完了，这就是跳跃表。
三.其他问题
当大量新节点通过逐层比较插入到链表中后，上层节点就会显得不够用，这就需要从新节点中“提拔”一部分节点到上一层，问题就是“提拔”谁呢(如何选择索引)？
跳表设计者采用了“抛硬币”的方法，随机决定新节点是否提拔。因为跳表的添加和删除的节点是不可预测的，很难用算法保证跳表的索引分布始终均匀。虽然抛硬币的方式不能保证绝对均匀，但大体上是趋于均匀的。
比如说，9插入到链表后，开始分析：
跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。
四.删除的情况
删除的时候只要在索引层找到要删除的节点，然后删除每一层相同的节点即可。如果某一层删到只剩下一个，那么整层都可以删掉。比如删除5:
跳跃表删除操作的时间复杂度是O（logN）。
五.跳跃表和二叉查找树的对比
跳表维持结构平衡的成本较低，完全靠随机。二叉查找树在多次插入和删除后需要重新保持自平衡。
六.应用
Redis的五种数据类型之一Sorted-set(zset)这种有序集合，正是对于跳跃表的改进和应用。
还有Java中的ConcurrentSkipListMap和ConcurrentSkipListSet内部都是用跳表的数据结构。
