作者:跟-着感觉走 | 来源:互联网 | 2023-02-12 14:22
基础版跳跃表实现(golang)-跳跃表入门跳跃表这个东西,一直在听说,但从未手动实现过,所以理解的也不是很透彻。最近闲来无事,用golang实现了一个基础版本,加深一下理解。跳跃
跳跃表入门
跳跃表这个东西,一直在听说,但从未手动实现过,所以理解的也不是很透彻。最近闲来无事,用golang实现了一个基础版本,加深一下理解。
跳跃表的逻辑结构如下:
这里不解释基础原理了,网上大把的资料,总结几点加深理解:
- 跳跃表的底层还是链表,而且是有序链表,在构造跳跃表的时候就必须保证数据有序;
- 跳跃表用的是空间换时间的思想;
- 有点类似有序数组的二分查找;
- 跳表的查询,插入和删除操作的期望时间复杂度都为 O(logN);
代码实现
跳跃表的实现并不固定,可以有很多不同的版本,我这里仅实现了一个基础版本,并没有各种优化操作。
基础结构:
// 单个节点
type SkipNode struct {
Val int
Level int
Nexts []*SkipNode
}
// 跳跃表
type SkipList struct {
Head *SkipNode
//Tail *SkipNode
MaxLevel int
}
源码:
package main
import (
"errors"
"fmt"
"math/rand"
"time"
)
// 单个节点
type SkipNode struct {
Val int
Level int
Nexts []*SkipNode
}
// 跳跃表
type SkipList struct {
Head *SkipNode
//Tail *SkipNode
MaxLevel int
}
// 初始化
func (obj *SkipList) Init(maxLevel int) {
obj.MaxLevel = maxLevel
head := new(SkipNode)
head.Level = 1
head.Val = -99999
head.Nexts = make([]*SkipNode, 1, maxLevel)
obj.Head = head
}
// 获取新节点的最大层数
func (obj *SkipList) GetNodeLevel() int {
level := 1
for rand.Intn(2) == 1 {
level++
if obj.MaxLevel <= level {
break
}
}
return level
}
// 插入节点
func (obj *SkipList) insert(val int) error {
preNodes := make([]*SkipNode, obj.Head.Level, obj.Head.Level)
currNode := obj.Head
// 查找定位位置
for i := obj.Head.Level - 1; i >= 0; i-- {
for currNode.Nexts[i] != nil && currNode.Nexts[i].Val = 0; i-- {
for currNode.Nexts[i] != nil && currNode.Nexts[i].Val = 0; i-- {
for currNode.Nexts[i] != nil && currNode.Nexts[i].Val = 0; i-- {
fmt.Printf(" skip list level %d: ", i)
tmpNode := node.Nexts[i]
for tmpNode != nil {
fmt.Printf("%d->", tmpNode.Val)
tmpNode = tmpNode.Nexts[i]
}
fmt.Println("\b\b ")
}
}
// 构造
func (obj *SkipList) build() {
for i := 1; i <70; i += 2 {
obj.insert(i)
}
}
func main() {
rand.Seed(time.Now().UnixNano())
skipObj := SkipList{}
skipObj.Init(10)
skipObj.build()
skipObj.printf()
err := skipObj.insert(3)
if err != nil {
fmt.Printf("insert 3 failed, %s\n", err.Error())
}
res := skipObj.find(37)
if res == nil {
fmt.Printf("not found 37\n")
} else {
fmt.Printf("found 37, %+v\n", res)
}
skipObj.del(37)
skipObj.del(33)
skipObj.del(4)
skipObj.printf()
res = skipObj.find(37)
if res == nil {
fmt.Printf("not found 37\n")
} else {
fmt.Printf("found 37, %+v\n", res)
}
}
运行结果如下: