本篇博客主要介绍一下跳跃表的原理和简单实现。
增加了向前指针的链表叫做跳表，跳表全称跳跃表，简称跳表。
我们知道，在一个单链表中如果想要根据值来查找一个元素，时间复杂度为
O
(
N
)
O(N)
O(N)，即使该链表是有序的，也不能通过二分的方式来降低时间复杂度。
如上图，如果我们要查找值为52的元素的结点，我们必须从头结点开始，循环遍历知道找到值为52的结点，也就是最后一个结点，一共比较8次（-INF，负无穷不算）。
我们有没有什么办法来减少访问的次数呢？我们可以试着去开辟一条捷径去访问52。
如上图，我们要查找值为52的结点，只需要在L2层查找4次即可找到。
在这个结构中，查询值为47的结点只需要查询5次。先在L2层查找47，查询4次后找到52，因为链表是有序的，所以我们回退到39，然后去L1层去查找，查询一次就查到了47，所以一共需要查找5次。
我们能不能让查找值为52结点的次数再减少呢？我们可以考虑再开辟一条捷径。
如上图，我们查找值为52的结点只需要在L3层查找2次即可。
查找元素47仍然是最耗时的，需要查询5次。先在L3层查询2次，再在L2层查询2次，最后到L1层查询一次。
从上面的查找过程看，这种思想和二分的思想非常相似，我们再将结构完善一下，最终结构如下：
我们可以看出最耗时的访问仍然是访问值为47的结点，一共需要查询6次。L4层访问52，L3访问25、52，L2访问39、52，L1访问47，共6次。
如果有n个元素，因为是二分，所以层数就应该是
l
o
g
2
N
log_2N
log2N层，再加上自身的1层。
最耗时间的查询自然是访问所有层数，耗时 l o g 2 N + l o g 2 N log_2N + log_2N log2N+log2N，即 2 l o g 2 N 2log_2N 2log2N。为什么是 2 l o g 2 N 2log_2N 2log2N呢？
所以跳跃表的时间复杂度为 O ( l o g 2 N ) O(log_2N) O(log2N)。
从上面跳跃表的时间复杂度的分析我们可以看出，该跳跃表是比较理想的。
但是如果想要在跳跃表中插入或者删除一个元素呢？比如我们插入一个元素22、23、24…，自然是在L1层插入，但是这些元素在L1层插入之后，那么如何调整L2层和L3层的连接来维持这个比较理想的跳跃表呢？
我们知道，平衡二叉搜索树的调整是一件令人非常头疼的事，左旋、右旋、左右旋；而调整一个理想的跳跃表将是一个比调整平衡二叉搜索树还复杂的操作。
但是这里，我们不需要通过复杂的操作调整连接来维护这样完美的跳跃表。有一种基于概率统计的插入算法，也能得到时间复杂度为
O
(
l
o
g
2
N
)
O(log_2N)
O(log2N)的查询效率，这种跳跃表是比较实用的。
从理想跳跃表，我们可以看出，L2层元素的数量是L1层元素数量的
1
/
2
1/2
1/2，L3层元素数量是L2层元素数量的
1
/
2
1/2
1/2，依次类推。从这里，我们可以想到，只要在插入时尽量保证上一层的元素个数是下一层元素的
1
/
2
1/2
1/2，我们的跳跃表就能成为理想的跳跃表。
那么如何在插入时保证上一层元素的个数是下一层元素个数的
1
/
2
1/2
1/2呢？我们可以通过抛硬币的方式来决定。
插入操作依赖于查询操作，所以插入操作的时间复杂度同样为 O ( l o g 2 N ) O(log_2N) O(log2N)。
删除操作和普通的链表删除操作完全一样，直接删除元素，然后调整一下删除元素后的指针就可以了。
删除操作同样依赖于查询操作，所以删除操作的时间复杂度同样也是
O
(
l
o
g
2
N
)
O(log_2N)
O(log2N)。
代码实现可参考：
