SkipList.java

public void insert(E value)
      {
          SkipNode<E> x = header;  
          SkipNode<E>[] update = new SkipNode[MAX_LEVEL + 1];
  
          for (int i = level; i >= 0; i--) {
  	    while (x.forward[i] != null && x.forward[i].value.compareTo(value) < 0) {
 	        x = x.forward[i];
  	    }
  	    update[i] = x; 
  	}
  	x = x.forward[0];
  
  
         if (x == null || !x.value.equals(value)) {        
             int lvl = randomLevel();
       
             if (lvl > level) {
 	        for (int i = level + 1; i <= lvl; i++) {
 	            update[i] = header;
 	        }
 	        level = lvl;
 	    }
 
             x = new SkipNode<E>(lvl, value);
	    for (int i = 0; i <= lvl; i++) {
 	        x.forward[i] = update[i].forward[i];
 	        update[i].forward[i] = x; 	    }

         }
     }
     
     
    
     private int getLevel(){
      	int lvl = (int)(Math.log(1.-Math.random())/Math.log(1.-P));
		return Math.min(lvl, MAX_LEVEL);
	}
      
      
     class SkipListNode {
      private int value;
	public SkipListNode[] next;//On the same level

	public int getValue(){
		return this.value;
	}
	public void setValue(int x){
		this.value = x;
	}

	public SkipListNode(int x, int level){
		value = x;
		next = new int[level+1];
	}
}