跳跃表入门
跳跃表这个货色，始终在据说，但从未手动实现过，所以了解的也不是很透彻。最近闲来无事，用golang实现了一个根底版本，加深一下了解。
跳跃表的逻辑构造如下：
这里不解释根底原理了，网上大把的材料，总结几点加深了解：
- 跳跃表的底层还是链表，而且是有序链表，在结构跳跃表的时候就必须保证数据有序；
- 跳跃表用的是空间换工夫的思维；
- 有点相似有序数组的二分查找;
- 跳表的查问，插入和删除操作的冀望工夫复杂度都为 O(logN);
代码实现
跳跃表的实现并不固定，能够有很多不同的版本，我这里仅实现了一个根底版本，并没有各种优化操作。
根底构造：
// 单个节点type SkipNode struct { Val int Level int Nexts []*SkipNode}// 跳跃表type SkipList struct { Head *SkipNode //Tail *SkipNode MaxLevel int}源码：
package mainimport ( "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 < val { currNode = currNode.Nexts[i] } if currNode.Nexts[i] != nil && currNode.Nexts[i].Val == val { return errors.New("same item") } preNodes[i] = currNode } // 创立新节点 node := new(SkipNode) node.Val = val node.Level = obj.GetNodeLevel() node.Nexts = make([]*SkipNode, node.Level, node.Level) for i := 0; i < node.Level; i++ { if i < obj.Head.Level { node.Nexts[i] = preNodes[i].Nexts[i] preNodes[i].Nexts[i] = node } else { node.Nexts[i] = nil obj.Head.Nexts = append(obj.Head.Nexts, node) } } obj.Head.Level = len(obj.Head.Nexts) return nil}// 查找跳表func (obj *SkipList) find(val int) *SkipNode { currNode := obj.Head // 查找定位地位 for i := obj.Head.Level - 1; i >= 0; i-- { for currNode.Nexts[i] != nil && currNode.Nexts[i].Val < val { currNode = currNode.Nexts[i] } if currNode.Nexts[i] != nil && currNode.Nexts[i].Val == val { return currNode.Nexts[i] } } return nil}// 删除节点func (obj *SkipList) del(val int) { 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 < val { currNode = currNode.Nexts[i] } if currNode.Nexts[i] != nil && currNode.Nexts[i].Val == val { preNodes[i] = currNode } } // 删除节点 for i := 0; i < obj.Head.Level; i++ { if preNodes[i] == nil { continue } preNodes[i].Nexts[i] = preNodes[i].Nexts[i].Nexts[i] }}// 打印跳表func (obj *SkipList) printf() { fmt.Println("skip list:") node := obj.Head for i := obj.Head.Level - 1; i >= 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) }}运行后果如下：