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
57
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
const MaxLevel = 16
// 链表节点结构
type SkipListNode struct {
v interface{} // 存储值
score int // 存储 score
forwards []*SkipListNode // 下一个节点的指针，注意，这个是一个纵向的数组。
}
// 链表结构
type SkipList struct {
head *SkipListNode // 最高层的第一个节点指针
level int // 层高
length int // 元素个数
}
func NewSkipListNode(v interface{}, score int, level int) *SkipListNode {
return &SkipListNode{
v: v,
score: score,
forwards: make([]*SkipListNode, level, level),
}
}
func NewSipList() *SkipList {
head := NewSkipListNode(0, math.MinInt32, MaxLevel)
return &SkipList{
head: head,
level: 0,
length: 0,
}
}
func (l *SkipList) Length() int {
return l.length
}
func (l *SkipList) Level() int {
return l.level
}
func (l *SkipList) Insert(v interface{}, score int) (bool, error) {
// 不能为空
if v == nil {
return false, errors.New("value is nil")
}
node := l.head
// 构造出每一层的前置节点
everyLevelPrevNodeList := [MaxLevel]*SkipListNode{}
for i := MaxLevel - 1; i >= 0; i-- {
for node.forwards[i] != nil {
if node.forwards[i].v == v {
return false, errors.New("value is exist")
}
if node.forwards[i].score > score {
everyLevelPrevNodeList[i] = node
break
}
node = node.forwards[i]
}
if node.forwards[i] == nil {
everyLevelPrevNodeList[i] = node
}
}
// 计算层数
level := 1
for i := 1; i < MaxLevel; i++ {
if rand.Int31() % 7 == 0 {
level++
}
}
// 设置新层高
if level > l.level {
l.level = level
}
// 构造新节点
newNode := NewSkipListNode(v, score, level)
for i := 0; i < level; i++ {
nextNode := everyLevelPrevNodeList[i].forwards[i]
everyLevelPrevNodeList[i].forwards[i] = newNode
newNode.forwards[i] = nextNode
}
return true,nil
}
func (l *SkipList) Find(score int) (interface{}, error) {
node := l.head
for i := l.level - 1; i >= 0; i-- {
for node.forwards[i] != nil {
if node.score == score {
return node.v, nil
} else if node.forwards[i].score > score {
break
}
node = node.forwards[i]
}
}
return nil, errors.New("not Found")
}
func (l *SkipList) Delete(score int) (interface{}, error) {
node := l.head
fmt.Println(node)
var val interface{}
// 构造出每一层的前置节点
everyLevelPrevNodeList := [MaxLevel]*SkipListNode{}
for i := MaxLevel - 1; i >= 0; i-- {
everyLevelPrevNodeList[i] = l.head
for node.forwards[i] != nil {
if node.forwards[i].score == score {
everyLevelPrevNodeList[i] = node
val = node.forwards[i].v
break
} else if node.forwards[i].score > score {
break
}
node = node.forwards[i]
}
}
// 删
isDel := false
for i := 0; i < l.level; i++ {
if everyLevelPrevNodeList[i].forwards[i] != nil {
everyLevelPrevNodeList[i].forwards[i] = everyLevelPrevNodeList[i].forwards[i].forwards[i]
isDel = true
}
}
if isDel {
l.length--
if l.head.forwards[l.level - 1] == nil {
l.level--
}
return val, nil
}
return val, errors.New("not Found")
}
func (l *SkipList) Print() {
for i := l.level - 1; i >= 0; i-- {
node := l.head.forwards[i]
for node != nil {
fmt.Print("v:", node.v, "s:", node.score, " -> ")
node = node.forwards[i]
}
fmt.Println()
}
}
|