数据结构 链表

时间：2021-09-08 17:33:33

参考：

1. Hbase 原理与实践 [跳跃表]

数据结构 链表

跳跃表

跳跃表是在链表的基础上进行扩展之后的一种数据结构。提高数据插入和删除的效率。

空间复杂度为 O(N)，时间复杂度为O(log(N))。

每层的一个元素有一个指向下一个元素的指针和一个指向下一层元素的指针。

|第五层|-| | | | |10|  |  |  |   |   |+|
|第四层|-| | | | |10|  |  |  |   |   |+|
|第三层|-| | | |9|10|  |  |  |100|   |+|
|第二层|-| |5| |9|10|  |15|  |100|   |+|
|第一层|-|1|5|8|9|10|11|15|19|100|101|+|

实现代码：

package algorithm

import (
    "crypto/rand"
    "encoding/binary"
    "math"
)

type Node struct {
    next   *Node
    bottom *Node
    value  int
}

type SkipList struct {
    height        int
    LevelHeadNode []*Node
    RandomFactor  float32
}

func NewSkipList() *SkipList {
    skipList := &SkipList{
        height:        1,
        LevelHeadNode: make([]*Node, 0),
        RandomFactor:  0.25,
    }
    skipList.init()
    return skipList
}

func (sl *SkipList) Exists(value int) bool {
    leftTopNode := sl.LevelHeadNode[sl.height-1]
    for {
        if leftTopNode.next.value > value {
            leftTopNode = leftTopNode.bottom
            if leftTopNode == nil {
                break
            }
        } else if leftTopNode.next.value == value {
            return true
        } else {
            leftTopNode = leftTopNode.next
        }
    }
    return false
}

func (sl *SkipList) Insert(value int) bool {
    if sl.Exists(value) {
        return false
    }

    //if value not exists
    pickHeight := pickHeight(sl.RandomFactor)
    sl.increaseHeight(pickHeight)

    newNodes := make([]*Node, pickHeight)
    for i := 0; i < pickHeight; i++ {
        newNodes[i] = newNode(value)
        if i > 0 {
            newNodes[i].bottom = newNodes[i-1]
        }
    }

    //find prev node in every level
    levelPrevNodes := make([]*Node, sl.height)
    leftTopNode := sl.LevelHeadNode[sl.height-1]
    levelPrevIndex := sl.height - 1
    for {
        if leftTopNode.next.value > value {
            levelPrevNodes[levelPrevIndex] = leftTopNode
            levelPrevIndex = levelPrevIndex - 1
            leftTopNode = leftTopNode.bottom
            if leftTopNode == nil {
                break
            }
        } else {
            leftTopNode = leftTopNode.next
        }
    }
    //update list for pick height
    for i := 0; i < pickHeight; i++ {
        newNodes[i].next = levelPrevNodes[i].next
        levelPrevNodes[i].next = newNodes[i]
    }
    return true
}

func (sl *SkipList) Remove(value int) bool {
    if !sl.Exists(value) {
        return false
    }

    //find prev node in every level
    levelPrevNodes := make([]*Node, sl.height)
    leftTopNode := sl.LevelHeadNode[sl.height-1]
    levelPrevIndex := sl.height - 1
    for {
        if leftTopNode.next.value >= value {
            levelPrevNodes[levelPrevIndex] = leftTopNode
            levelPrevIndex = levelPrevIndex - 1
            leftTopNode = leftTopNode.bottom
            if leftTopNode == nil {
                break
            }
        } else {
            leftTopNode = leftTopNode.next
        }
    }
    //update list for pick height
    for i := 0; i < sl.height; i++ {
        if levelPrevNodes[i].next.value == value {
            next := levelPrevNodes[i].next
            levelPrevNodes[i].next = levelPrevNodes[i].next.next
            next.next = nil
            next.bottom = nil
        }
    }
    return true
}

func (sl *SkipList) init() {
    sl.LevelHeadNode = append(sl.LevelHeadNode, newHeadAndTailList())
}

func (sl *SkipList) increaseHeight(pickHeight int) {
    if pickHeight > sl.height {
        for i := sl.height; i < pickHeight; i++ {
            head := newHeadAndTailList()
            head.bottom = sl.LevelHeadNode[i-1]
            sl.LevelHeadNode = append(sl.LevelHeadNode, head)
        }
        sl.height = pickHeight
    }
}

func pickHeight(randomFactor float32) int {
    height := 1
    bytes := make([]byte, 4)
    for {
        for read, _ := rand.Read(bytes); read != 4; {
        }
        if binary.BigEndian.Uint32(bytes)%100 < uint32(randomFactor*100) {
            height++
        } else {
            break
        }
    }
    return height
}

func newNode(value int) *Node {
    return &Node{
        value: value,
    }
}

func newHeadAndTailList() *Node {
    head := Node{
        value: math.MinInt32,
    }
    tail := Node{
        value: math.MaxInt32,
    }
    head.next = &tail
    return &head
}