下文介绍一种基于单链表的高级数据结构， 跳表 。
将单链表先进行排序，然后针对 有序链表 为了实现高效的查找，可以使用跳表这种数据结构。
其根本思想是 二分查找 的思想。
跳表的前提条件是 针对 有序的单链表 ，实现高效地查找，插入，删除。
Redis中的 有序集合 sorted set 就是用跳表实现的。
对于单链表，即使是 存储的有序数据（即 有序链表），想在其中查找某个数据，也只能从头到尾遍历，查找效率低，时间复杂度是O(n)，如下图所示：
怎么才能提高查找效率呢？
为了提高查找效率，使用二分查找的思想，对有序链表建立一级“索引”。 每两个节点提取一个节点到索引层。 索引层中的每个节点 都包含两个指针，一个指向下一个节点，一个down指针，指向下一级节点。
假设要查找图中 18这个节点：
首先在一级索引层遍历，当遍历到14这个节点的时候，发现其下一个节点是23，则要查找的18就在14和23之间。 然后，通过14节点的 down 指针，下降到原始链表这一层，继续在原始链表中遍历。 此时，只需要在原始链表中，遍历两个节点，14和18,就找到18这个节点了。 查找18这个节点，在原始链表需要遍历10个节点，现在只需要遍历7个节点（一级索引层遍历5个节点，原始链表遍历2个节点）。
从以上示例可以看出，加上一层索引之后，查找一个节点的遍历节点数减少了，效率提高了。如果再增加一级索引，那么效率会不会更高呢？
建立二级索引
与建立一级索引的方式类似，在第一级索引的基础上，每两个节点抽出一个节点到第二级索引，如下图：
现在如果要查找18节点，只需要遍历6个节点（二级索引层遍历3个节点，一级索引层1个节点，原始链表2个节点）。
通过建立索引的方式，对于数据量越大的有序链表，通过建立多级索引，查找效率提升会非常明显。
这种链表加多级索引的结构 就是 跳表。
假设链表包含n个节点，在单链表中查询某个数据的时间复杂度是O(n)。
一个包含n个节点的有序单链表最多会有多少级索引？
每两个节点抽出一个节点作为上一级索引的节点，则 ：
第一级索引的节点个数大约是 n/2 ，第二级索引的节点个数大约是 n/4，第三级索引的节点个数大约是 n/8，则第k级索引节点的个数大约是
。
假设有 h 级索引，最高一级的索引有两个节点，也就是 
，从而求得
如果把原始链表这一层也算进去，那么整个跳表的高度约为 
在跳表查询时，每一级索引 最多需要遍历3个节点。
（因为假设在上图跳表中，从二级索引层，查找 节点12，则从节点1遍历到节点7，然后再遍历节点14(节点12 小于 节点14) ，从节点7向下一级索引层遍历到节点7，然再向右遍历节点11，再遍历节点14，发现节点12小于节点14， 则继续向下一级遍历，最终在下一级遍历到节点12。
在上面遍历节点12的过程，在二级索引层遍历了3个节点（1—>7---->14），在一级索引层遍历了3个节点（7—>11---->14）。因此每一级最多遍历3个节点。 ）
那么在跳表中查询数据的时间复杂度就是 每一层遍历的节点数乘以层数 
，因此跳表中查找的时间复杂度就是O(logn). 与二分查找的时间复杂度相同。
基于单链表实现了二分查找，查询效率的提升依赖构建了多级索引，是一种空间换时间的设计思路。
建立索引后 的 总的索引点 的 空间复杂度：
跳表的查询数据的空间复杂度是O(n)，也就是说，基于单链表构造跳表，需要额外再用一倍的存储空间。
有没有办法降低索引占用的存储空间呢？
如果每3个节点 或 每5个节点抽1个节点到上一级索引，索引节点就会相应减少。假设每3个节点抽取一个节点到上一级，总的索引节点个数为：
每3个节点抽1个节点到上一级索引的方法 比 每2个节点抽1个节点构建索引的方式，减少了一半的索引节点存储空间。
因此，通过调节抽取节点的间隔，控制索引节点占用的存储空间，以此来达到空间复杂度 和 时间复杂度的平衡。
跳表作为一个动态数据结构，不仅支持查找操作，还支持数据的插入和删除操作，并且 插入和删除的操作的时间复杂度都是O(logn).
为了保证原始链表中数据的有序性，我们需要先找到新数据应该插入的位置。 可以基于多级索引，快速查找到新数据的插入位置，时间复杂度为O(log n)。
假设插入数据为6的节点，如下图：
删除原链表中的节点，如果节点存在于索引中，也要删除索引中的节点。 因为单链表中的删除需要用到 要删除节点 的 前驱动节点。 可以像插入操作一样，通过索引逐层向下遍历到原始链表中，要删除的节点，并记录其 前驱节点，从而实现删除操作。
当频繁地向跳表中插入数据时，如果插入过程不伴随着索引更新，就有可能导致某2个索引节点之间数据非常多，在极端地情况下，跳表就会退化成单链表。
作为一种动态数据结构，为了避免性能下降，我们需要在数据插入，删除的过程中，动态地更新跳表的索引结构。 就像红黑树，二叉平衡树是通过左右旋来保持左右子树的大小平衡， 而跳表是借助随机函数来更新索引结构。
当向跳表中插入数据时，我们选择同时将这个数据插入到部分索引层中。 如何决定插入到哪些索引层中呢？ 通过一个随机函数来决定，比如通过 随机函数得到某个值 K, 那么就将这个节点添加到第一级到第K级索引中。
为什么Redis中的有序集合用跳表而非红黑树来实现呢？
1.对于插入，删除，查找 以及 输出有序序列 这几个操作，红黑树也可以完成，时间复杂度 与 用跳表实现是相同的。 但是，对于按照区间查找数据这个操作（比如 [20,300]）,红黑树的效率没有跳表高，跳表可以做到 O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序向后遍历输出，直到遇到值大于区间终点的节点为止。
2.跳表更加灵活，它可以通过改变节点的抽取间隔，灵活地平衡空间复杂度和时间复杂度
3.相比红黑树，跳表更容易实现，代码更简单。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/13389.html