跳表（skiplist）Java实现

package com.db.one; import java.util.Random; public class SkipList<T extends Comparable<? super T>> { private int level; private int length; private SkipNode<T> header; private static int MAX_LEVEL = 10; Random ram = new Random(); public SkipList(){ this(MAX_LEVEL); } @SuppressWarnings("unchecked") public SkipList(int maxLevel){ level = maxLevel; header = new SkipNode(0,level); for (int i = 0; i< this.header.getLevel(); i++) { this.header.setForward(i, null); } } public int getRandom(int min, int max) { return ram.nextInt(max) % (max - min + 1) + min; } @SuppressWarnings("unchecked") public void insert(T key){ int nodeLevel = this.getRandom(1, level); SkipNode<T> newNode = new SkipNode<T>(key,nodeLevel); SkipNode<T>[] temp = new SkipNode[level]; SkipNode<T> ptr = header; for(int i = level - 1;i>=0;--i){ //倒序遍历 while(ptr.getForward(i)!=null&&ptr.getForward(i).getKey().compareTo(key) < 0){ //直到最后一个比要插入值大的节点 ptr = ptr.getForward(i); } temp[i] = ptr; } //将新节点插入对应位置 并设置好跳跃表 for(int i=0;i<nodeLevel;++i){ newNode.setForward(i, temp[i].getForward(i)); temp[i].setForward(i, newNode); } System.out.println(key); } public T search(T key){ SkipNode<T> ptr = header; int tempLevel = level-1; while(tempLevel >= 0 && ptr.getForward(tempLevel) != null){ if(key.equals(ptr.getForward(tempLevel).getKey())){ return ptr.getForward(tempLevel).getKey(); } else if(key.compareTo(ptr.getForward(tempLevel).getKey()) < 0){ //进入下一层 --tempLevel; }else{ ptr = ptr.getForward(tempLevel); } } return null; } }