跳表(Skip List)
介绍
跳表是一种基于有序链表的数据结构,通过添加额外的"跳跃"链接,实现了对链表的快速查找。传统的有序链表查找需要从头开始一个一个节点遍历,时间复杂度为O(n),而跳表通过构建多层索引,可以达到平均O(log n)的搜索效率,接近于二叉搜索树。
跳表的核心构想可以类比为图书馆的索引系统或多层电梯:
- 底层链表:完整存储所有数据的有序链表
- 索引层:由底层链表中部分节点"提拔"形成的快速通道
在跳表中,每个节点包含以下几个组成部分:
- 值(value):节点存储的数据
- 前进指针数组(forward array):指向不同层级的后继节点
- 层高(level):该节点的最大层级
核心特性
- 多层结构:由最底层的原始有序链表,以及若干层索引组成
- 概率平衡:通过随机函数决定节点的层数,无需复杂的平衡操作
- 快速查找:能够跳过大量节点,实现对数级别的查找效率
- 有序性:所有节点按关键字排序
...