关于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 < 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)
    }
}

运行后果如下：

关于golang:基础版跳跃表实现golang

跳跃表入门

代码实现