Skip List

Linked lists are well known for their simplicity and ease of implementation, and are often used in practical development. The time complexity of various operations is respectively

• Query: O (n) O (n) O (n)
• Insert: O (1) O (1) O (1)
• Delete: O (1) O (1) O (1)

As you can see, the search/query speed of linked lists is relatively slow. Because the list element queries must start at the first node at a time, only one node can be traversed at a time. SkipList, on the other hand, allows for node hopping, which reduces the time complexity of query operations.

Skip List

Skip list is a probabilistic data structure, which is an extension of linked list data structure. In a linked list data structure, each node points to its neighbor to the right. The skip list is extended on this basis. In addition to the pointer pointing to the adjacent nodes on the right (basic level), some nodes have other Pointers pointing to nodes KKK (K ≥ 0K ≥ 0K ≥0) on the right. The higher the level of the pointer, the fewer nodes on the level.

4. Belief in the Perfect Skip List

The so-called perfect skip list refers to the interval 2l2^ L2L between two adjacent nodes as the pointer level (L (L ≥0) L (L ≥0) L (L ≥0) L) increases.

Perfect skip lists have the following properties:

• If the number of nodes is NNN, the number of layers is ceil(log⁡2n)ceil(\log_2 n)ceil(log2n)
• The number of nodes at LLL layer is only half of that at L − 1L − 1L −1

As a result, the time complexity of the query is reduced to O(log⁡n)O(\log n)O(logn). The performance of the query is improved, but node insertion and deletion become very difficult, because the Pointers between nodes need to be reset every time a node is inserted/deleted.

⓶ random skip list

Perfect skip lists improve query performance, but node insertion and deletion are very difficult to maintain. Therefore, we can only expect a perfect skip list to meet the requirements of a perfect skip list, but in reality each node contains only a random level of Pointers, which is a random skip list.

How to determine the hierarchy of Pointers contained in each node inserted into the skip list? Here, taking coin flipping as an example, the number of consecutive heads obtained before the coin landed on the back is the hierarchy of Pointers contained in the node. At the same time, assuming that the number of nodes in the current skip list is NNN, then theoretically, after inserting a new node, the level of the skip list should not exceed ceil(log⁡2(n+1))ceil(\log_2 (n+1))ceil(log2(n+1))). Therefore, the newly inserted node should contain a pointer with the lower of the two levels.

⓷ code implementation

import random
import math


class Node:
    def __init__(self, key=-1, level=0) :
        self.key = key
        self.next = [None] * (level + 1)

    def __repr__(self) :
        return str(self.__dict__)

    def __str__(self) :
        return str(self.__dict__)


class SkipList:
    def __init__(self) :
        self.header = Node()
        self.length = 0
        self.maxLevel = 0

    def get_level(self) :
        Randomly obtain the hierarchy of Pointers that the newly inserted node should contain but theoretically should not exceed the logarithm of the number of nodes in the skip list.
        level = 0
        while random.randint(1.2) != 2 and level < math.log2(self.length + 1):
            level += 1

        return level

    def get_target(self, key) :
        """ Gets the location to perform the insert/delete/query operation ""
        target = [None] * (self.maxLevel + 1)
        node = self.header

        for i in reversed(range(self.maxLevel + 1)) :while node.next[i] is not None and node.next[i].key < key:
                node = node.next[i]
            target[i] = node

        return target

    def search_node(self, key) :
        target = self.get_target(key)

        if len(target) > 0:
            if target[0].next[0].key == key:
                return target[0].next[0]

        return None

    def insert_node(self, key) :
        "" node insertion ""
        target = self.get_target(key)

        Insert only if the element to be inserted does not exist in the skip list or if the skip list is empty
        if target[0].next[0] is None orkey ! = target[0].next[0].key:
            level = self.get_level()
            node = Node(key, level)
            min_level = min(level, self.maxLevel)

            for i in range(min_level + 1):
                node.next[i] = target[i].next[i]
                target[i].next[i] = node

            If the newly inserted node contains Pointers that exceed the top level of the current skip list, the level of the header node should be increased accordingly
            if self.maxLevel < level:
                self.header.next.extend([None] * (level - self.maxLevel))
                for i in range(self.maxLevel + 1, level + 1):
                    self.header.next[i] = node
                self.maxLevel = level
            self.length += 1

    def delete_node(self, key) :
        """ Node deletion """
        target = self.get_target(key)

        if target[0].next[0].key == key:
            node = target[0].next[0]
            for i in range(len(node.next)):
                target[i].next[i] = node.next[i]
                Node deletion may be accompanied by a top-level drop in the skip list
                if self.header.next[i] is None:
                    self.maxLevel -= 1
            self.length -= 1

        return

    def print_node(self) :
        print("print node start")
        for i in reversed(range(self.maxLevel + 1)) :print("level = {}".format(i))
            node = self.header
            while node.next[i] is not None:
                node = node.next[i]
                print(node.key, end=' ')
            print()


lst = SkipList()
lst.insert_node(3)
lst.insert_node(6)
lst.insert_node(7)
lst.insert_node(9)
lst.insert_node(12)
lst.insert_node(19)
lst.insert_node(17)
lst.insert_node(26)
lst.insert_node(21)
lst.insert_node(25)

node = lst.search_node(12)
print(node)

lst.print_node()
lst.delete_node(12)
lst.print_node()

Copy the code