概述
首先来了解一下跳表的概念，跳表中的表指的是链表，所以宏观上来看跳表是一种链表结构，那么它与传统的链表有什么不同呢？一般的单链表如果我们需要查找第n个元素，那么就需要从头节点开始一个一个的遍历n次，时间复杂读就是O(n)，而跳表就是在单链表之上做了一些优化，使时间复杂度达到O(logn)。
在O(logn)复杂度内查找元素，我们不难想到其他的数据结构，avl树，红黑树，b树，b+树之类。但是这些树状结构有个共性就是需要在元素数量发生变化的时候保持平衡才能继续维持性能，所以就需要做一个额外的操作，旋转。而旋转一方面增加了代码实现的复杂性，同时也降低了在频繁做增删操作时，树的性能。
<br />跳表的结构如上图所示，可以看到跳表是分层的链表，底层是真正保存的数据，传统的单链表，而之上的层可以理解为下层节点的索引。所以这也是典型的空间换时间的优化方式。
查询
首先需要明确一点，索引不存数据，数据是在总底层
以找9为例子：
- head < 9，找head的下个节点a
- a == 9 ，需要判断 a 有没下沉节点，如果有，走到b
- b == 9 ，需要判断 b 有没下沉节点，如果有，走到c
- c == 9 ，需要判断 c 有没下沉节点，如果没有，返回节点c
以找20为例子：
查找应该分两步，就算没找到匹配的，也要返回 离查找节点最近的一个节点
- head < 20，找head的下个节点a
- a < 20，判断a1 < 20 ，否，a节点下沉，到达b
- b < 20, 判断c < 20 ， 是，c节点下沉，到达d
- d < 20，判断e < 20，是，e没下层节点，找到 21
- 21 > 20，因此判断，20在链表中不存在，返回 节点e
```go
// Get 查询节点
func (sl *skipList) Get(score int64) interface{} {
node := sl.findNode(score)
if node.score == score {
} else {return node.val
} }return nil
func (sl skipList) findNode(score int64) skipListNode { p := sl.head
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 { // 如果p的下一个节点大于score, 那么p下沉
if p.down == nil { // 要找的score，不在跳表里，返回比score小的最近的一个节点
return p
}
p = p.down
} else {
p = p.next // 如果p的下一个节点不大于score, 那么p变为p的下一个节点
}
}
}
return p
}
<a name="rIRZu"></a>
### 插入
例如：x节点 是新插入的<br />
- 找到节点a,向节点a的后面插入x
- 跑硬币，决定x 是否需要建立上层节点，如果是
- 找到节点a，发现a 没有上层节点，因此找到b
- b 上行，得到节点c
- 在c的后面添加节点d
- 将x 与 d 之间建立关系
- 再抛硬币，决定节点d 是否需要建立上层节点.....
```go
// Insert 插入节点
func (sl *skipList) Insert(score int64, val interface{}) {
f := sl.findNode(score) // 找到与score最近的节点，找到的节点必须 <= 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
// 抛硬币，50%可能性需要往上一层建立索引
for rander.Intn(2) < 1 && sl.Levels() < MAX_LEVEL {
curlevels++
if curlevels > sl.levels {
sl.newlevels()
}
// 如果f没有上层节点，那么就找f节点的上一个节点的上层节点
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) newlevels() {
nhead := &skipListNode{score: math.MinInt64}
ntail := &skipListNode{score: math.MaxInt64}
nhead.next = ntail
ntail.pre = nhead
// 新的一层与老的一层建立关系
sl.head.up = nhead
nhead.down = sl.head
sl.tail.up = ntail
ntail.down = sl.tail
// 更新sl，将新的一层的头与尾，作为整体的头和尾
sl.head = nhead
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) 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
}
实现
package main
import (
"fmt"
"math"
"math/rand"
"time"
)
const MAX_LEVEL = 10 // 最多10层
type skipListNode struct {
score int64 // 分值
val interface{} // 数据，只有最底层的链表才存数据
next *skipListNode // 下一个节点
pre *skipListNode // 上一个节点
up *skipListNode // 上行节点
down *skipListNode // 下行节点
}
type skipList struct {
head *skipListNode
tail *skipListNode
size int
levels int
}
func NewSkipList() *skipList {
sl := new(skipList)
sl.head = new(skipListNode)
sl.tail = new(skipListNode)
sl.head.score = math.MinInt64
sl.tail.score = math.MaxInt64
sl.head.next = sl.tail
sl.tail.pre = sl.head
sl.size = 0
sl.levels = 1
return sl
}
func (sl *skipList) Size() int {
return sl.size
}
func (sl *skipList) Levels() int {
return sl.levels
}
// Get 查询节点
func (sl *skipList) Get(score int64) interface{} {
node := sl.findNode(score)
if node.score == score {
return node.val
} else {
return nil
}
}
func (sl *skipList) findNode(score int64) *skipListNode {
p := sl.head
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 { // 如果p的下一个节点大于score, 那么p下沉
if p.down == nil { // 要找的score，不在跳表里，返回比score小的最近的一个节点
return p
}
p = p.down
} else {
p = p.next // 如果p的下一个节点不大于score, 那么p变为p的下一个节点
}
}
}
return p
}
// Insert 插入节点
func (sl *skipList) Insert(score int64, val interface{}) {
f := sl.findNode(score) // 找到与score最近的节点，找到的节点必须 <= 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
// 抛硬币，50%可能性需要往上一层建立索引
for rander.Intn(2) < 1 && sl.Levels() < MAX_LEVEL {
curlevels++
if curlevels > sl.levels {
sl.newlevels()
}
// 如果f没有上层节点，那么就找f节点的上一个节点的上层节点
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) newlevels() {
nhead := &skipListNode{score: math.MinInt64}
ntail := &skipListNode{score: math.MaxInt64}
nhead.next = ntail
ntail.pre = nhead
// 新的一层与老的一层建立关系
sl.head.up = nhead
nhead.down = sl.head
sl.tail.up = ntail
ntail.down = sl.tail
// 更新sl，将新的一层的头与尾，作为整体的头和尾
sl.head = nhead
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) 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) Print() {
mapScore := make(map[int64]int)
p := sl.head
for p.down != nil {
p = p.down
}
index := 0
for p != nil {
mapScore[p.score] = index
p = p.next
index++
}
p = sl.head
for i := 0; i < sl.levels; i++ {
q := p
preIndex := 0 // preIndex代表已经打印到该下标了，默认为0是因为 第一个节点比较特殊，它是BEGIN
for q != nil {
s := q.score
if s == math.MinInt64 {
fmt.Printf("%s", "BEGIN")
q = q.next
continue
}
index := mapScore[s] // index为该Score在最底层链表的下标
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
}
}
func main() {
sk := 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")
sk.Print()
}
若有收获，就点个赞吧
0 人点赞
