跳跃表 Skip Listtype
status
date
slug
summary
tags
category
icon
password
Property
跳跃表(Skip List)是在链表的基础上增加了“跳跃”的功能，即加上了【多级索引】，通过索引来快速查找，可以支持快速的删除、插入和查找操作。它实际上是一种增加了前向指针的链表，是一种随机化的数据结构。其具有如下性质：
- 由很多层链表组成
- 每一层都是一个有序的链表
- 最底层（level 1）的链表包含所有元素
- 如果一个元素出现在 level i 层的链表中，则它在 level i 之下的链表也都会出现
- 每个节点都包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素
对于下图所示的单链表而言，即使数据是有序的，但是如果想要查找某个数据，只能从头节点开始向后遍历，查询效率低，时间复杂度为：
将其变为跳表形式，则如下图所示：
如果给其继续添加多级索引，那么其结构如下所示：
