为什么要有跳表这样的结构?
拿一个单链表来说,即便单链表的数据是有序的,如果我们想从里面查找一个指定的数,那么时间复杂度任然是O(N). 那么怎么才能是链表的查询速度变快呢?
这就是跳表这个数据结构,跳表就是在链表的基础上增加多级索引,从而提高查询速度的.
跳表结构,每两个节点会抽出一个节点来作为上一级索引的节点,那么第一级节点的个数就是n/2, 第二级n/4..... 那么跳表的高度时间就是log2(N).
查询16的路径分析:
1->7->13->13(down)->13(down)->16
整个查询是log(N)级别的.