跳表（跳跃列表） 跳表（跳跃列表）

跳表

结合链表和二分法的特点，将链表进行加工，创造一个二者的结合体：

1. 单链表中的各个节点依次按照一定顺序排列
2. 可以进行跳转查找（类似于二分查找算法），从而显著降低其时间复杂度

跳表作为一种以空间换时间的策略被广泛采用，在数据结构中它通过在每个节点中引入指向后续节点的前向指针来提高数据查找的速度。

跳表的性质
(1) 跳表由多层结构构成,层级通过特定概率生成
(2) 每一层均为有序的单向链表,默认按升序排列
(3) 最底层(Level 1)的所有数据项均被包含
(4) 若某数据项存在于Level i 的链表中,则该数据项也将存在于该层级下所有更低层级的结构中
(5) 每个节点拥有两个指针,其中一个用于指向其所在链表中的下一个元素,另一个用于指向对应下一层级的节点

next数组
在一个有序链表中选择其一半数量的节点用于构建索引结构。当向链表中插入一个新的节点时, 比较所需的次数将减少50%的数量. 这种策略虽然会导致存储空间增加50%, 但其性能效率提升了约一倍.

一般会设定跳表中的层级数量为层数-1（其中最