基本操作
查找操作
跳跃表按照自顶向下的顺序进行查找，也就是从head3开始查找。
- 假设要查找8，head3.next=8，ok！
- 假设要查找7，head3.next=8>7，则指针向下移动到head2，head2.next=4<8，则指针向右移动到4节点，4.next=8>7，指针向下移动到level1层的4节点，4.next=6<7，指针向右移到6节点，6.next=8>7，指针向下移动到level0所在的6节点,6.next=7，ok！（查找轨迹见下图）
可以看出，跳跃表查找操作的思路与二分法较为类似，相比于单向链表逐个遍历要更快些。
删除操作
在查找操作的基础上，只需要找到待删除节点，然后逐个调整每一层待删除节点前一个节点的next指针即可。
添加操作
添加操作相对复杂一些。首先要将元素添加到level0层相应的位置，而level1、level2和level3层是否添加该元素，我们采用基于概率的方法进行判断。首先level0层肯定要添加元素，因为它要包含所有元素。规定添加到每层的概率是1/2。也就是说添加到level1层的概率是1/2，添加到level2层的概率是1/4，添加到level3层的概率是1/8......但是需要记住，如果在第n层没有添加元素，那么在这之上的所有层都不再添加元素。
既然是基于概率，我们可以用随机数进行模拟。跳跃表一共有4层，2的4次方是16，利用随机函数生成一个[0,15)之间的随机整数，如果该随机数在[0,8)之间，在将元素添加到level1；如果该随机数在[0,4)之间，在将元素添加到level1、level2；如果该随机数在[0,1)之间，在将元素添加到level1、level2、level3。
代码实现（Java）
跳跃表的实际结构如下图所示。与上面的结构相比，每个元素并非在每一层都有一个节点，而是将元素所在索引位置的所有层封装成一个节点。
首先需要定义跳跃表节点SkipListNode
public class SkipListNode { private int value; private SkipListNode[] next; // getters setters }然后定义跳跃表SkipList
public class SkipList { private SkipListNode head; private int levelNum; private Random random; private Integer randomLimit; public SkipList(int levelNum) { // levelNum=4 : 0 1 2 3 this.head = new SkipListNode(null, levelNum); // head只存放指向下个节点的指针，不存放元素 this.levelNum = levelNum; this.random = new Random(); this.randomLimit = (int)Math.pow(2, levelNum - 1); } /** * 查找元素 */ public boolean find(Integer value) throws Exception { if(value == null) throw new Exception("The value is null"); if(getNode(value) == null) return false; else return true; } /** * 添加元素 */ public void insert(Integer value) throws Exception { if(value == null) throw new Exception("The value is null"); if(find(value)) throw new Exception("The value already exists"); // 计算level1、level2...是否添加该元素 int level = levelNum - 1; int rand = random.nextInt(randomLimit); int powNum = 0; while(level > 0) { if(rand < Math.pow(2, powNum)) { break; } level--; powNum++; } SkipListNode newNode = new SkipListNode(value, levelNum); SkipListNode preNode = null; SkipListNode curNode = null; SkipListNode tmpNode = null; while(level >= 0) { preNode = head; curNode = head.getNext(level); while(curNode != null) { if(value < curNode.getValue()) { break; } preNode = curNode; curNode = curNode.getNext(level); } tmpNode = preNode.getNext(level); preNode.setNext(level, newNode); newNode.setNext(level, tmpNode); level--; } } // 删除元素 public void delete(Integer value) throws Exception { if(value == null) throw new Exception("The value is null"); if(!find(value)) throw new Exception("The value doesn't exist"); int level = levelNum - 1; SkipListNode preNode = head; SkipListNode curNode = head; Integer curValue = null; while(level >= 0) { curNode = curNode.getNext(level); if(curNode != null) { curValue = curNode.getValue(); if(curValue == value) { break; } else if(curValue < value) { preNode = curNode; } else { curNode = preNode; level--; } } else { curNode = preNode; level--; } }
