golang 实现跳表

跳表的概念

跳表（Skip List）是一种有序数据结构，用于在链表的基础上提供快速的搜索、插入和删除操作。跳表通过在每一级加入"跳跃"操作，有效地提高了链表的查询效率。

跳表的实现思路

跳表的原理是在链表的基础上增加多级索引，提高查询效率。每一级的索引都是原链表的一个子集，且较高级的索引包含较低级索引的节点。

// 定义跳表节点结构
type SkipListNode struct {
    value int
    next  []*SkipListNode // 存储不同级别的下一个节点
}

type SkipList struct {
    head  *SkipListNode
    level int // 当前跳表的最大级别
}

跳表的插入操作

插入操作是跳表中最重要的一部分，它保持了跳表的有序性，并更新索引。

// 在跳表中插入一个节点
func (sl *SkipList) Insert(value int) {
    // 创建一个新的跳表节点
    newNode := &SkipListNode{
        value: value,
        next:  make([]*SkipListNode, sl.level+1), // 根据当前最大级别来初始化节点的下一个节点数组
    }

    // 查找插入位置
    cur := sl.head
    update := make([]*SkipListNode, sl.level+1)
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].value < value {
            cur = cur.next[i]
        }
        update[i] = cur
    }

    // 更新每一级的节点链表
    for i := sl.level; i >= 0; i-- {
        newNode.next[i] = update[i].next[i]
        update[i].next[i] = newNode
    }

    // 更新跳表的最大级别
    if sl.level < sl.randomLevel() {
        sl.level++
        update = append(update, sl.head)
        sl.head.next = append(sl.head.next, newNode)
    }
}

跳表的搜索操作

搜索操作通过逐级比较，并向右侧移动，实现对于指定值的查找。

// 在跳表中搜索指定值
func (sl *SkipList) Search(target int) *SkipListNode {
    cur := sl.head
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].value < target {
            cur = cur.next[i]
        }
    }
    return cur.next[0]
}

跳表的删除操作

删除操作需要在每一级链表中更新节点的指针。

// 从跳表中删除指定值的节点
func (sl *SkipList) Delete(target int) {
    cur := sl.head
    update := make([]*SkipListNode, sl.level+1)
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].value < target {
            cur = cur.next[i]
        }
        update[i] = cur
    }
    delNode := cur.next[0]
    if delNode != nil && delNode.value == target {
        // 更新每一级的节点链表
        for i := 0; i <= sl.level; i++ {
            if update[i].next[i] == delNode {
                update[i].next[i] = delNode.next[i]
            }
        }
        if sl.head.next[sl.level] == nil {
            sl.level--
        }
    }
}

总结

跳表是一种高效的有序数据结构，它通过添加多级索引，提供快速的搜索、插入和删除功能。在设计跳表时，需要定义节点结构，并实现插入、搜索和删除操作。插入操作需要更新每一级节点链表，搜索操作逐级比较并向右移动，删除操作需要在每一级链表中更新节点的指针。