对一个有序数组进行二分查找，是程序员的一项基本功。二分查找的时间复查度O(logN)，效率比较高。那么对于有序数组的近亲—-有序链表，有没有一种类似二分查找的算法呢？当然有，那就是跳跃表。
跳跃表是对有序链表进行快速查询的，平均时间复杂度O(logN)，查找速度可与二分查找相同，速度甚至可与平衡二叉树媲美。相对于平衡二叉树来说，跳跃表不需要进行左旋、右旋等操作来保持“平衡”，实现起来也更加简单。很多领域都才用了跳跃表，例如redis的有序集合。另外，一个哥们去阿里面试，有一道没回答的面试题目“如何让链表的元素查询接近线性时间？”我觉得他是再问跳跃表，也就是这个原因写了这个博文。
跳跃表是什么鬼？#
开始之前，先举个例子：
对于图的有序链表，如果要查找45，需要经过<3,5,9,12,25,21,34>节点，但是如果找200(一个不存在的值)，那么需要全部遍历一遍才能知道。一个一个的找思想，也太慢了吧。
那么我们对这个链表进行改造，成这样的
再查询45的话，只需经过<3,15,15,34,34>即可，如图
如果查询200(不存在的值)，只需要经过图中路径即可，不需要遍历全部节点。
是不是很爽，是不是有二分查找的感觉。
这就是跳跃表
跳跃表的性质如下：
- 1.由很多层结构组成
- 2.每一层都是一个有序的链表
- 3.最底层(Level 1)的链表包含所有元素
- 4.如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
- 5.每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
这样是不是豁然开朗了。