python 跳表讲解

跳表（Skip List）是一种基于链表的数据结构，它允许快速地查找、插入和删除元素。跳表通过在链表中添加多级索引来实现快速查找，每一级索引都是原始链表的一个子集，且每一级索引的元素数量都比下一级索引少。

跳表的时间复杂度为 O(log n)，与平衡树相当，但实现起来比平衡树简单，且在并发环境下性能更好。

下面是一个简单的 Python 实现：

import random

class SkipNode:
    def __init__(self, val=None, level=0):
        self.val = val
        self.next = [None] * (level + 1)

class SkipList:
    def __init__(self):
        self.head = SkipNode()
        self.level = 0

    def __len__(self):
        return len(self.head.next[0])

    def __getitem__(self, idx):
        if idx < 0 or idx >= len(self):
            raise IndexError('Index out of range')
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.next[i] and len(curr.next[i]) <= idx:
                idx -= len(curr.next[i])
                curr = curr.next[i]
        return curr.next[0][idx]

    def insert(self, val):
        level = self._random_level()
        node = SkipNode(val, level)
        self.level = max(self.level, level)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.next[i] and curr.next[i].val < val:
                curr = curr.next[i]
            if i <= level:
                node.next[i] = curr.next[i]
                curr.next[i] = node

    def remove(self, val):
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.next[i] and curr.next[i].val < val:
                curr = curr.next[i]
            if curr.next[i] and curr.next[i].val == val:
                curr.next[i] = curr.next[i].next[i]
                if i == 0 and not curr.next[i]:
                    while self.level > 0 and not self.head.next[self.level]:
                        self.level -= 1

    def _random_level(self):
        level = 0
        while random.random() < 0.5 and level < 16:
            level += 1
        return level