跳表的定義

跳表(SkipList)：增加了向前指針的鏈表叫做跳表顶瞳。跳表全稱叫做跳躍表贬芥，簡稱跳表。跳表是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)妒蔚，實(shí)質(zhì)是一種可以進(jìn)行近似二分查找的有序鏈表。跳表在原有的有序鏈表上增加了多級(jí)索引月弛，通過索引來實(shí)現(xiàn)快速查詢肴盏。跳表不僅能提高搜索性能，同時(shí)也可以提高插入和刪除操作的性能帽衙。

跳表的詳解

有序原始鏈表

image.png

那么我們可以由此得到啟發(fā)田轧，和上面建立第一級(jí)索引的方式相似冷蚂，在第一級(jí)索引的基礎(chǔ)上，每兩個(gè)一級(jí)索引結(jié)點(diǎn)就抽到一個(gè)結(jié)點(diǎn)到第二級(jí)索引中醉冤。再來查找值為16的結(jié)點(diǎn)卫袒，只需要遍歷6個(gè)結(jié)點(diǎn)即可宵呛，從而進(jìn)一步提高了查找效率。

跳表的時(shí)間復(fù)雜度

單鏈表的查找時(shí)間復(fù)雜度為：O(n)夕凝，
下面分析下跳表這種數(shù)據(jù)結(jié)構(gòu)的查找時(shí)間復(fù)雜度：
我們首先考慮這樣一個(gè)問題宝穗，如果鏈表里有n個(gè)結(jié)點(diǎn)，那么會(huì)有多少級(jí)索引呢码秉？按照上面講的逮矛，每兩個(gè)結(jié)點(diǎn)都會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)。那么第一級(jí)索引的個(gè)數(shù)大約就是n/2转砖，第二級(jí)的索引大約就是n/4须鼎，第三級(jí)的索引就是n/8鲸伴，依次類推，也就是說晋控，第k級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第k-1級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的1/2汞窗，那么第k級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)為n/(2k)。

