# golang skiplist(跳表)实现

l刘言飞语 · · 422 次点击 · · 开始浏览

# 跳表

1.png

so ，跳表 = 链表 + 有序 + 概率分层

`ps:head 节点为左上第一个节点，tail 节点为右上第一个节点`

Insert：插入15，首先找到离15最近，比15小的节点12，然后将节点插入底层（单链表的插入操作）。判断是否需要分层，不需要返回。需要的话自底向上一层一层插入节点

Remove：同样的删除15，首先找到离15最近，比15小的节点12，然后将节点在底层删除，如果有上层节点，继续删除。

talk is cheap，show you the code：

``````package skipList

import (
"fmt"
"math"
"math/rand"
"time"
)

const UP_LEVELS_ABILITY = 500
const UP_LEVELS_TOTAL = 1000

type skipListNode struct {
score int64
val   interface{}
next  *skipListNode
pre   *skipListNode
up    *skipListNode
down  *skipListNode
}

type skipList struct {
tail   *skipListNode
size   int
levels int
}

func NewSkipList() *skipList {
sl := new(skipList)
sl.tail = new(skipListNode)
sl.tail.score = math.MaxInt64

sl.size = 0
sl.levels = 1

return sl
}

func (sl *skipList) Size() int {
return sl.size
}

func (sl *skipList) Levels() int {
return sl.levels
}

func (sl *skipList) Get(score int64) interface{} {
node := sl.findNode(score)
if node.score == score {
return node.val
} else {
return nil
}
}

func (sl *skipList) Insert(score int64, val interface{}) {
f := sl.findNode(score)
if f.score == score {
f.val = val
return
}
curNode := new(skipListNode)
curNode.score = score
curNode.val = val

sl.insertAfter(f, curNode)

rander := rand.New(rand.NewSource(time.Now().UnixNano()))

curlevels := 1
for rander.Intn(UP_LEVELS_TOTAL) < UP_LEVELS_ABILITY {
curlevels++
if curlevels > sl.levels {
sl.newlevels()
}

for f.up == nil {
f = f.pre
}
f = f.up
tmpNode := &skipListNode{score: score}

curNode.up = tmpNode
tmpNode.down = curNode
sl.insertAfter(f, tmpNode)

curNode = tmpNode
}

sl.size++
}

func (sl *skipList) Remove(score int64) interface{} {
f := sl.findNode(score)
if f.score != score {
return nil
}
v := f.val

for f != nil {
f.pre.next = f.next
f.next.pre = f.pre
f = f.up
}
return v
}

func (sl *skipList) newlevels() {
nhead := &skipListNode{score: math.MinInt64}
ntail := &skipListNode{score: math.MaxInt64}

sl.tail.up = ntail
ntail.down = sl.tail

sl.tail = ntail
sl.levels++
}

func (sl *skipList) insertAfter(pNode *skipListNode, curNode *skipListNode) {
curNode.next = pNode.next
curNode.pre = pNode
pNode.next.pre = curNode
pNode.next = curNode
}

func (sl *skipList) findNode(score int64) *skipListNode {

for p != nil {
if p.score == score {
if p.down == nil {
return p
}
p = p.down
} else if p.score < score {
if p.next.score > score {
if p.down == nil {
return p
}
p = p.down
} else {
p = p.next
}
}
}
return p
}

func (sl *skipList) Print() {

mapScore := make(map[int64]int)

for p.down != nil {
p = p.down
}
index := 0
for p != nil {
mapScore[p.score] = index
p = p.next
index++
}
for i := 0; i < sl.levels; i++ {
q := p
preIndex := 0
for q != nil {
s := q.score
if s == math.MinInt64 {
fmt.Printf("%s", "BEGIN")
q = q.next
continue
}
index := mapScore[s]
c := (index - preIndex - 1) * 6
for m := 0; m < c; m++ {
fmt.Print("-")
}
if s == math.MaxInt64 {
fmt.Printf("-->%s\n", "END")
} else {
fmt.Printf("-->%3d", s)
preIndex = index
}
q = q.next
}
p = p.down
}
}
``````

``````package main

import (
"skipList"
)

func main() {
sk := skipList.NewSkipList()

sk.Insert(100, "lala")
sk.Insert(11, "sx")
sk.Insert(22, "11")
sk.Insert(3, "dd")
sk.Insert(80, "bb")
sk.Insert(77, "bb")
sk.Insert(6, "bb")
sk.Insert(88, "bb")
sk.Insert(33, "bb")
sk.Insert(44, "bb")

//fmt.Println(sk.Get(22))
//fmt.Println(sk.Get(55))
//fmt.Println(sk.Remove(22))
//fmt.Println(sk.Get(22))
//fmt.Println(sk.Size())
//fmt.Println(sk.Layout())
sk.Print()
}
``````
2.png

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

