跳表

跳表的定义

跳表(SkipList)：增加了向前指针的链表叫做跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质是一种可以进行近似二分查找的有序链表。跳表在原有的有序链表上增加了多级索引，通过索引来实现快速查询。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

跳表的详解

有序原始链表
对于一个单链表来说，即使链表中的数据是有序的，如果我们想要查找某个数据，也必须从头到尾的遍历链表，很显然这种查找效率是十分低效的，时间复杂度为O(n)。
那么我们如何提高查找效率呢？我们可以对链表建立一级“索引”，每两个结点提取一个结点到上一级，我们把抽取出来的那一级叫做索引或者索引层，如下图所示，我建立了两级索引，down表示down指针。
image.png
假设我们现在要查找值为16的这个结点。我们可以先在索引层遍历，当遍历索引层中值为13的时候，通过值为13的结点的指针域发现下一个结点值为17，因为链表本身有序，所以值为16的结点肯定在13和17这两个结点之间。然后我们通过索引层结点的down指针，下降到原始链表这一层，继续往后遍历查找。这个时候我们只需要遍历2个结点（值为13和16的结点），就可以找到值等于16的这个结点了。如果使用原来的链表方式进行查找值为16的结点，则需要遍历10个结点才能找到，而现在只需要遍历7个结点即可，从而提高了查找效率。

那么我们可以由此得到启发，和上面建立第一级索引的方式相似，在第一级索引的基础上，每两个一级索引结点就抽到一个结点到第二级索引中。再来查找值为16的结点，只需要遍历6个结点即可，从而进一步提高了查找效率。

跳表的时间复杂度

单链表的查找时间复杂度为：O(n)，
下面分析下跳表这种数据结构的查找时间复杂度：
我们首先考虑这样一个问题，如果链表里有n个结点，那么会有多少级索引呢？按照上面讲的，每两个结点都会抽出一个结点作为上一级索引的结点。那么第一级索引的个数大约就是n/2，第二级的索引大约就是n/4，第三级的索引就是n/8，依次类推，也就是说，第k级索引的结点个数是第k-1级索引的结点个数的1/2，那么第k级的索引结点个数为n/(2k)。