赡译、】
`
假設(shè)索引有h級(jí)仲吏，最高級(jí)的索引有2個(gè)結(jié)點(diǎn)，通過上面的公式蝌焚，我們可以得到裹唆，從而可得：h =log2n-1。如果包含原始鏈表這一層只洒，整個(gè)跳表的高度就是许帐。我們?cè)谔碇胁檎夷硞€(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷m個(gè)結(jié)點(diǎn)红碑，那么在跳表中查詢一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就為O(m*logn)舞吭。

其實(shí)根據(jù)前面的分析，我們不難得出m=3析珊，即每一級(jí)索引都最多只需要遍歷3個(gè)結(jié)點(diǎn)羡鸥，分析如下：

時(shí)間復(fù)雜度分析

如上圖所示，假如我們要查找的數(shù)據(jù)是x忠寻，在第k級(jí)索引中惧浴，我們遍歷到y(tǒng)結(jié)點(diǎn)之后，發(fā)現(xiàn)x大于y奕剃，小于y后面的結(jié)點(diǎn)z衷旅。所以我們通過y的down指針，從第k級(jí)索引下降到第k-1級(jí)索引纵朋。在第k-1級(jí)索引中柿顶，y和z之間只有3個(gè)結(jié)點(diǎn)(包含y和z)。所以操软，我們?cè)趉-1級(jí)索引中最多需要遍歷3個(gè)結(jié)點(diǎn)嘁锯，以此類推，每一級(jí)索引都最多只需要遍歷3個(gè)結(jié)點(diǎn)聂薪。

因此家乘，m=3，所以跳表查找任意數(shù)據(jù)的時(shí)間復(fù)雜度為O(logn)藏澳，這個(gè)查找的時(shí)間復(fù)雜度和二分查找是一樣的仁锯，但是我們卻是基于單鏈表這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。不過翔悠，天下沒有免費(fèi)的午餐业崖，這種查找效率的提升是建立在很多級(jí)索引之上的野芒，即空間換時(shí)間的思想。其具體空間復(fù)雜度見下文詳解腻要。

跳表的空間復(fù)雜度

比起單純的單鏈表复罐，跳表就需要額外的存儲(chǔ)空間去存儲(chǔ)多級(jí)索引。假設(shè)原始鏈表的大小為n雄家，那么第一級(jí)索引大約有n/2個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有4/n個(gè)結(jié)點(diǎn)胀滚，依次類推趟济，每上升一級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就減少一半，直到剩下最后2個(gè)結(jié)點(diǎn)咽笼，如下圖所示顷编，其實(shí)就是一個(gè)等比數(shù)列。

空間復(fù)雜度

這幾級(jí)索引結(jié)點(diǎn)總和為：n/2 + n/4 + n/8 + ... + 8 + 4 + 2 = n - 2剑刑。所以跳表的空間復(fù)雜度為O(n)媳纬。也就是說如果將包含n個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表，我們需要額外再用接近n個(gè)結(jié)點(diǎn)的存儲(chǔ)空間施掏。

其實(shí)從上面的分析钮惠，我們利用空間換時(shí)間的思想，已經(jīng)把時(shí)間壓縮到了極致七芭，因?yàn)槊恳患?jí)每兩個(gè)索引結(jié)點(diǎn)就有一個(gè)會(huì)被抽到上一級(jí)的索引結(jié)點(diǎn)中素挽，所以此時(shí)跳表所需要的額外內(nèi)存空間最多，即空間復(fù)雜度最高狸驳。其實(shí)我們可以通過改變抽取結(jié)點(diǎn)的間距來降低跳表的空間復(fù)雜度预明，在其時(shí)間復(fù)雜度和空間復(fù)雜度方面取一個(gè)綜合性能，當(dāng)然也要看具體情況耙箍，如果內(nèi)存空間足夠撰糠，那就可以選擇最小的結(jié)點(diǎn)間距，即每兩個(gè)索引結(jié)點(diǎn)抽取一個(gè)結(jié)點(diǎn)到上一級(jí)索引中辩昆。如果想降低跳表的空間復(fù)雜度阅酪，則可以選擇每三個(gè)或者每五個(gè)結(jié)點(diǎn)，抽取一個(gè)結(jié)點(diǎn)到上級(jí)索引中卤材。

image.png

如上圖所示遮斥，每三個(gè)結(jié)點(diǎn)抽取一個(gè)結(jié)點(diǎn)到上一級(jí)索引中，則第一級(jí)需要大約n/3個(gè)結(jié)點(diǎn)扇丛，第二級(jí)索引大約需要n/9個(gè)結(jié)點(diǎn)术吗。每往上一級(jí)，索引的結(jié)點(diǎn)個(gè)數(shù)就除以3帆精，為了方便計(jì)算较屿，我們假設(shè)最高一級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)為1隧魄，則可以得到一個(gè)等比數(shù)列，去下圖所示：

image.png

通過等比數(shù)列的求和公式隘蝎，總的索引結(jié)點(diǎn)大約是：n/3 + n /9 + n/27 + ... + 9 + 3 + 1 = n/2购啄。盡管空間復(fù)雜度還是O(n)，但是比之前的每兩個(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)的索引構(gòu)建方法嘱么，可以減少了一半的索引結(jié)點(diǎn)存儲(chǔ)空間狮含。

實(shí)際上，在軟件開發(fā)中曼振，我們不必太在意索引占用的額外空間几迄。在講數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們習(xí)慣性地把要處理的數(shù)據(jù)看成整數(shù)冰评，但是在實(shí)際的軟件開發(fā)中映胁，原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值和幾個(gè)指針甲雅，并不需要存儲(chǔ)對(duì)象解孙，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了抛人。

5弛姜、跳表的插入
跳表插入的時(shí)間復(fù)雜度為：O(logn)，支持高效的動(dòng)態(tài)插入函匕。

在單鏈表中娱据，一旦定位好要插入的位置，插入結(jié)點(diǎn)的時(shí)間復(fù)雜度是很低的盅惜，就是O(1)中剩。但是為了保證原始鏈表中數(shù)據(jù)的有序性，我們需要先找到要插入的位置抒寂，這個(gè)查找的操作就會(huì)比較耗時(shí)结啼。

對(duì)于純粹的單鏈表，需要遍歷每個(gè)結(jié)點(diǎn)屈芜，來找到插入的位置郊愧。但是對(duì)于跳表來說，查找的時(shí)間復(fù)雜度為O(logn)井佑，所以這里查找某個(gè)數(shù)據(jù)應(yīng)該插入的位置的時(shí)間復(fù)雜度也是O(logn)属铁，如下圖所示：

image.png

6、跳表的刪除
跳表的刪除操作時(shí)間復(fù)雜度為：O(logn)躬翁，支持動(dòng)態(tài)的刪除焦蘑。

在跳表中刪除某個(gè)結(jié)點(diǎn)時(shí)，如果這個(gè)結(jié)點(diǎn)在索引中也出現(xiàn)了盒发，我們除了要?jiǎng)h除原始鏈表中的結(jié)點(diǎn)例嘱，還要?jiǎng)h除索引中的狡逢。因?yàn)閱捂湵碇械膭h除操作需要拿到刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后再通過指針操作完成刪除拼卵。所以在查找要?jiǎng)h除的結(jié)點(diǎn)的時(shí)候奢浑，一定要獲取前驅(qū)結(jié)點(diǎn)（雙向鏈表除外）。因此跳表的刪除操作時(shí)間復(fù)雜度即為O(logn)腋腮。

7雀彼、跳表索引動(dòng)態(tài)更新
當(dāng)我們不斷地往跳表中插入數(shù)據(jù)時(shí)，我們?nèi)绻桓滤饕秃陀锌赡艹霈F(xiàn)某2個(gè)索引節(jié)點(diǎn)之間的數(shù)據(jù)非常多的情況详羡，在極端情況下，跳表還會(huì)退化成單鏈表嘿悬，如下圖所示：

image.png

作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，我們需要某種手段來維護(hù)索引與原始鏈表大小之間的平衡水泉，也就是說善涨，如果鏈表中的結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加一些草则，避免復(fù)雜度退化钢拧，以及查找、插入和刪除操作性能的下降炕横。

如果你了解紅黑樹源内、AVL樹這樣的平衡二叉樹，你就會(huì)知道它們是通過左右旋的方式保持左右子樹的大小平衡份殿，而跳表是通過隨機(jī)函數(shù)來維護(hù)“平衡性”膜钓。

當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們可以通過一個(gè)隨機(jī)函數(shù)卿嘲，來決定這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引層中颂斜，比如隨機(jī)函數(shù)生成了值K，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第K級(jí)這個(gè)K級(jí)索引中拾枣。如下圖中要插入數(shù)據(jù)為6沃疮，K=2的例子：

image.png

隨機(jī)函數(shù)的選擇是非常有講究的，從概率上講梅肤，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性司蔬，不至于性能的過度退化。至于隨機(jī)函數(shù)的選擇姨蝴，見下面的代碼實(shí)現(xiàn)過程俊啼，而且實(shí)現(xiàn)過程并不是重點(diǎn)，掌握思想即可似扔。

8吨些、跳表的性質(zhì)
(1) 由很多層結(jié)構(gòu)組成搓谆，level是通過一定的概率隨機(jī)產(chǎn)生的；
(2) 每一層都是一個(gè)有序的鏈表豪墅，默認(rèn)是升序 泉手；
(3) 最底層(Level 1)的鏈表包含所有元素；
(4) 如果一個(gè)元素出現(xiàn)在Level i 的鏈表中偶器，則它在Level i 之下的鏈表也都會(huì)出現(xiàn)斩萌；
(5) 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素屏轰，一個(gè)指向下面一層的元素颊郎。

平民版跳表實(shí)現(xiàn)，若果你對(duì)跳表實(shí)現(xiàn)完全沒概念霎苗，可一觀

skip_list_test.go

package skip_list_2

import (
    "testing"
)

func TestNewSkipList(t *testing.T) {
    root := NewLinkedList()
    data := []int{1, 3, 4, 5, 7, 8, 9, 10, 13, 16, 17, 18}
    for i := range data {
        root.InsertToTail(data[i])
    }
    skipList := NewSkipList(4, root)
    skipList.Dump()
    skipList.search(1)
    skipList.insert(6)
    skipList.Dump()

    skipList.search(6)

}

skip_list.go

package skip_list_2

import (
    "fmt"
    "math/rand"
)

type SkipList struct {
    maxHeight int
    root      *LinkedList
    indexList []*LinkedList
    step      int
}

func NewSkipList(step int, root *LinkedList) *SkipList {
    skipList := &SkipList{root: root, step: step}
    skipList.createIndexList()
    return skipList

}

func (sl *SkipList) isEmpty() bool {
    return sl.root.length == 0
}

func (sl *SkipList) createIndexList() {
    sl.indexList = make([]*LinkedList, 0, 0)
    var currentList *LinkedList
    for {
        if currentList == nil {
            currentList = sl.root
        }

        tmpList := NewLinkedList()
        for i := 0; i < currentList.length; i += sl.step {

            if i == 0 {
                node := currentList.FindByIndex(i)
                newNode := tmpList.InsertToTail(node.value)
                newNode.down = node
            } else {
                node := currentList.FindByIndex(i)
                newNode := tmpList.InsertToTail(node.value)
                newNode.down = node
            }
        }
        if tmpList.length == 1 { // 只有一個(gè)索引姆吭，沒有什么意義
            break
        }
        sl.indexList = append(sl.indexList, tmpList)
        fmt.Println(tmpList)
        if tmpList.length == 2 { //最頂層只有三個(gè)索引
            break
        } else {
            currentList = tmpList
        }

    }
}

func (sl *SkipList) search(v int) *Node {
    fmt.Println("----- search start-----", v)
    list := sl.indexList[len(sl.indexList)-1]
    var tNode *Node
    tNode = list.FindByIndex(0)
    fmt.Println(tNode)
    for {
        var nodeL, nodeR *Node
        nodeL = tNode
        nodeR = tNode.next
        fmt.Printf("左節(jié)點(diǎn)%v -->> 右節(jié)點(diǎn)%v\n", nodeL, nodeR)
        if nodeR == nil { // 當(dāng)前層， nodeL 就是最后一個(gè)點(diǎn)
            tNode = nodeL.down
        } else if v >= nodeL.value && v < nodeR.value {
            tNode = nodeL.down
        } else if v >= nodeR.value {
            tNode = nodeR.down
        }
        if tNode.down == nil {
            break
        }
        if tNode.next == nil {
            tNode = tNode.down
        }
    }
    fmt.Printf("原始節(jié)點(diǎn)%v\n", tNode)
    for {
        if tNode == nil || tNode.value > v {
            fmt.Println("找不到對(duì)應(yīng)的node")
            return nil
        }
        if tNode.value == v {
            fmt.Println("找到了node", tNode)
            return tNode
        }
        fmt.Println("繼續(xù)查找node")
        tNode = tNode.next
    }

}

func (sl *SkipList) searchPer(v int) *Node {
    fmt.Println("----- searchPer start-----", v)
    list := sl.indexList[len(sl.indexList)-1]
    var tNode *Node
    tNode = list.FindByIndex(0)
    fmt.Println(tNode)
    for {
        var nodeL, nodeR *Node
        nodeL = tNode
        nodeR = tNode.next
        fmt.Printf("左節(jié)點(diǎn)%v -->> 右節(jié)點(diǎn)%v\n", nodeL, nodeR)
        if nodeR == nil { // 當(dāng)前層唁盏， nodeL 就是最后一個(gè)點(diǎn)
            tNode = nodeL.down
        } else if v >= nodeL.value && v < nodeR.value {
            tNode = nodeL.down
        } else if v >= nodeR.value {
            tNode = nodeR.down
        }
        if tNode.down == nil {
            break
        }
        if tNode.next == nil {
            tNode = tNode.down
        }
    }
    fmt.Printf("原始節(jié)點(diǎn)%v\n", tNode)
    for {
        if tNode.next == nil {
            fmt.Println("找到了要插入的節(jié)點(diǎn)", tNode)
            return tNode
        }

        if tNode.next.value >= v {
            fmt.Println("找到了要插入的節(jié)點(diǎn)", tNode)
            return tNode
        }

        fmt.Println("繼續(xù)查找node")
        tNode = tNode.next
    }
}
func (sl *SkipList) insert(v int) bool {
    fmt.Println("----- insert start-----", v)
    node := sl.searchPer(v)
    tmp := node.next
    node.next = NewNode(v)
    node.next.next = tmp

    //插入完成后 更新索引

    level := rand.Intn(len(sl.indexList))
    fmt.Println("隨機(jī)索引層為: ", level)
    insertNode := NewNode(v)
    for l := level; l >= 0; l-- {
        // 確認(rèn)插入位置的
        node := sl.indexList[l].FindByIndex(0)
        var target *Node
        for {
            nodeL := node
            nodeR := node.next
            if nodeR == nil {
                target = nodeL
                break
            } else if v >= nodeL.value && v < nodeR.value {
                target = nodeL
                break
            } else if v >= nodeR.value {
                target = nodeR
                break
            }
            node = node.next
        }
        tmp := target.next
        target.next = insertNode
        insertNode.next = tmp

        newInsertNode := NewNode(v)
        insertNode.down = newInsertNode
        insertNode = newInsertNode
    }

    return true
}

func (sl *SkipList) Dump() {
    fmt.Println("----- dump start-----")

    for i := len(sl.indexList) - 1; i >= 0; i-- {
        sl.indexList[i].Print()
    }
    sl.root.Print()
    fmt.Println("----- dump end-----")

}

linked_list.go

package skip_list_2

import "fmt"

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

type LinkedList struct {
    head   *Node
    length int
}

func NewNode(v int) *Node {
    return &Node{nil, v, nil}
}

func (this *Node) GetNext() *Node {
    return this.next
}

func (this *Node) GetValue() int {
    return this.value
}

func NewLinkedList() *LinkedList {
    return &LinkedList{NewNode(0), 0}
}

//在某個(gè)節(jié)點(diǎn)后面插入節(jié)點(diǎn)
func (this *LinkedList) InsertAfter(p *Node, v int) *Node {
    if nil == p {
        return nil
    }
    newNode := NewNode(v)
    oldNext := p.next
    p.next = newNode
    newNode.next = oldNext
    this.length++
    return newNode
}

//在某個(gè)節(jié)點(diǎn)前面插入節(jié)點(diǎn)
func (this *LinkedList) InsertBefore(p *Node, v int) bool {
    if nil == p || p == this.head {
        return false
    }
    cur := this.head.next
    pre := this.head
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur
        cur = cur.next
    }
    if nil == cur {
        return false
    }
    newNode := NewNode(v)
    pre.next = newNode
    newNode.next = cur
    this.length++
    return true
}

//在鏈表頭部插入節(jié)點(diǎn)
func (this *LinkedList) InsertToHead(v int) *Node {
    return this.InsertAfter(this.head, v)
}

//在鏈表尾部插入節(jié)點(diǎn)
func (this *LinkedList) InsertToTail(v int) *Node {
    cur := this.head
    for nil != cur.next {
        cur = cur.next
    }
    return this.InsertAfter(cur, v)
}

//通過索引查找節(jié)點(diǎn)
func (this *LinkedList) FindByIndex(index int) *Node {
    if index >= this.length {
        return nil
    }
    cur := this.head.next
    var i int = 0
    for ; i < index; i++ {
        cur = cur.next
    }
    return cur
}

//刪除傳入的節(jié)點(diǎn)
func (this *LinkedList) DeleteNode(p *Node) bool {
    if nil == p {
        return false
    }
    cur := this.head.next
    pre := this.head
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur
        cur = cur.next
    }
    if nil == cur {
        return false
    }
    pre.next = p.next
    p = nil
    this.length--
    return true
}

//打印鏈表
func (this *LinkedList) Print() {
    cur := this.head.next
    format := ""
    for nil != cur {
        format += fmt.Sprintf("%+v", cur.GetValue())
        cur = cur.next
        if nil != cur {
            format += "->"
        }
    }
    fmt.Println(format)
}

/*
單鏈表反轉(zhuǎn)
時(shí)間復(fù)雜度：O(N)
*/
func (this *LinkedList) Reverse() {
    if nil == this.head || nil == this.head.next || nil == this.head.next.next {
        return
    }

    var pre *Node = nil
    cur := this.head.next
    for nil != cur {
        tmp := cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    }

    this.head.next = pre
}

/*
判斷單鏈表是否有環(huán)
*/
func (this *LinkedList) HasCycle() bool {
    if nil != this.head {
        slow := this.head
        fast := this.head
        for nil != fast && nil != fast.next {
            slow = slow.next
            fast = fast.next.next
            if slow == fast {
                return true
            }
        }
    }
    return false
}

/*
刪除倒數(shù)第N個(gè)節(jié)點(diǎn)
*/
func (this *LinkedList) DeleteBottomN(n int) {
    if n <= 0 || nil == this.head || nil == this.head.next {
        return
    }

    fast := this.head
    for i := 1; i <= n && fast != nil; i++ {
        fast = fast.next
    }

    if nil == fast {
        return
    }

    slow := this.head
    for nil != fast.next {
        slow = slow.next
        fast = fast.next
    }
    slow.next = slow.next.next
}

/*
獲取中間節(jié)點(diǎn)
*/
func (this *LinkedList) FindMiddleNode() *Node {
    if nil == this.head || nil == this.head.next {
        return nil
    }
    if nil == this.head.next.next {
        return this.head.next
    }

    slow, fast := this.head, this.head
    for nil != fast && nil != fast.next {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

func main() {
    list := NewLinkedList()
    list.InsertToTail(2)
    list.InsertToHead(1)
    list.InsertToTail(3)
    list.InsertToTail(4)
    list.Reverse()
    list.Print()
    if list.HasCycle() {
        fmt.Println("has cycle")
    }
}