介绍跳表
技术是为了解决问题而生的，跳表主要用来解决：有序链表逐个查找效率慢的问题。
具体来说，跳表在有序链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速查找。三级索引指向二级索引，二级索引指向一级索引，以此类推。
跳表如下图所示：
如果我们要在链表中查找 33 这个元素，只能从头开始遍历链表，查找 6 次，直到找到 33 为止。此时，时间复杂度是 O(N)，查找效率很低。
为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个元素出来作为索引。这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。此时，我们只需要 4 次查找就能定位到元素 33 了。
如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取 1、27、100 作为二级索引，二级索引指向一级索引。这样，我们只需要 3 次查找，就能定位到元素 33 了。
可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时，跳表的查找时间复杂度就是 O(logN)。
参考资料
若有收获，就点个赞吧
1 人点赞
