public class SkipNode {
public int element;
public SkipNode next = null;
//public SkipNode pre = null;
public SkipNode down = null;
//public SkipNode up = null;
public SkipNode( int e ) {
this.element = e;
}
public SkipNode(SkipNode n) {
this.element = n.element;
}
}
跳表中的成员变量
- 左上角第一个结点，这里不存储元素，设置值为-1
- 索引层数（不包括原始链表，初始为0）
- 原始链表的元素数量
- 随机数
public SkipNode first = new SkipNode( -1 ); // 跳表左上角第一个结点，不存储元素，值设置为-1
int usedlevel = 0; // 跳表的索引层数
int size = 0; // 原始链表中的元素数量
Random r = new Random(); // 随机数
在跳表中查找元素
遍历跳表，找不到则返回null，思路类似二分查找，时间复杂度O(logn)
public SkipNode find(int key) {
SkipNode p = first;
while (p != null && p.down != null) {
if (p.next != null && key >= p.next.element) {
p = p.next; // 比右边大或相等时向右
} else if (p.next == null || key < p.next.element) {
p = p.down; // 否则向下
}
}
while (p.next != null && key >= p.next.element ) { // 到达底层后右边可能还有元素
p = p.next;
}
if( p.element != -1 && key == p.element) return p;
return null;
}
在跳表中插入元素
由于每增加一个新元素都重新构造链表结构的代价太大，这里采取的是“概率”的思路，即既然标准跳表每一层索引的大小都是其上一层索引大小的二分之一，那么下层索引的每个元素也出现在其上层索引中的概率（即元素向上爬升的概率）也是二分之一。所以理论上，只要构造跳表时，每插入一个元素，都按照这个几率计算这个元素爬升的索引层数，那么当元素数量足够多时，就能构造出标准跳表。
具体插入步骤如下：
- 用随机数生成需要爬升的索引数量
- 构造完索引后，从最上层索引开始插入元素，对每一层，先在该层插入元素，而后将该层插入的结点与上一层插入的结点相连
时间复杂度为O(logn)
public SkipNode insert( int key ) {
if( find(key) != null ) return null; // 节点已存在不插入
SkipNode node = new SkipNode( key );
int level = getLevel(); // 随机数看新插入值是否建立索引，每层索引有1/2机会被建立
if ( level > usedlevel ) addlevel(level - usedlevel); // 索引不够用时建立新索引
SkipNode p = first;
while (usedlevel - level > 0) {
p = p.down;
level++;
} // 获得最高更新索引层的头结点
SkipNode oldnode = null;
while (p != null) { // 更新索引及结点
while (p.next != null && p.next.element < key) {//往右搜索
p = p.next;
}
node.next = p.next;
p.next = node; //这一层
if (oldnode != null) oldnode.down = node; //上一层
oldnode = node; // 下一层
if (p.down != null) node = new SkipNode(node);
p = p.down;
}
size++;//跳表中的元素数量加一
return node;
}
public void addlevel(int x) {
for (int i = 0; i < x; i++) { // 每层建立一个头结点
SkipNode newfirst = new SkipNode(-1);
newfirst.next = null;
newfirst.down = first;
first = newfirst;
}
usedlevel = x + usedlevel;
}
int getLevel() { // 随机获得爬升索引层
int level = 0;
for (int i = 0; i <= usedlevel; i++) { // 每层有1/2几率爬升，这样生成的表，数据越多越接近标准跳表
if (r.nextInt(2) == 1) level++;
else break;
}
//System.out.println(level);
return level;
}
在跳表中删除元素
- 寻找指定结点在最高层索引上的前置结点
- 从该层开始向下，在每层索引及原始链表上删除对应元素
- 删除空索引
查找过程依然类似二分法，时间复杂度O(logn)
private SkipNode findPreNode(int key) {
SkipNode p = first;
while (p != null && p.down != null) {
if (p.next != null && key > p.next.element) {
p = p.next; // 比右边大时向右
} else if (p.next != null && key == p.next.element) {
return p; // 与右边相等时返回自身
} else if (p.next == null || key < p.next.element) {
p = p.down; // 否则向下
}
}
while (p.next != null) { // 到达底层后右边可能还有元素
if (key == p.next.element) {
//System.out.println(p.element.value);
return p;
}
p = p.next;
}
return null; // 无前置结点
}
public int remove(int key) {
if( first.next == null ) return -1; // 链表为空，返回-1
SkipNode p = findPreNode(key);//找到待删除元素的最上层的前一个节点
if (p == null) { // 结点不存在
return -1;
}
int value = p.next.element; // 记录待删除元素
while (p != null && p.next != null ) { //找到每层待删除元素的前一个节点，并在该层删除元素
p.next = p.next.next;
p = p.down;//往下遍历，直到最底下一层
while (p != null && p.next.element != key) {
p = p.next;
}
}
// 删除仅剩头结点的索引（下面称为空索引）
p = first;
int newlevel = usedlevel; // 计算索引层数减少量
while (p.down != null && p.next == null) { // 删除连续空索引
p = p.down;
newlevel--;
}
first = p;
usedlevel = newlevel;
size--;
return value;
}
展示跳表中元素
public void show( ) {
SkipNode p = first;
while( p != null ) {
SkipNode p1 = p;
while( p1 != null ) {
System.out.print( p1.element );
System.out.print( " " );
p1 = p1.next;
}
p = p.down;
System.out.println();
}
}
测试
测试代码：
public static void main(String[] args) { // Test
Skiplist l = new Skiplist();
l.insert(1);
l.insert(2);
l.insert(4);
l.insert(6);
l.insert(5);
l.insert(5);
l.insert(0);
//System.out.println(l.find(5).element);
l.show();
l.remove(5);
l.remove(1);
l.remove(4);
l.show();
}
输出：
-1 0 6 -1 0 2 6 -1 0 1 2 4 5 6 -1 0 6 -1 0 2 6 -1 0 2 6整体代码
import java.util.Random;
public class Skiplist {
public SkipNode first = new SkipNode( -1 ); // 跳表左上角第一个结点
int usedlevel = 0; // 跳表的索引层数
int size = 0; // 原始链表中的元素数量
Random r = new Random(); // 随机数
public static void main(String[] args) { // Test
Skiplist l = new Skiplist();
l.insert(1);
l.insert(2);
l.insert(4);
l.insert(6);
l.insert(5);
l.insert(5);
l.insert(0);
//System.out.println(l.find(5).element);
l.show();
l.remove(5);
l.remove(1);
l.remove(4);
l.show();
}
public SkipNode getFirst( ) {
SkipNode p = first;
while( p.down != null ) p = p.down;
return p;
}
public SkipNode find(int key) {
SkipNode p = first;
while (p != null && p.down != null) {
if (p.next != null && key >= p.next.element) {
p = p.next; // 比右边大或相等时向右
} else if (p.next == null || key < p.next.element) {
p = p.down; // 否则向下
}
}
while (p.next != null && key >= p.next.element ) { // 到达底层后右边可能还有元素
p = p.next;
}
if( p.element != -1 && key == p.element) return p;
return null;
}
private SkipNode findPreNode(int key) {
SkipNode p = first;
while (p != null && p.down != null) {
if (p.next != null && key > p.next.element) {
p = p.next; // 比右边大时向右
} else if (p.next != null && key == p.next.element) {
return p; // 与右边相等时返回自身
} else if (p.next == null || key < p.next.element) {
p = p.down; // 否则向下
}
}
while (p.next != null) { // 到达底层后右边可能还有元素
if (key == p.next.element) {
//System.out.println(p.element.value);
return p;
}
p = p.next;
}
return null; // 无前置结点
}
public int remove(int key) {
if( first.next == null ) return -1; // 链表为空，返回-1
SkipNode p = findPreNode(key);//找到待删除元素的最上层的前一个节点
if (p == null) { // 结点不存在
return -1;
}
int value = p.next.element; // 记录待删除元素
while (p != null && p.next != null ) {
p.next = p.next.next;
p = p.down;//往下遍历，直到最底下一层
while (p != null && p.next.element != key) {
p = p.next;
}//找到每层待删除元素的前一个节点
}
// 删除仅剩头结点的索引（下面称为空索引）
p = first;
int newlevel = usedlevel; // 计算索引层数减少量
while (p.down != null && p.next == null) { // 删除连续空索引
p = p.down;
newlevel--;
}
first = p;
usedlevel = newlevel;
size--;
return value;
}
public SkipNode insert( int key ) {
if( find(key) != null ) return null; // 节点已存在不插入
SkipNode node = new SkipNode( key );
int level = getLevel(); // 随机数看新插入值是否建立索引，每层索引有1/2机会被建立
if ( level > usedlevel ) addlevel(level - usedlevel); // 索引不够用时建立新索引
SkipNode p = first;
while (usedlevel - level > 0) {
p = p.down;
level++;
} // 获得最高更新索引层的头结点
SkipNode oldnode = null;
while (p != null) { // 更新索引及结点
while (p.next != null && p.next.element < key) {//往右搜索
p = p.next;
}
node.next = p.next;
p.next = node; //这一层
if (oldnode != null) oldnode.down = node; //上一层
oldnode = node; // 下一层
if (p.down != null) node = new SkipNode(node);
p = p.down;
}
size++;//跳表中的元素数量加一
return node;
}
public void addlevel(int x) {
for (int i = 0; i < x; i++) { // 每层建立一个头结点
SkipNode newfirst = new SkipNode(-1);
newfirst.next = null;
newfirst.down = first;
first = newfirst;
}
usedlevel = x + usedlevel;
}
int getLevel() { // 随机获得爬升索引层
int level = 0;
for (int i = 0; i <= usedlevel; i++) { // 每层有1/2几率爬升，这样生成的表，数据越多越接近标准跳表
if (r.nextInt(2) == 1) level++;
else break;
}
//System.out.println(level);
return level;
}
public void show( ) {
SkipNode p = first;
while( p != null ) {
SkipNode p1 = p;
while( p1 != null ) {
System.out.print( p1.element );
System.out.print( " " );
p1 = p1.next;
}
p = p.down;
System.out.println();
}
}
public class SkipNode {
public int element;
public SkipNode next = null;
//public SkipNode pre = null;
public SkipNode down = null;
//public SkipNode up = null;
public SkipNode( int e ) {
this.element = e;
}
public SkipNode(SkipNode n) {
this.element = n.element;
}
}
}
