对于二分查找算法，其底层依赖支持随机查找特性的数组，一般情况下只能依靠数组来实现。但是，如果数据存储在链表中，是否可以实现二分查找算法呢？
为此，需要引入一种新型的动态数据结构，跳表（Skip List）。跳表可以支持快速的插入、删除和查找操作，甚至可以替代红黑树。
对于一个单链表，即使其中存储的数据是有序的，如果我们想要查找特定的值，也只能从头到尾进行遍历，时间复杂度为O(n)。
为了提高查找效率，我们可以使用额外的链表来建立查找索引，每两个结点提取一个结点到上一级，把抽取出来的一级称作索引或索引层。索引层中的每一个结点有一个down指针，该指针指向其下一级结点。
这样，如果我们要查找特定的值，例如16，便可以首先对第一级索引层进行遍历，当查找到值为13的结点时，发现其下一个结点的值为17，因为数据是有序存储的，那么16肯定在这两个结点之间。此时，只需要通过13结点的down指针转移到原始链表的13结点处，再对原始链表的13到17结点之间的元素进行查找即可很快找到值为16的结点。
在上述查找过程中，利用第一级索引层，从原先需要遍历10个结点降低为只需要遍历7个结点，跳过了中间的多个结点，查找效率大幅度提高。
在第一级索引的基础上，还可以继续增加第二级索引，对于第一级索引中的值，每两个结点创建一个结点，如下图所示。
这样，如果要查找值为16的结点，就只需要遍历6个结点。
在上述例子中，由于原始结点数目不多，查找效率的提升不明显。但是，当原始结点的数目很大时，查找效率就会得到明显提升。
在单链表中查询某个数据的时间复杂度为O(n)。那么，跳表的查询时间复杂度是多少？
假设链表中有n个结点，按照每两个结点抽取一个结点作为上一级索引的结点，那么第一级索引有n/2个结点，第二级索引有n/4个结点，即：第k级索引的结点个数是第k-1级索引的结点个数的1/2，第k级索引结点的个数为 n / ( 2 k ) n/(2^{^{k}}) n/(2k)。
假设索引有h级，最高级的索引有两个结点，那么 n / ( 2 h ) = 2 n/(2^{^{h}})=2 n/(2h)=2，求得 h = l o g 2 n − 1 h=log{_{2}}^{n}-1 h=log2n−1，加上原始链表，整个跳表的高度为 l o g 2 n log{_{2}}^{n} log2n。假设，在跳表中查询某个数据时，每一层都需要遍历m个结点，那么在跳表中查询一个数据的时间复杂度为 O ( m ∗ l o g n ) ) O(m*log{_{}}^{n})) O(m∗logn))。
如果使用上述的跳表结构，那么在每一级遍历时，最多只需要遍历3个结点。原因在于，当我们从当前级跳转到下一级索引时，当前级的两个结点之间最多只存在3个结点，那么每级最多也只需要遍历3个结点。
因此，在跳表中查询任意数据的时间复杂度就是
O
(
l
o
g
n
)
)
O(log{_{}}^{n}))
O(logn))。查找的时间复杂度和二分查找相同。
跳表的空间复杂度如下所示：
上述等比数列的和为n-2，那么空间复杂度为O(n)。也就是说，为包含n个结点的单链表构建多级索引构成跳表，需要额外使用接近n个结点的存储空间。
如果每三个结点或这五个结点抽取一个结点构成上级索引，如下图所示：
空间复杂度的计算方式如下图所示：
和为n/2，空间复杂度同样是O(n)，但是相比于间隔为2，减少了一般的索引结点存储空间。
在实际工程中，单链表中的每一结点所存储的对象可能很大，此时，在构建索引结点时，只需要存储关键值和指针，不需要存储对象，因而当对象比索引结点大很多时，索引结点所占用的额外空间可以忽略不计。
跳表除了支持查找操作之外还支持动态的插入、删除操作，插入、删除操作的时间复杂度也是
O
(
l
o
g
n
)
)
O(log{_{}}^{n}))
O(logn))。
在单链表中，如果要找到特定的位置并执行插入操作，查找操作比较耗时，而插入的时间复杂度为
O
(
1
)
O(1)
O(1)。而对于跳表来说，查找某个特定的插入位置的时间复杂度为
O
(
l
o
g
n
)
)
O(log{_{}}^{n}))
O(logn))，找到插入位置后，插入操作的时间复杂度同样为
O
(
1
)
O(1)
O(1)。如下图所示：
在进行删除操作时，我们需要考虑的一点时，所删除的结点可能会在索引中出现，此时要同时删除索引中的对应结点。在进行删除操作时，要注意获取被删除结点的前驱结点。
如下图所示，假如一直往原始列表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从 O(logn) 退化为 O(n)。那这种问题该怎么解决呢？我们需要在插入数据的时候，索引节点也需要相应的增加、或者重建索引，来避免查找效率的退化。那我们该如何去维护这个索引呢？
比较容易理解的做法就是完全重建索引，我们每次插入数据后，都把这个跳表的索引删掉全部重建，重建索引的时间复杂度是多少呢？因为索引的空间复杂度是 O(n)，即：索引节点的个数是 O(n) 级别，每次完全重新建一个 O(n) 级别的索引，时间复杂度也是 O(n) 。造成的后果是：为了维护索引，导致每次插入数据的时间复杂度变成了 O(n)。
那有没有其他效率比较高的方式来维护索引呢？假如跳表每一层的晋升概率是 1/2，最理想的索引就是在原始链表中每隔一个元素抽取一个元素做为一级索引。换种说法，我们在原始链表中随机的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率呢？ 当然可以了，因为一般随机选的元素相对来说都是比较均匀的。如下图所示，随机选择了n/2 个元素做为一级索引，虽然不是每隔一个元素抽取一个，但是对于查找效率来讲，影响不大，比如我们想找元素 16，仍然可以通过一级索引，使得遍历路径较少了将近一半。如果抽取的一级索引的元素恰好是前一半的元素 1、3、4、5、7、8，那么查找效率确实没有提升，但是这样的概率太小了。我们可以认为：当原始链表中元素数量足够大，且抽取足够随机的话，我们得到的索引是均匀的。我们要清楚设计良好的数据结构都是为了应对大数据量的场景，如果原始链表只有 5 个元素，那么依次遍历 5 个元素也没有关系，因为数据量太少了。所以，我们可以维护一个这样的索引：随机选 n/2 个元素做为一级索引、随机选 n/4 个元素做为二级索引、随机选 n/8 个元素做为三级索引，依次类推，一直到最顶层索引。这里每层索引的元素个数已经确定，且每层索引元素选取的足够随机，所以可以通过索引来提升跳表的查找效率。
那代码该如何实现，才能使跳表满足上述这个样子呢？可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推，就能满足我们上面的条件。现在我们就需要一个概率算法帮我们把控这个 1/2、1/4、1/8 … ，当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。下面开始讲解这个概率算法代码如何实现。
我们可以实现一个 randomLevel() 方法，该方法会随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），且该方法有 1/2 的概率返回 1、1/4 的概率返回 2、1/8的概率返回 3，以此类推。
所以，通过 randomLevel() 方法，我们可以控制整个跳表各级索引中元素的个数。重点来了：randomLevel() 方法返回 2 的时候会建立一级索引，我们想要一级索引中元素个数占原始数据的 1/2，但是 randomLevel() 方法返回 2 的概率为 1/4，那是不是有矛盾呢？明明说好的 1/2，结果一级索引元素个数怎么变成了原始链表的 1/4？我们先看下图，应该就明白了。
假设我们在插入元素 6 的时候，randomLevel() 方法返回 1，则我们不会为 6 建立索引。插入 7 的时候，randomLevel() 方法返回3 ，所以我们需要为元素 7 建立二级索引。这里我们发现了一个特点：当建立二级索引的时候，同时也会建立一级索引；当建立三级索引时，同时也会建立一级、二级索引。所以，一级索引中元素的个数等于 [ 原始链表元素个数 ] * [ randomLevel() 方法返回值 > 1 的概率 ]。因为 randomLevel() 方法返回值 > 1就会建索引，凡是建索引，无论几级索引必然有一级索引，所以一级索引中元素个数占原始数据个数的比率为 randomLevel() 方法返回值 > 1 的概率。那 randomLevel() 方法返回值 > 1 的概率是多少呢？因为 randomLevel() 方法随机生成 1~MAX_LEVEL 的数字，且 randomLevel() 方法返回值 1 的概率为 1/2，则 randomLevel() 方法返回值 > 1 的概率为 1 - 1/2 = 1/2。即通过上述流程实现了一级索引中元素个数占原始数据个数的 1/2。
同理，当 randomLevel() 方法返回值 > 2 时，会建立二级或二级以上索引，都会在二级索引中增加元素，因此二级索引中元素个数占原始数据的比率为 randomLevel() 方法返回值 > 2 的概率。 randomLevel() 方法返回值 > 2 的概率为 1 减去 randomLevel() = 1 或 =2 的概率，即 1 - 1/2 - 1/4 = 1/4。OK，达到了我们设计的目标：二级索引中元素个数占原始数据的 1/4。
但是问题又来了，怎么设计这么一个 randomLevel() 方法呢？直接撸代码：
// 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
// 1/2 的概率返回 1
// 1/4 的概率返回 2
// 1/8 的概率返回 3 以此类推
private int randomLevel() {
int level = 1;
// 当 level < MAX_LEVEL，且随机数小于设定的晋升概率时，level 1
while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
level += 1;
return level;
}