、】
`
假设索引有h级，最高级的索引有2个结点，通过上面的公式，我们可以得到，从而可得：h =log2n-1。如果包含原始链表这一层，整个跳表的高度就是。我们在跳表中查找某个数据的时候，如果每一层都要遍历m个结点，那么在跳表中查询一个数据的时间复杂度就为O(m*logn)。

其实根据前面的分析，我们不难得出m=3，即每一级索引都最多只需要遍历3个结点，分析如下：

时间复杂度分析

如上图所示，假如我们要查找的数据是x，在第k级索引中，我们遍历到y结点之后，发现x大于y，小于y后面的结点z。所以我们通过y的down指针，从第k级索引下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个结点(包含y和z)。所以，我们在k-1级索引中最多需要遍历3个结点，以此类推，每一级索引都最多只需要遍历3个结点。

因此，m=3，所以跳表查找任意数据的时间复杂度为O(logn)，这个查找的时间复杂度和二分查找是一样的，但是我们却是基于单链表这种数据结构实现的。不过，天下没有免费的午餐，这种查找效率的提升是建立在很多级索引之上的，即空间换时间的思想。其具体空间复杂度见下文详解。

跳表的空间复杂度

比起单纯的单链表，跳表就需要额外的存储空间去存储多级索引。假设原始链表的大小为n，那么第一级索引大约有n/2个结点，第二级索引大约有4/n个结点，依次类推，每上升一级索引结点的个数就减少一半，直到剩下最后2个结点，如下图所示，其实就是一个等比数列。

空间复杂度

这几级索引结点总和为：n/2 + n/4 + n/8 + ... + 8 + 4 + 2 = n - 2。所以跳表的空间复杂度为O(n)。也就是说如果将包含n个结点的单链表构造成跳表，我们需要额外再用接近n个结点的存储空间。

其实从上面的分析，我们利用空间换时间的思想，已经把时间压缩到了极致，因为每一级每两个索引结点就有一个会被抽到上一级的索引结点中，所以此时跳表所需要的额外内存空间最多，即空间复杂度最高。其实我们可以通过改变抽取结点的间距来降低跳表的空间复杂度，在其时间复杂度和空间复杂度方面取一个综合性能，当然也要看具体情况，如果内存空间足够，那就可以选择最小的结点间距，即每两个索引结点抽取一个结点到上一级索引中。如果想降低跳表的空间复杂度，则可以选择每三个或者每五个结点，抽取一个结点到上级索引中。

image.png

如上图所示，每三个结点抽取一个结点到上一级索引中，则第一级需要大约n/3个结点，第二级索引大约需要n/9个结点。每往上一级，索引的结点个数就除以3，为了方便计算，我们假设最高一级的索引结点个数为1，则可以得到一个等比数列，去下图所示：

image.png

通过等比数列的求和公式，总的索引结点大约是：n/3 + n /9 + n/27 + ... + 9 + 3 + 1 = n/2。尽管空间复杂度还是O(n)，但是比之前的每两个结点抽一个结点的索引构建方法，可以减少了一半的索引结点存储空间。

实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构的时候，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

5、跳表的插入
跳表插入的时间复杂度为：O(logn)，支持高效的动态插入。

在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是O(1)。但是为了保证原始链表中数据的有序性，我们需要先找到要插入的位置，这个查找的操作就会比较耗时。

对于纯粹的单链表，需要遍历每个结点，来找到插入的位置。但是对于跳表来说，查找的时间复杂度为O(logn)，所以这里查找某个数据应该插入的位置的时间复杂度也是O(logn)，如下图所示：

image.png

6、跳表的删除
跳表的删除操作时间复杂度为：O(logn)，支持动态的删除。

在跳表中删除某个结点时，如果这个结点在索引中也出现了，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到删除结点的前驱结点，然后再通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点（双向链表除外）。因此跳表的删除操作时间复杂度即为O(logn)。

7、跳表索引动态更新
当我们不断地往跳表中插入数据时，我们如果不更新索引，就有可能出现某2个索引节点之间的数据非常多的情况，在极端情况下，跳表还会退化成单链表，如下图所示：

image.png

作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中的结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入和删除操作性能的下降。

如果你了解红黑树、AVL树这样的平衡二叉树，你就会知道它们是通过左右旋的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护“平衡性”。

当我们往跳表中插入数据的时候，我们可以通过一个随机函数，来决定这个结点插入到哪几级索引层中，比如随机函数生成了值K，那我们就将这个结点添加到第一级到第K级这个K级索引中。如下图中要插入数据为6，K=2的例子：

image.png

随机函数的选择是非常有讲究的，从概率上讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能的过度退化。至于随机函数的选择，见下面的代码实现过程，而且实现过程并不是重点，掌握思想即可。

8、跳表的性质
(1) 由很多层结构组成，level是通过一定的概率随机产生的；
(2) 每一层都是一个有序的链表，默认是升序 ；
(3) 最底层(Level 1)的链表包含所有元素；
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现；
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

平民版跳表实现，若果你对跳表实现完全没概念，可一观

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 { // 只有一个索引，没有什么意义
            break
        }
        sl.indexList = append(sl.indexList, tmpList)
        fmt.Println(tmpList)
        if tmpList.length == 2 { //最顶层只有三个索引
            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("左节点%v -->> 右节点%v\n", nodeL, nodeR)
        if nodeR == nil { // 当前层， nodeL 就是最后一个点
            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("原始节点%v\n", tNode)
    for {
        if tNode == nil || tNode.value > v {
            fmt.Println("找不到对应的node")
            return nil
        }
        if tNode.value == v {
            fmt.Println("找到了node", tNode)
            return tNode
        }
        fmt.Println("继续查找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("左节点%v -->> 右节点%v\n", nodeL, nodeR)
        if nodeR == nil { // 当前层， nodeL 就是最后一个点
            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("原始节点%v\n", tNode)
    for {
        if tNode.next == nil {
            fmt.Println("找到了要插入的节点", tNode)
            return tNode
        }

        if tNode.next.value >= v {
            fmt.Println("找到了要插入的节点", tNode)
            return tNode
        }

        fmt.Println("继续查找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("随机索引层为: ", level)
    insertNode := NewNode(v)
    for l := level; l >= 0; l-- {
        // 确认插入位置的
        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}
}

//在某个节点后面插入节点
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
}

//在某个节点前面插入节点
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
}

//在链表头部插入节点
func (this *LinkedList) InsertToHead(v int) *Node {
    return this.InsertAfter(this.head, v)
}

//在链表尾部插入节点
func (this *LinkedList) InsertToTail(v int) *Node {
    cur := this.head
    for nil != cur.next {
        cur = cur.next
    }
    return this.InsertAfter(cur, v)
}

//通过索引查找节点
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
}

//删除传入的节点
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)
}

/*
单链表反转
时间复杂度：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
}

/*
判断单链表是否有环
*/
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
}

/*
删除倒数第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
}

/*
获取中间节点
*/
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")
    }
}