golang泛型实现——skiplist@慕课网 原创
func (s *SkipList[T]) InsertInner(score float64, elem T, level int) *SkipList[T] {
var (
update [SKIPLIST_MAXLEVEL]*Node[T]
rank [SKIPLIST_MAXLEVEL]int
)
x := s.head
var x2 *Node[T]
for i := s.level - 1; i >= 0; i-- {
if i == s.level-1 {
rank[i] = 0
} else {
rank[i] = rank[i+1]
}
for x.NodeLevel[i].forward != nil &&
(x.NodeLevel[i].forward.score < score) {
// 暂时不支持重复的key, 后面再说 TODO
//|| x.NodeLevel[i].forward.score == score &&
//s.compare(elem, x.NodeLevel[i].forward.elem) < 0) {
//TODO span的含义是?
rank[i] += x.NodeLevel[i].span
x = x.NodeLevel[i].forward
}
// 保存插入位置的前一个节点, 保存的数量就是level的值
update[i] = x
}
// 这个score已经存在直接返回
x2 = x.NodeLevel[0].forward
if x2 != nil && score == x2.score {
x2.elem = elem
return s
}
if level > s.level {
// 这次新的level与老的level的差值, 给填充head指针
for i := s.level; i < level; i++ {
// TODO rank的含义
rank[i] = 0
update[i] = s.head
update[i].NodeLevel[i].span = s.length
}
s.level = level
}
// 创建新节点
x = newNode(level, score, elem)
for i := 0; i < level; i++ {
// x.NodeLevel[i]的节点假设等于a, 需要插入的节点x在a之后,
// a, x, a.forward三者的关系就是[a, x, a.forward]
// 那就变成了x.forward = a.forward, 修改x.forward的指向
// a.forward = x
// 看如下两行代码
x.NodeLevel[i].forward = update[i].NodeLevel[i].forward
update[i].NodeLevel[i].forward = x
x.NodeLevel[i].span = update[i].NodeLevel[i].span - (rank[0] - rank[i])
update[i].NodeLevel[i].span = rank[0] - rank[i] + 1
}
for i := level; i < s.level; i++ {
update[i].NodeLevel[i].span++
}
if update[0] != s.head {
x.backward = update[0]
}
if x.NodeLevel[0].forward != nil {
x.NodeLevel[0].forward.backward = x
} else {
s.tail = x
}
s.length++
return s
}