# 跳表

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 $O(n)$

可以每隔两个结点建立一个索引，这样查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。

在第一级索引的基础之上，继续每两个结点就建立一个索引，然后构成第二级索引。

以此类推。

这种链表加多级索引的结构，就是『 跳表 』当链表的长度 n 比较大时，比如 1000、10000 的时候，在构建索引之后，查找效率的提升就会非常明显。

# 用跳表查询到底有多快？

# 动态插入和删除元素

# 跳表索引动态更新