在这里记录自己查询网上资料后自己实现的JAVA版本跳表的代码，比较简陋。实现过程中遇到个低级错误，在方法内部尝试修改实参引用的指向是无效的（实际上修改的是形参指向，方法内部只能修改实参指向的具体内容，无法修改实参指向），以后一定切记。
public class SkipList {
private Node head, tail; //最左上头结点，最右上尾结点
private Random random = new Random(); //用于生成随机数
private static final double PROMOTE_RATE = 0.5; //结点向上扩展的概率
private static final int MAX_LEVEL = 32; //允许最大层级
private static int current_max_level = 0; //当前最大层级
/**
* 链表结点
*/
public class Node {
int data;
Node up, down, left, right;
public Node(int data) {
this.data = data;
}
}
/**
* 跳表构造函数
*/
public SkipList() {
head = new Node(Integer.MIN_VALUE);
tail = new Node(Integer.MAX_VALUE);
head.right = tail;
tail.left = head;
}
/**
* 查询最底层链表中是否存在值为data的结点
* @param data
* @return
*/
public boolean search(int data) {
return findData(data).data == data;
}
/**
* 查询最底层链表中最接近且值小于等于data的结点
* @param data
* @return
*/
private Node findData(int data) {
Node node = head;
while(true) {
while(node.right.data <= data) {
node = node.right;
}
if(node.down == null)
break;
node = node.down;
}
return node;
}
/**
* 插入值为data的结点
* @param data
*/
public void insert(int data) {
Node preNode = findData(data);
if(preNode.data == data)
return;
Node newNode = new Node(data);
appendNode(preNode,newNode);
int level = 0;
while(random.nextDouble() < PROMOTE_RATE) {
if(level >= current_max_level && level < MAX_LEVEL)
addLevel();
if(level < current_max_level) {
while(preNode.up == null && preNode.left != null) {
preNode = preNode.left;
}
preNode = preNode.up;
Node extend = new Node(data);
appendNode(preNode,extend);
extendNode(newNode,extend);
newNode = extend;
}
level++;
}
}
/**
* 删除值为data的结点
* @param data
* @return
*/
public boolean erase(int data) {
Node node = findData(data);
if(node.data != data)
return false;
while(true) {
if(current_max_level != 0 && node.left.data == Integer.MIN_VALUE && node.right.data == Integer.MAX_VALUE) {
cutLevel();
break;
}
node.left.right = node.right;
if(node.up == null) {
break;
}
node = node.up;
}
return true;
}
/**
* 垂直扩展结点
* @param preNode 新向上扩展的结点的down结点
* @param extendNode 新向上扩展的结点
*/
private void extendNode(Node preNode,Node extendNode) {
extendNode.down = preNode;
preNode.up = extendNode;
}
/**
* 水平扩展结点
* @param preNode 新添加结点的left结点
* @param nextNode 新添加的结点
*/
private void appendNode(Node preNode,Node nextNode) {
nextNode.right = preNode.right;
preNode.right.left = nextNode;
preNode.right = nextNode;
nextNode.left = preNode;
}
/**
* 向上添加一个层级
*/
private void addLevel() {
Node newHead = new Node(Integer.MIN_VALUE);
Node newTail = new Node(Integer.MAX_VALUE);
newHead.right = newTail;
newTail.left = newHead;
newHead.down = head;
head.up = newHead;
newTail.down = tail;
tail.up = newTail;
head = newHead;
tail = newTail;
current_max_level++;
}
/**
* 向下减少一个层级
*/
private void cutLevel() {
head = head.down;
tail = tail.down;
current_max_level--;
}
/**
* 输出最底层链表
*/
public void printList() {
Node node = head;
while(node.down != null) {
node = node.down;
}
while(node != null) {
if(node.data != Integer.MIN_VALUE && node.data != Integer.MAX_VALUE) {
System.out.print(node.data + " ");
}
node = node.right;
}
System.out.println();
}
}