# 跳表

1.png

so ，跳表 = 链表 + 有序 + 概率分层

`ps:head 节点为左上第一个节点，tail 节点为右上第一个节点`

Insert：插入15，首先找到离15最近，比15小的节点12，然后将节点插入底层（单链表的插入操作）。判断是否需要分层，不需要返回。需要的话自底向上一层一层插入节点

Remove：同样的删除15，首先找到离15最近，比15小的节点12，然后将节点在底层删除，如果有上层节点，继续删除。

talk is cheap，show you the code：

``````package skipList

import (
"fmt"
"math"
"math/rand"
"time"
)

const UP_LEVELS_ABILITY = 500
const UP_LEVELS_TOTAL = 1000

type skipListNode struct {
score int64
val   interface{}
next  *skipListNode
pre   *skipListNode
up    *skipListNode
down  *skipListNode
}

type skipList struct {
tail   *skipListNode
size   int
levels int
}

func NewSkipList() *skipList {
sl := new(skipList)
sl.tail = new(skipListNode)
sl.tail.score = math.MaxInt64

sl.size = 0
sl.levels = 1

return sl
}

func (sl *skipList) Size() int {
return sl.size
}

func (sl *skipList) Levels() int {
return sl.levels
}

func (sl *skipList) Get(score int64) interface{} {
node := sl.findNode(score)
if node.score == score {
return node.val
} else {
return nil
}
}

func (sl *skipList) Insert(score int64, val interface{}) {
f := sl.findNode(score)
if f.score == score {
f.val = val
return
}
curNode := new(skipListNode)
curNode.score = score
curNode.val = val

sl.insertAfter(f, curNode)

rander := rand.New(rand.NewSource(time.Now().UnixNano()))

curlevels := 1
for rander.Intn(UP_LEVELS_TOTAL) < UP_LEVELS_ABILITY {
curlevels++
if curlevels > sl.levels {
sl.newlevels()
}

for f.up == nil {
f = f.pre
}
f = f.up
tmpNode := &skipListNode{score: score}

curNode.up = tmpNode
tmpNode.down = curNode
sl.insertAfter(f, tmpNode)

curNode = tmpNode
}

sl.size++
}

func (sl *skipList) Remove(score int64) interface{} {
f := sl.findNode(score)
if f.score != score {
return nil
}
v := f.val

for f != nil {
f.pre.next = f.next
f.next.pre = f.pre
f = f.up
}
return v
}

func (sl *skipList) newlevels() {
nhead := &skipListNode{score: math.MinInt64}
ntail := &skipListNode{score: math.MaxInt64}

sl.tail.up = ntail
ntail.down = sl.tail

sl.tail = ntail
sl.levels++
}

func (sl *skipList) insertAfter(pNode *skipListNode, curNode *skipListNode) {
curNode.next = pNode.next
curNode.pre = pNode
pNode.next.pre = curNode
pNode.next = curNode
}

func (sl *skipList) findNode(score int64) *skipListNode {

for p != nil {
if p.score == score {
if p.down == nil {
return p
}
p = p.down
} else if p.score < score {
if p.next.score > score {
if p.down == nil {
return p
}
p = p.down
} else {
p = p.next
}
}
}
return p
}

func (sl *skipList) Print() {

mapScore := make(map[int64]int)

for p.down != nil {
p = p.down
}
index := 0
for p != nil {
mapScore[p.score] = index
p = p.next
index++
}
for i := 0; i < sl.levels; i++ {
q := p
preIndex := 0
for q != nil {
s := q.score
if s == math.MinInt64 {
fmt.Printf("%s", "BEGIN")
q = q.next
continue
}
index := mapScore[s]
c := (index - preIndex - 1) * 6
for m := 0; m < c; m++ {
fmt.Print("-")
}
if s == math.MaxInt64 {
fmt.Printf("-->%s\n", "END")
} else {
fmt.Printf("-->%3d", s)
preIndex = index
}
q = q.next
}
p = p.down
}
}
``````

``````package main

import (
"skipList"
)

func main() {
sk := skipList.NewSkipList()

sk.Insert(100, "lala")
sk.Insert(11, "sx")
sk.Insert(22, "11")
sk.Insert(3, "dd")
sk.Insert(80, "bb")
sk.Insert(77, "bb")
sk.Insert(6, "bb")
sk.Insert(88, "bb")
sk.Insert(33, "bb")
sk.Insert(44, "bb")

//fmt.Println(sk.Get(22))
//fmt.Println(sk.Get(55))
//fmt.Println(sk.Remove(22))
//fmt.Println(sk.Get(22))
//fmt.Println(sk.Size())
//fmt.Println(sk.Layout())
sk.Print()
}
``````
2.png