插入和删除算法
都是通过查找与连接（search and splice）：
维护一个update数组，在搜索结束之后，update[i]保存的是待插入/删除结点在第i层的左侧结点。
插入
若key不存在，则插入该key与对应的value；若key存在，则更新value。
如果待插入的结点的层数高于跳表的当前层数listLevel，则更新listLevel。
选择待插入结点的层数randomLevel：
randomLevel只依赖于跳表的最高层数和概率值p。
另一种实现方法为，如果生成的randomLevel大于当前跳表的层数listLevel，那么将randomLevel设置为listLevel+1，这样方便以后的查找，在工程上是可以接受的，但同时也破坏了算法的随机性。
删除
删除特定的key与对应的value。如果待删除的结点为跳表中层数最高的结点，那么删除之后，要更新listLevel。
public class SkipList<T> { // 最高层数 private final int MAX_LEVEL; // 当前层数 private int listLevel; // 表头 private SkipListNode<T> listHead; // 表尾 private SkipListNode<T> NIL; // 生成randomLevel用到的概率值 private final double P; // 论文里给出的最佳概率值 private static final double OPTIMAL_P = 0.25; public SkipList() { // 0.25, 15 this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1); } public SkipList(double probability, int maxLevel) { P = probability; MAX_LEVEL = maxLevel; listLevel = 1; listHead = new SkipListNode<T>(Integer.MIN_VALUE, null, maxLevel); NIL = new SkipListNode<T>(Integer.MAX_VALUE, null, maxLevel); for (int i = listHead.forward.length - 1; i >= 0; i--) { listHead.forward[i] = NIL; } } // 内部类 class SkipListNode<T> { int key; T value; SkipListNode[] forward; public SkipListNode(int key, T value, int level) { this.key = key; this.value = value; this.forward = new SkipListNode[level]; } } public T search(int searchKey) { SkipListNode<T> curNode = listHead; for (int i = listLevel; i > 0; i--) { while (curNode.forward[i].key < searchKey) { curNode = curNode.forward[i]; } } if (curNode.key == searchKey) { return curNode.value; } else { return null; } } public void insert(int searchKey, T newValue) { SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL]; SkipListNode<T> curNode = listHead; for (int i = listLevel - 1; i >= 0; i--) { while (curNode.forward[i].key < searchKey) { curNode = curNode.forward[i]; } // curNode.key < searchKey <= curNode.forward[i].key update[i] = curNode; } curNode = curNode.forward[0]; if (curNode.key == searchKey) { curNode.value = newValue; } else { int lvl = randomLevel(); if (listLevel < lvl) { for (int i = listLevel; i < lvl; i++) { update[i] = listHead; } listLevel = lvl; } SkipListNode<T> newNode = new SkipListNode<T>(searchKey, newValue, lvl); for (int i = 0; i < lvl; i++) { newNode.forward[i] = update[i].forward[i]; update[i].forward[i] = newNode; } } } public void delete(int searchKey) { SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL]; SkipListNode<T> curNode = listHead; for (int i = listLevel - 1; i >= 0; i--) { while (curNode.forward[i].key < searchKey) { curNode = curNode.forward[i]; } // curNode.key < searchKey <= curNode.forward[i].key update[i] = curNode; } curNode = curNode.forward[0]; if (curNode.key == searchKey) { for (int i = 0; i < listLevel; i++) { if (update[i].forward[i] != curNode) { break; } update[i].forward[i] = curNode.forward[i]; } while (listLevel > 0 && listHead.forward[listLevel - 1] == NIL) { listLevel--; } } } private int randomLevel() { int lvl = 1; while (lvl < MAX_LEVEL && Math.random() < P) { lvl++; } return lvl; } public void print() { for (int i = listLevel - 1; i >= 0; i--) { SkipListNode<T> curNode = listHead.forward[i]; while (curNode != NIL) { System.out.print(curNode.key + "->"); curNode = curNode.forward[i]; } System.out.println("NIL"); } } public static void main(String[] args) { SkipList<Integer> sl = new SkipList<Integer>(); sl.insert(20, 20); sl.insert(5, 5); sl.insert(10, 10); sl.insert(1, 1); sl.insert(100, 100); sl.insert(80, 80); sl.insert(60, 60); sl.insert(30, 30); sl.print(); System.out.println("---"); sl.delete(20); sl.delete(100); sl.print(); } }
