前面我们学习了二分查找法，如你所知，它是基于数组实现的时间复杂度为O(logn)的静态查找算法（适合静态数据）。那么，是否有一种数据结构让我们能基于链表实现类似“二分查找”的功能的算法呢？答案是肯定的，那就是跳表。
跳表不太常见，但是它是一种各方面性能都表优秀的动态数据结构，它支持快速插入、删除、查找，甚至可以替代红黑树。
怎样理解跳表
首先，我们有一组数据，它用链表存储：
跳表-链.jpg
如果我们对链表进行查询，它的时间复杂度为O(n)，那么，如果我们为这个链表增加一级索引，会有什么效果呢？
跳表-一级索引.jpg
如图，我们将抽出来的那一级叫做索引层，其中的 down 表示 down 指针，指向下一个结点。
我们看出，增加一层索引之后，查找一个值需要遍历的结点减少了，也就是查找效率提高了，那么我们为什么不再添加一层：
跳表-二级索引.jpg
使用同样的思路，我们可以一直向上构建索引，直到顶层索引只有两个结点：
跳表-多级索引查找.jpg
这种链表 + 多级索引的数据结构，就是跳表。
跳表的性能
跳表的查询
观察上面的例子，你可以看出，索引加上原始链表，跳表一共有 k = logn 层。
跳表-索引次数分析.jpg
结合两个条件，跳表的查询的时间复杂度为O(logn)。
跳表的内存消耗
我们需要创建索引层来实现跳表的功能，这势必会需要额外的内存实现。假设原始链表共有 n 个数据，每隔一个数据选取一个结点值作为索引，我们计算一下需要构建的结点总和：n/2 + n/4 + ... + 8 + 4 + 2 这是一个等比数列，求和为 n - 2 。
跳表-索引结点数.jpg
所以，跳表的空间复杂度为O(n)。
你可以计算一下，每 3 个结点需要耗费多少空间。
尽管空间复杂度为O(n)，但是如果我们存储的数据单元很大，那么索引带来的消耗基本上可以忽略。
动态插入和删除
跳表的查找操作的时间复杂度为O(logn)，使用链表进行插入删除的时间复杂度为O(1)，所以跳表的动态插入和删除的复杂度为O(logn)。
跳表索引的动态更新
当我们不停地插入数据时，如果不更新索引，就有可能出现某 2 个结点之间的数据非常多，极端情况下，跳表还会退化成单链表：
跳表的动态更新.jpg
在这里，我们通过一个随机函数，来决定将这个结点随机插入到哪几级索引中，比如随机函数生成了值 K ，那么就将这个结点添加到第一级到第 K 级索引中：
跳表-动态更新随机插入.jpg
与红黑树对比
跳表的插入、删除、查找 操作和红黑树的时间复杂度是一样的。但是，跳表可以很方便地按照区间来查找数据，而红黑树在这方面就逊色一些。
总结
跳表使用了空间换时间的设计思路，通过构建多级索引来提高查询效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是O(longn)。
跳表的空间复杂度为O(n)，但是可以通过改变构建索引的策略来平衡执行效率和内存消耗。
跳表的代码实现并不简单，但是作为一种动态的数据结构，它比红黑树要简单多了。所以很多时候，我们会使用跳表。
以上就是关于跳表的所有内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论