本文将mark下Skip List的相关notes。

Overview

可以看下视频Skip List Explained。

核心思想

跳跃表的核心思想非常直观：为有序的链表增加多级“索引”，来加速查找过程。它是对“二分查找”思想的一种链表实现。

Why

对于一个有序链表，查找一个元素只能从头到尾遍历，时间复杂度是 O(n)，效率很低。我们希望能像数组的二分查找一样，实现 O(log n) 的查找效率，但链表不支持随机访问。

跳跃表通过“空间换时间”的策略，完美地解决了这个问题。

结构

跳跃表由多层链表组成:

  1. 最底层（第0层）：是一个包含所有元素的有序单链表
  2. 第1层：是底层链表的一个“索引”子集，它只包含底层中的部分节点，节点密度更低
  3. 第2层：是第1层索引的索引，节点更稀疏
  4. 以此类推… 直到最顶层

每一层都是一个有序的链表，高层链表是低层链表的“快速通道”。

参考资料:

  1. deepseek prompt:简要介绍下跳跃表这个数据结构
  2. Skip List Explained
  3. Skip Lists CMSC 420