05、跳表

哈喽，大家好，我是厨子，今天给大家介绍一下跳表

主要从，什么是跳表，跳表是用来干嘛的几个角度来剖析，希望能够对大家有一些帮助

什么是跳表?

跳表是一种基于链表的数据结构,它通过在普通链表的基础上增加多级索引来实现快速查找。你可以把它想象成一座多层的立交桥:

• 底层:所有的数据都在这一层,按顺序排列
• 上层:每一层都是下一层的"快速通道",存储了部分节点的索引

这样设计的好处是:查找数据时可以先在高层快速跳跃,接近目标后再降到低层精确定位,大大提高了效率。

跳表层级结构示意图

为什么需要跳表?

上面说了，跳表是一种基于链表的数据结构，那么我们来说一下传统链表的局限

2普通链表的局限

假设我们要在一个有序链表中查找元素 77

暂时无法在飞书文档外展示此内容

使用普通链表,我们必须从头开始,逐个节点比较,最坏情况下需要遍历 n 个节点,时间复杂度为 O(n)。

那我们想提高查找效率，应该怎么做呢？

跳表的优化思路

如果我们在链表上方建立一层索引,每隔一个节点抽取一个:

层级2:  1 ------> 14 -------> 32 -------> 71 -------> 85
       ↓         ↓          ↓          ↓           ↓
层级1:  1 -> 7 -> 14 -> 21 -> 32 -> 37 -> 71 -> 77 -> 85 -> 92

现在查找 77:

1. 在层级2从1开始: 1 < 77,继续
2. 到达14: 14 < 77,继续
3. 到达32: 32 < 77,继续
4. 到达71: 71 < 77,继续
5. 下一个是85 > 77,降到层级1（从 71 降到下一级）
6. 从71开始: 71 -> 77,找到!

相比原来的检索方式，效率得到了提升，如果继续增加索引层级,效率会进一步提升。

这就是为什么需要跳表

跳表的结构设计

节点结构

每个跳表节点包含:

• 值(value): 存储的数据
• 多个指针(forward[]): 指向不同层级的下一个节点

// 跳表节点类
class SkipListNode {
private:
    // 节点存储的值
    int value;
    // 指向各层下一个节点的指针数组，索引 0 为最底层
    std::vector<SkipListNode*> forward;

public:
    // 构造函数：初始化节点值和层数（forward 数组大小）
    SkipListNode(int val, int level) : value(val) {
        // 初始化 forward 数组，每个元素初始化为 nullptr（指向空）
        forward.resize(level, nullptr);
    }

    // 友元声明：让 SkipList 类能直接访问节点的私有成员
    friend class SkipList;
};

3.2 完整跳表结构示例

一个典型的跳表看起来像这样:

层级2:  1 ------> 14 -------> 32 -------> 71 -------> 85
       ↓         ↓          ↓          ↓           ↓
层级1:  1 -> 7 -> 14 -> 21 -> 32 -> 37 -> 71 -> 77 -> 85 -> 92

下面我们来说一下跳表的多种操作

核心操作详解

查找操作

从最高层开始,逐层向右查找,遇到大于目标值的节点就下降一层。

代码实现

#include <vector>
#include <climits>  // 用于 INT_MIN

// 跳表节点类（需提前声明）
class SkipListNode {
public:
    int value;
    std::vector<SkipListNode*> forward;

    // 构造函数：初始化值和 forward 数组
    SkipListNode(int val, int level) : value(val) {
        forward.resize(level, nullptr);
    }
};

// 跳表类
class SkipList {
private:
    int max_level;       // 最大层级
    int level;           // 当前最高层级
    SkipListNode* head;  // 头节点

public:
    // 构造函数：初始化跳表
    SkipList(int max_level = 16) : max_level(max_level), level(0) {
        // 头节点值设为负无穷
        head = new SkipListNode(INT_MIN, max_level);
    }

    // 析构函数：释放内存（补充实现，避免内存泄漏）
    ~SkipList() {
        SkipListNode* current = head;
        while (current != nullptr) {
            SkipListNode* next = current->forward[0];
            delete current;
            current = next;
        }
    }

    // 查找目标值：存在返回 true，否则返回 false
    bool search(int target) {
        SkipListNode* current = head;

        // 从当前最高层开始向下查找
        for (int i = level; i >= 0; --i) {
            // 在当前层向右移动，直到下一个节点的值 >= target
            while (current->forward[i] != nullptr && current->forward[i]->value < target) {
                current = current->forward[i];
            }
        }

        // 移动到最底层的下一个节点
        current = current->forward[0];

        // 检查是否找到目标值
        if (current != nullptr && current->value == target) {
            return true;
        }
        return false;
    }
};

时间复杂度: O(log n)

链表的插入和删除操作相对来说复杂一些，咱们这里详细说一下

时间复杂度: O(log n)

参考资料:

• William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees" (1990)
• Redis 源码: https://github.com/redis/redis/blob/unstable/src/t_zset.c