```go
package main
import (
"fmt"
"math/rand"
)
var MAX_LEVEL int
type node struct {
key int
forward []*node
}
type SkipList struct {
lv int //level
hnode *node
}
func randomLevel() int {
return rand.Intn(10)
}
func init() {
MAX_LEVEL = 10
}
func createNode(lv int, kv int) *node {
return &node{
key: kv,
forward: make([]*node, lv, lv),
}
}
func createSkipList() *SkipList {
sl := new(SkipList)
sl.lv = 0
sl.hnode = createNode(MAX_LEVEL, 0)
//象征性得初始化下
// for i := 0; i < MAX_LEVEL; i++ {
// sl.hnode.forward[i] = nil
// }
return sl
}
func main() {
data := []int{1, 2, 3, 4, 5, 6, 7, 8}
fmt.Println("skip list", data)
sl := createSkipList()
fmt.Println(sl, sl.hnode.forward)
for i := 0; i < 10; i++ {
insert(sl, i)
}
fmt.Println(search(sl, 11))
fmt.Println(search(sl, 1))
fmt.Println(delete(sl, 1))
fmt.Println(search(sl, 1))
}
func insert(sl *SkipList, kv int) bool {
var p, q *node
//var update []*node
update := make([]*node, MAX_LEVEL, MAX_LEVEL)
p = sl.hnode
k := sl.lv
for i := k - 1; i >= 0; i-- { //loop level
for p != nil && p.forward[i] != nil && p.forward[i].key < kv {
p = p.forward[i]
}
update[i] = p
}
if p != nil && p.key == kv {
return false
}
k = randomLevel()
//update hnode forword pointer
if k > sl.lv {
for i := sl.lv; i < k; i++ {
update[i] = sl.hnode
}
sl.lv = k
}
q = createNode(k, kv)
for i := 0; i < k; i++ {
if update[i] != nil {
q.forward[i] = update[i].forward[i]
update[i].forward[i] = q
} else {
}
}
return true
}
func delete(sl *SkipList, kv int) bool {
update := make([]*node, MAX_LEVEL, MAX_LEVEL)
p := sl.hnode
for i := sl.lv - 1; i >= 0; i-- {
for p != nil && p.forward[i] != nil && p.forward[i].key < kv {
p = p.forward[i]
}
update[i] = p
}
if p.forward != nil && p.forward[0].key != kv {
return false
}
deleteN := p.forward[0]
for i := sl.lv - 1; i >= 0; i-- {
if update[i] != nil && update[i].forward[i] == deleteN {
update[i].forward[i] = deleteN.forward[i]
if sl.hnode.forward[i] == nil {
sl.lv--
}
}
}
return true
}
func search(sl *SkipList, kv int) int {
var q *node
q = sl.hnode
for i := sl.lv - 1; i >= 0; i-- {
for q != nil && q.forward[i] != nil && q.forward[i].key <= kv {
if q.forward[i].key == kv {
return q.forward[i].key
}
q = q.forward[i]
}
}
return -1
}
```
所有代码在GitHub上，喜欢得golanger 自己拉
https://github.com/godla/golang-sort-data-structures-study
一起每天写一点吧^.^
有疑问加站长微信联系（非本文作者）
