1）在有序数列里搜索一个数

2）或者把一个数插入到正确的位置

（刚开始一个数都没有，所以解决了这个问题，我们一直用这个策略更新即可）

public static class SkipListNode { public Integer value;//本身的值 public
ArrayList<SkipListNode> nextNodes; //指向下一个元素的结点组成的数组，长度全看脸。 public
SkipListNode(Integer value) { this.value = value; nextNodes = new
ArrayList<SkipListNode>(); } }

private boolean lessThan(Integer a, Integer b) { return a.compareTo(b) < 0; }
private boolean equalTo(Integer a, Integer b) { return a.compareTo(b) == 0; }

// Returns the node at a given level with highest value less than e private
SkipListNode findNext(Integer e, SkipListNode current, int level) {
SkipListNode next = current.nextNodes.get(level); while (next != null) {
Integer value = next.value; if (lessThan(e, value)) { // e < value break; }
current = next; next = current.nextNodes.get(level); } return current; }

// Returns the skiplist node with greatest value <= e private SkipListNode
find(Integer e) { return find(e, head, maxLevel); } // Returns the skiplist
node with greatest value <= e // Starts at node start and level private
SkipListNode find(Integer e, SkipListNode current, int level) { do { current =
findNext(e, current, level); } while (level-- > 0); return current; }

public boolean contains(Integer value) { SkipListNode node = find(value);
return node != null && node.value != null && equalTo(node.value, value); }

public void add(Integer newValue) { if (!contains(newValue)) { size++; int
level = 0; while (Math.random() < PROBABILITY) { level++;//能有几层全看脸 } while
SkipListNode newNode = new SkipListNode(newValue); SkipListNode current =
current.nextNodes.get(level)); current.nextNodes.set(level, newNode); } while
(level-- > 0); } }

public void delete(Integer deleteValue) { if (contains(deleteValue)) {
SkipListNode deleteNode = find(deleteValue); size--; int level = maxLevel;
SkipListNode current = head; do {//就是一个链表删除节点的操作 current =
findNext(deleteNode.value, current, level); if (deleteNode.nextNodes.size() >
level) { current.nextNodes.set(level, deleteNode.nextNodes.get(level)); } }
while (level-- > 0); } }

public static class SkipListIterator implements Iterator<Integer> { SkipList
list; SkipListNode current; public SkipListIterator(SkipList list) { this.list
= list; this.current = list.getHead(); } public boolean hasNext() { return
current.nextNodes.get(0) != null; } public Integer next() { current =
current.nextNodes.get(0); return current.value; } }

import java.util.ArrayList; import java.util.Iterator; public SkipListDemo {
public static class SkipListNode { public Integer value; public
ArrayList<SkipListNode> nextNodes; public SkipListNode(Integer value) {
this.value = value; nextNodes = new ArrayList<SkipListNode>(); } } public
static class SkipListIterator implements Iterator<Integer> { SkipList list;
SkipListNode current; public SkipListIterator(SkipList list) { this.list =
list; this.current = list.getHead(); } public boolean hasNext() { return
current.nextNodes.get(0) != null; } public Integer next() { current =
current.nextNodes.get(0); return current.value; } } public static class
SkipList { private SkipListNode head; private int maxLevel; private int size;
private static final double PROBABILITY = 0.5; public SkipList() { size = 0;
(!contains(newValue)) { size++; int level = 0; while (Math.random() <
maxLevel++; } SkipListNode newNode = new SkipListNode(newValue); SkipListNode
current = head; do { current = findNext(newValue, current, level);
current.nextNodes.set(level, newNode); } while (level-- > 0); } } public void
delete(Integer deleteValue) { if (contains(deleteValue)) { SkipListNode
deleteNode = find(deleteValue); size--; int level = maxLevel; SkipListNode
current = head; do { current = findNext(deleteNode.value, current, level); if
(deleteNode.nextNodes.size() > level) { current.nextNodes.set(level,
deleteNode.nextNodes.get(level)); } } while (level-- > 0); } } // Returns the
skiplist node with greatest value <= e private SkipListNode find(Integer e) {
return find(e, head, maxLevel); } // Returns the skiplist node with greatest
value <= e // Starts at node start and level private SkipListNode find(Integer
e, SkipListNode current, int level) { do { current = findNext(e, current,
level); } while (level-- > 0); return current; } // Returns the node at a given
level with highest value less than e private SkipListNode findNext(Integer e,
SkipListNode current, int level) { SkipListNode next =
current.nextNodes.get(level); while (next != null) { Integer value =
next.value; if (lessThan(e, value)) { // e < value break; } current = next;
next = current.nextNodes.get(level); } return current; } public int size() {
return size; } public boolean contains(Integer value) { SkipListNode node =
find(value); return node != null && node.value != null && equalTo(node.value,
value); } public Iterator<Integer> iterator() { return new
SkipListIterator(this); }
/******************************************************************************
* Utility Functions *
******************************************************************************/
private boolean lessThan(Integer a, Integer b) { return a.compareTo(b) < 0; }
private boolean equalTo(Integer a, Integer b) { return a.compareTo(b) == 0; } }
public static void main(String[] args) { } }