跳跃表(skiplist)
跳跃表是一种有序数据结构,通过在每个节点中维护多个指向其他节点的指针,达到快速访问节点的目的。
查找算法复杂度:平均O(logN)、最坏O(N)
1、结构及实现
1.1跳跃表
header: 指向表头节点的指针
tail: 指向表尾节点的指针
level: 跳跃表内层数最大的节点的层数(不包含表头节点层数)
length: 跳跃表的长度,即跳跃表目前包含的节点数量(不包含表头节点)
1.2跳跃表节点
obj: 成员对象
score: 分值,跳跃表中,节点按各自保存的分值从小到大排列
backward: 后退指针,指向当前节点的前一个节点,用于从表尾向表头遍历
level: 层
forward:前进指针,用于访问位于表尾方向的其他节点
span:跨度,记录前进指针所指向的节点和当前节点的距离