跳表有着诸多的优越性，在 redis、leveldb、Kafka 中都有诸多使用，他是综合插入，删除，查找性能最优越的一个数据结构，而他的实现又是如此的优雅，下面是 golang 版本的一个实现，增加诸多注释。
const (
maxLevel = 16
p = 0.25
)
type Node struct {
Val int
Next []*Node
}
type Skiplist struct {
level int
header *Node // 头节点
}
func Constructor() Skiplist {
return Skiplist{
level: 0, // 默认层为0
header: &Node{
Next: make([]*Node, maxLevel), // 头节点有 maxLevel 个指针
},
}
}
func (this *Skiplist) Search(target int) bool {
cur := this.header // 从头开始
for i := this.level - 1; i >= 0; i-- {
// 从最高层开始，依次向下一层查找
for cur.Next[i] != nil && cur.Next[i].Val < target {
// 如果当前层的值比目标值小，则继续在当前层前进
cur = cur.Next[i]
}
// 如果当前层找到的这个最小值的下一个值不为nil，并且等于目标值，直接返回 true
if cur.Next[i] != nil && cur.Next[i].Val == target {
return true
}
}
// 全局扫一遍都没找到就返回 false
return false
}
func (this *Skiplist) max(a, b int) int {
if a > b {
return a
}
return b
}
func (this *Skiplist) randLevel() int {
l := 1
// 默认 1 层，每增加一层概率缩小
for rand.Float64() < p && l < maxLevel {
l++
}
return l
}
func (this *Skiplist) Add(num int) {
//其实这个变量思考了很久，不知道他在干什么
// 1. updateNode 其实需要记录着每一层对于 num 这个节点找到的最接近的值
// 2. 初始化为 header ,是因为方便简化下面的一个新节点加入的时候逻辑
// 3. 新加入的节点，它可能不会增加新的层，那么他的前驱就是第 1 点描述
// 4. 新加入的节点，它可能会增加新的层，新层的话这个新节点的前驱节点就是 header，第 2点描述
updateNode := make([]*Node, maxLevel)
for i := range updateNode {
updateNode[i] = this.header
}
// 从当前节点开始
cur := this.header
for i := this.level - 1; i >= 0; i-- {
for cur.Next[i] != nil && cur.Next[i].Val < num {
cur = cur.Next[i]
}
updateNode[i] = cur // 记录本层，最接近 num 的节点
}
lv := this.randLevel() // 新节点的层数
newNode := &Node{
Val: num, // num 赋值，这里不判断重复值，重复的依然插入
Next: make([]*Node, lv), // 有几层，就有几个指针
}
for i := 0; i < lv; i++ {
// 从第 0 层开始，对于每一层都要赋值
// 新节点的在第 i 层的下一个节点等于 updateNode 所指向的下一个节点
// updateNode 的下一个节点执行 newNode 这个新节点
newNode.Next[i], updateNode[i].Next[i] = updateNode[i].Next[i], newNode
}
// 跳表最大的层级等于之前的层级和此节点的层级最大值
this.level = this.max(this.level, lv)
}
func (this *Skiplist) Erase(num int) bool {
flag := 0 // 是否触发删除，触发删除逻辑则为 1
newLevel := this.level // 删除节点可能会触发层级降低，因为空的层级没啥意义
cur := this.header
// 依旧是遍历
for i := this.level - 1; i >= 0; i-- {
// 逻辑类似
for cur.Next[i] != nil && cur.Next[i].Val < num {
cur = cur.Next[i]
}
// 我这里的实现和大多数人不一样，但是我觉得这样简单一些
// 这里和 search 实现有点类似，如果找到下一个值和目标值相等
if cur.Next[i] != nil && cur.Next[i].Val == num {
cur.Next[i] = cur.Next[i].Next[i] // 当前节点指向的下一个节点等于当前节点的下下个节点，那么下个节点就相当于删除了，可以思考一下指针
flag = 1 // 修改标志位
if this.header.Next[i] == nil {
// 这里其实是缩层逻辑，如果在这一层，头指针指向了一个空节点，这一层其实就不要了
newLevel--
}
}
}
this.level = newLevel
return flag == 1
}
可以去 leetcode1206 跳表 测试代码逻辑正确性。
