听说过跳表这种数据结构么

一、什么是跳表

我们在上一篇中介绍了时间复杂度十分优秀的二分查找算法，但是它只能作用于有序数组上，查找起来比较方便，但是数组中插入和删除元素是比较麻烦的；那么有没有办法让二分查找也能作用于有序链表上，从而达到查找、插入和删除元素都十分的快速呢？

对于普通的有序列表来说，当然不能实现我们的目标，如下查找的时间复杂度为O(n)；

原始有序单链表

我们可以基于原始链表建立一个索引层，比如每两个节点提取一个节点到索引层：

带一级索引的跳表

如此，两种数据结构我们查找元素16的比较次数分别为10次和8次，确实能提高查询速度；我们更近一步，再次建立第二级索引：

带二级索引的跳表

此时查找元素16比较的次数只需要比较7次即可；

如果在大数据量的有序链表中，我们建立很多层索引，使得最高层索引只有两个节点，那么就实现了类似二分查找的算法思想，此时这种数据结构就被成为跳表。

假设有序链表总节点个数为n，我们建立索引时每两个节点提取一个索引节点；那么第一级索引共有n/2个节点；

第k级索引共有（n/2^{k）个节点，假设k为最高级索引，为2个节点，那么2=(n/2}k)，n=2^(k+1)，k=logn-1，如果原始链表也算进去的话，k=logn正好是整个数据结构的高度。

假设每一层需要遍历m个节点，那么时间复杂度就可以表示为O(mlogn)，但是推断m是常量级别的，因此可以忽略，那么整个查找过程时间复杂度就是O(logn)，竟然和二分查找是一样的高效！

第一级索引需要n/2个节点，第二级需要n/2^{2个节点，依次类推，第k级索引需要的节点个数为n/2}k，这正好是一个等比数列，等比数列求和的结果是n-2，所以空间复杂度为O(n)，这是一个以空间换时间的策略；

我们可以每3个节点或者每4个节点往上提取一个索引节点，如此可以适当减少需要的额外空间，但是空间复杂度仍然为O(n)；如果有序链表存储的是大对象，那么索引节点中无需存放整个大对象，只要存储对象的指针即可，所以此时空间复杂度就显得不那么重要了；

跳表因为是顺序链表，所以真正插入和删除的时间复杂度都是O(1)，但是找到需要插入节点的位置或者找到待删除的节点时间复杂度为O(logn)；

跳表在删除的时候，除了需要删除原始有序链表中的节点，还需要同步删除k级索引中的全部该索引节点；

跳表在插入元素式，极端情况下会导致两个索引节点中存在大量的原始节点，时间效率极有可能会退化为单链表的O(n)，所以需要动态地平衡和更新k级索引节点；

Redis在存储有序集合的时候就用到了跳表+散列表的数据结构，跳表和红黑树相比，插入、删除、查找的时间复杂度相同，但是跳表在按照区间查找时明显具有效率优势，而且跳表实现起来比红黑树要简单易懂，不容易出错。

红黑树等常用数据结构在程序语言中都是封装好的，我们想用的话直接拿来用即可，比如HashMap，但是跳表却没有对应的封装好的数据结构，想用的话开发者必须自己去实现。