跳表来了, 顾名思义, 跳表就是可以跳跃的表, 我简单画了张图:
在原来链表的基础上, 建立一个新的索引链表, 原链表没两个建立一个
原来查找节点5的访问顺序是: 1->2->3->4->5->6,...共遍历了6个节点
现在在索引的基础上查找5的访问顺序是: 1->3->5->5->6(先访问索引), 共遍历了5个节点
这种链表加索引的结构就是跳表
查找
从刚才的介绍中可以看出, 加了一层索引后, 访问效率变高了...我们再次访问节点6, 访问顺序是: 1->5->5->5->6, 需要访问的节点又变少了, 原来访问节点6需要遍历6次, 现在只需要遍历5次
什么, 效率提升不明显?...从上面的例子可以看出, 简直就是二分查找的翻版, 时间复杂度O(logn)
空间复杂度
很清楚的看出来, 跳表的解决方案就是用空间来换时间
若原来的链表占用空间为n, 那么一级索引占用空间为n/2, 二级索引占用空间为...一种解决方案是, 当链表插入新的数据时, 同时将新插入的数据添加到跳表的索引中, 这样就解决了索引的问题, 但是将节点更新到所有索引中显然不可取, 同时也会降低查询的效率, 针对这种情况, 通过一个随机函数