Golang implements skip table

Skip list is a data structure based on linked list. It adds some additional pointers to the linked list, which greatly improves the efficiency of data search and operation compared with ordinary linked lists. Jump tables were originally proposed by William Pugh in 1990 and are widely used in databases, search engines and other fields. This article will introduce how to use Go language to implement skip table data structure.

1. Overview of skip list

The skip list is a multi-level linked list structure. The data nodes of each level of linked list are distributed among several nodes of the next level of linked list. Each node in the jump list has an array containing multiple pointers that point to the root node and the node at the same location in the next-level linked list. These pointers are set randomly or according to certain rules. Improper settings will cause the jump list to degenerate into a singly linked list, so the pointer distribution needs to be set appropriately.

The skip table supports basic operations such as addition, deletion, and search. Its time complexity is O(log n), which is equivalent to the time complexity of a binary tree. Since the skip list structure is based on a linked list, a certain amount of additional storage space is required to store pointer information.

2. Jump table implementation

First, we need to define the node structure of the jump table:

type skipListNode struct {
    Val       int                            // 节点值
    next      []*skipListNode               // 指向下一层节点的指针数组
}

The node structure defines the value of the node and points to the next layer Pointer array of nodes next. The number of nodes in the next layer is randomly set and generated through the rand.Intn() function.

func newNode(val int, level int) *skipListNode {
    node := &skipListNode{Val: val, next: make([]*skipListNode, level+1)}
    return node
}

func randLevel() int {
    level := 1
    for rand.Float32() < 0.5 {
        level++
    }
    return level
}

After defining the node structure and the function that generates the random number of layers, we can define the structure of the skip table:

type skipList struct {
    head   []*skipListNode              // 指向跳表头节点的指针数组
    level  int                           // 当前跳表深度
    length int                          // 跳表节点数量
}

The skip table structure contains the node pointing to the head of the skip table. The pointer array head, the current skip table depth level and the number of skip table nodes length. The initial depth of the jump table is 1, and the depth is changed according to the number of levels generated by random numbers when adding nodes.

After defining the jump list structure, we can start to implement the basic operations of the jump list. The first is the insertion operation:

func (sl *skipList) insert(val int) {
    level := randLevel()                   // 生成随机层数
    node := newNode(val, level)            // 创建新节点
    update := make([]*skipListNode, level+1) // 用于更新每层跳表的节点指针
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {       // 从最高层开始向下查找
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找插入位置
            cur = cur.next[i]
        }
        update[i] = cur                      // 更新每层跳表要插入的位置
    }
    for i := 0; i <= level; i++ {            // 更新每层跳表插入节点
        node.next[i] = update[i].next[i]
        update[i].next[i] = node
    }
    // 更新跳表深度和节点数
    if level > sl.level {
        sl.level = level
    }
    sl.length++
}

The insertion operation first generates a random number of layers, creates new nodes, and uses the update array to record the position when inserting each layer into the jump table. Then start from the top level and search downwards for the location to be inserted, record the previous node of the location to be inserted, and then update the directions of the inserted node and the previous node in the jump table of each layer. Finally, the depth and number of nodes of the jump table are updated.

The next step is the deletion operation:

func (sl *skipList) delete(val int) {
    update := make([]*skipListNode, sl.level+1) // 用于更新每层跳表的节点指针
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找要删除的节点位置
            cur = cur.next[i]
        }
        if cur.next[i] != nil && cur.next[i].Val == val { // 找到要删除的节点
            update[i] = cur
        } else {
            update[i] = nil
        }
    }
    if update[0] != nil && update[0].next[0].Val == val { // 更新节点指针
        node := update[0].next[0]
        for i := 0; i <= sl.level && update[i].next[i] == node; i++ {
            update[i].next[i] = node.next[i]
        }
        // 更新跳表深度和节点数
        for sl.level > 0 && len(sl.head[sl.level].next) == 0 {
            sl.level--
        }
        sl.length--
    }
}

The deletion operation first finds the node to be deleted and records its position and the position of the previous node. If the node to be deleted is found, the node pointer is updated, and the depth and number of nodes of the jump table are updated.

The last is the search operation:

func (sl *skipList) search(val int) *skipListNode {
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找要查找的节点位置
            cur = cur.next[i]
        }
    }
    if cur.next[0] != nil && cur.next[0].Val == val { // 找到要查找的节点
        return cur.next[0]
    }
    return nil // 没有找到节点，返回nil
}

The search operation is basically similar to the insertion and deletion operations. It starts from the top level and searches downward for the node to be found, records its location, and returns the node if it is found. .

3. Skip list analysis

The skip list is an efficient data structure based on linked lists. Compared with the balanced binary tree, the time complexity of its insertion and deletion operations is the same (O(log n )), but the time complexity of the search operation is O(log n), which is more efficient than the search time complexity of the binary tree O(h), where h is the height of the tree. Due to the setting of random layers, the height of the jump table is also random, and the efficiency of insertion, deletion and search is also higher.

The skip table can also control its space complexity by reasonably setting the number of nodes and pointers. Setting multiple pointers in the jump list and consuming more storage space is a trade-off. In order to obtain better performance, these additional space overheads are more reasonable in some specific scenarios.

4. Summary

The skip list is an efficient linked list data structure that can be used to replace the balanced tree to deal with large-scale cache data storage and search problems. The concurrency features and flat package structure of the Go language make skip lists very practical in Go applications. The key to implementing a skip table lies in the random generation of node levels, finding the locations to be inserted and deleted, and updating node pointers. Through these basic operations, skip lists make their efficiency higher than that of ordinary linked lists, and the number of nodes and pointers can be reasonably set according to specific application scenarios.

The above is the detailed content of Golang implements skip table. For more information, please follow other related articles on the PHP Chinese website!