跳表

跳表是一种基于有序链表的数据结构，支持快速插入、删除、查找操作，其时间复杂度为O(log n)，比普通链表的O(n)更高效。

https://cmps-people.ok.ubc.ca/ylucet/DS/SkipList.html

图一

图二

图三

跳表的特性有这么几点：

• 一个跳表结构由很多层数据结构组成。
• 每一层都是一个有序的链表，默认是升序。也可以自定义排序方法。
• 最底层链表（图中所示Level1）包含了所有的元素。
• 如果每一个元素出现在LevelN的链表中（N>1)，那么这个元素必定在下层链表出现。
• 每一个节点都包含了两个指针，一个指向同一级链表中的下一个元素，一个指向下一层级别链表中的相同值元素。

跳表的查找

跳表的插入

跳表插入数据的流程如下：

1. 找到元素适合的插入层级K，这里的K采用随机的方式。若K大于跳表的总层级，那么开辟新的一层，否则在对应的层级插入。
2. 申请新的节点。
3. 调整对应的指针。

假设我要插入元素13，原有的层级是3级，假设K=4：

倘若K=2：