跳表(skiplist)在redis/levelDB中屬於核心數據結構,我簡單粗暴的用Golang實現了下。
就我的簡單理解來說，就一個普通的鏈表，在insert時，通過Random_level(),把一層變成很多層，
越上數據越小，跨度越大。 查找時從上往下找，用空間換時間。
記下測試代碼:
package main
import (
"fmt"
//"github.com/xclpkg/algorithm"
"math/rand"
)
func main() {
slt := NewSkipList()
for i := 100; i > 0; i-- {
slt.Insert(i)
}
slt.PrintSkipList()
slt.Search(20)
slt.Search(36)
slt.Search(93)
slt.Delete(55)
slt.PrintSkipList()
}
const SKIPLIST_MAXLEVEL = 8 //32
const SKIPLIST_P = 4
type SkipList struct {
Header []List
Level int
}
func NewSkipList() *SkipList {
return &SkipList{Level: 1, Header: make([]List, SKIPLIST_MAXLEVEL)}
}
func (skipList *SkipList) Insert(key int) {
update := make(map[int]*Node)
for i := len(skipList.Header) - 1; i >= 0; i-- {
if skipList.Header[i].Len() > 0 {
for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
if e.Value.(int) >= key {
update[i] = e
break
}
}
} //Heaer[lv].List
} //Header Level
level := skipList.Random_level()
if level > skipList.Level {
skipList.Level = level
}
for i := 0; i < level; i++ {
if v, ok := update[i]; ok {
skipList.Header[i].InsertBefore(key, v)
} else {
skipList.Header[i].PushBack(key)
}
}
}
func (skipList *SkipList) Search(key int) *Node {
for i := len(skipList.Header) - 1; i >= 0; i-- {
if skipList.Header[i].Len() > 0 {
for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
switch {
case e.Value.(int) == key:
fmt.Println("Found level=", i, " key=", key)
return e
case e.Value.(int) > key:
break
}
} //end for
} //end if
} //end for
return nil
}
func (skipList *SkipList) Delete(key int) {
for i := len(skipList.Header) - 1; i >= 0; i-- {
if skipList.Header[i].Len() > 0 {
for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
switch {
case e.Value.(int) == key:
fmt.Println("Delete level=", i, " key=", key)
skipList.Header[i].remove(e)
case e.Value.(int) > key:
break
}
} //end for
} //end if
} //end for
}
func (skipList *SkipList) PrintSkipList() {
fmt.Println("\nSkipList-------------------------------------------")
for i := SKIPLIST_MAXLEVEL - 1; i >= 0; i-- {
fmt.Println("level:", i)
if skipList.Header[i].Len() > 0 {
for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
fmt.Printf("%d ", e.Value)
} //end for
} //end if
fmt.Println("\n--------------------------------------------------------")
} //end for
}
func (skipList *SkipList) Random_level() int {
level := 1
for (rand.Int31()&0xFFFF)%SKIPLIST_P == 0 {
level += 1
}
if level < SKIPLIST_MAXLEVEL {
return level
} else {
return SKIPLIST_MAXLEVEL
}
}
//////////////////////////////////////////////////////
type Node struct {
next, prev *Node
list *List
Value interface{}
}
type List struct {
root Node
len int
}
func (node *Node) Next() *Node {
if p := node.next; node.list != nil && p != &node.list.root {
return p
}
return nil
}
func (node *Node) Prev() *Node {
if p := node.prev; node.list != nil && p != &node.list.root {
return p
}
return nil
}
func (list *List) Init() *List {
list.root.next = &list.root
list.root.prev = &list.root
list.len = 0
return list
}
func New() *List {
return new(List).Init()
}
func (list *List) lazyInit() {
if list.root.next == nil {
list.Init()
}
}
func (list *List) Len() int {
return list.len
}
func (list *List) remove(e *Node) *Node {
e.prev.next = e.next
e.next.prev = e.prev
e.next = nil
e.prev = nil
e.list = nil
list.len--
return e
}
func (list *List) Remove(e *Node) interface{} {
if e.list == list {
list.remove(e)
}
return e.Value
}
func (list *List) Front() *Node {
if list.len == 0 {
return nil
}
return list.root.next
}
func (list *List) Back() *Node {
if list.len == 0 {
return nil
}
return list.root.prev
}
func (list *List) insert(e, at *Node) *Node {
n := at.next
at.next = e
e.prev = at
e.next = n
n.prev = e
e.list = list
list.len++
return e
}
func (list *List) insertValue(v interface{}, at *Node) *Node {
return list.insert(&Node{Value: v}, at)
}
func (list *List) InsertBefore(v interface{}, mark *Node) *Node {
if mark.list != list {
return nil
}
return list.insertValue(v, mark.prev)
}
func (list *List) PushBack(v interface{}) *Node {
list.lazyInit()
return list.insertValue(v, list.root.prev)
}
效果:
SkipList------------------------------------------- level: 7 -------------------------------------------------------- level: 6 -------------------------------------------------------- level: 5 -------------------------------------------------------- level: 4 -------------------------------------------------------- level: 3 93 -------------------------------------------------------- level: 2 36 93 -------------------------------------------------------- level: 1 6 10 22 23 25 36 42 47 48 54 55 61 72 75 78 82 89 93 -------------------------------------------------------- level: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 5 7 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 -------------------------------------------------------- Found level= 0 key= 20 Found level= 2 key= 36 Found level= 3 key= 93 Delete level= 1 key= 55 Delete level= 0 key= 55 SkipList------------------------------------------- level: 7 -------------------------------------------------------- level: 6 -------------------------------------------------------- level: 5 -------------------------------------------------------- level: 4 -------------------------------------------------------- level: 3 93 -------------------------------------------------------- level: 2 36 93 -------------------------------------------------------- level: 1 6 10 22 23 25 36 42 47 48 54 61 72 75 78 82 89 93 -------------------------------------------------------- level: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 56 57 5 8 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 --------------------------------------------------------搞定。
