数据结构（一）--- 跳跃表

1、简述

跳跃表（skiplist）是一种优秀的数据查找结构，查找原理类似于2分查找，平均的查找时间复杂度为O(logN)；

其底层基于链表实现，但区别在于含有多层，每个节点的每层都有指向表尾方向最近一个节点的指针；

各种语言对跳跃表的实现可能不同，但主要原理是相同的，所以这里只是所以下原理，

• 
  

• 图中是含有四层结构的跳跃表，bw是指向前一个节点的指针，每个节点只有一个，删除时方便。

• 每个节点都含有一个或多个指向表尾最近一个节点的指针。

• 最底层（L1层）包含所有的节点。

• 图中bw笔者参考了Redis实现的跳跃表结构，自主添加上的，便于更好的理解。

2、查询

 跳跃表的优秀表现在于查询功能，以上图中查找值为90的节点为例，如果在链表中继续要进行顺序查找，需要进行9步才能查询到，而在上图的跳跃表中则需要6步就能完成，具体步骤如下：

（1）由最高层L4层开始查询，L4层当前节点值10，小于90，则取当前点的下一个节点120，大于90，这时降层到L3层查找；即查找值处于当前节点的值和当前节点下一节点的值之间时，降层查询。

（2）当前节点为10，L3层，取其下一节点40比较，小于90，进行下一步。

（3）节点40，取其下一节点80比较，小于90，进行下一步。

（4）节点80，取其下一节点120比较，大于90，此时将80设置为当前节点，并在当前节点上降层，进行下一步。

（5）当前节点80，L2层，取下一节点100比较，大于90，当前节点不变，直接降层，进行下一步。

（6）当前节点80，L1层，取下一节点90比较，等