跳变是一种高效的搜索结构，是对链表的一种优化，如下图所示，以下图片均摘自博客，原始的链表结构如下图，实现查找、删除和插入复杂度都为O(n)，因为需要遍历链表
而跳表的思想如下，即多加一些索引，高层的索引跳跃连接，可以更快地抵达要查找的目标节点，查找时先从最高层索引开始，高速前进，当下一个节点的值大于要查找的值时就进入下一层，相当于减速，直到最底层找到目标节点
相对于原始链表，优势在于高层索引可以快速跨越，能实现
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)级别的查找、删除和插入，计算如下，其实是一种近似的计算方法，默认在每一层只查找一次，然后就进入下一层，则查找的次数就是跳表的高度h，但是一般情况下每一层肯定不止找一次，因此最小的查找次数就是跳表的高度h，关键是求得h，通过找规律很容易得出：
一级索引的节点为
n
/
2
n/2
n/2，二级索引的节点数为
n
/
4
n/4
n/4，则第k级索引的节点数为
n
/
2
k
n/2^k
n/2k，最高级索引H通常只有两个节点，即头尾，因此满足
2
=
n
/
2
H
2=n/2^H
2=n/2H，解得
H
=
l
o
g
2
n
−
1
H=log_2n-1
H=log2n−1，再加上原始的链表得到跳表的层数为
h
=
H
+
1
=
l
o
g
2
n
h=H+1=log_2n
h=H+1=log2n，因此时间复杂度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)。
Java实现如下，相对于红黑树等二分查找结构实现更简单
import java.util.Random;
class SkipList {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node();
private Random random = new Random();
class Node {
private int data;
// forwards: 存储该节点在各个level索引的下一个节点
private Node[] forwards = new Node[MAX_LEVEL];
private int maxLevel;
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{data: ");
sb.append(data);
sb.append("; level: ");
sb.append(maxLevel);
sb.append(" }");
return sb.toString();
}
}
public Node find(int value) {
// 查找的时候从最顶层开始，因为最顶层跨度大，可以很快接近要查找的值
Node p = head;
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value)
// 在这一层一直找，直到找到最后一个小于value的节点，然后跳出进入下一层查找
p = p.forwards[i];
}
if (p.forwards[0] != null && p.forwards[0].data == value)
// p.forwards[0]：p的第0层的下一个节点，如果是value 那就找到了，否则没找到
return p.forwards[0];
return null;
}
public void insert(int value) {
Node p = head;
int level = randomLevel();
Node node = new Node();
node.data = value;
node.maxLevel = level;
Node update[] = new Node[level]; // 更新level级以下的所有索引
for (int i = level - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value)
p = p.forwards[i];
// 找到这一层里面小于value的最后一个节点，然后保存在update中，下次在这里插入新节点
update[i] = p;
}
for (int i = 0; i < level; i++) {
// 这里实际上就是链表的插入，很简单，相当于每一层都插入一个
node.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = node;
}
if (levelCount < level)
levelCount = level; // 当前最大层数
}
public void delete(int value) {
Node[] deleteNode = new Node[MAX_LEVEL];
Node p = head;
for (int i = levelCount - 1; i >= 0; i--) {
// 先找到它在这一层的最后一个比要删除节点小的节点
while (p.forwards[i] != null && p.forwards[i].data < value)
p = p.forwards[i];
deleteNode[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value)
// p.forwards[0] != null && p.forwards[0].data == value 首先保证这个节点在跳表中
for (int i = levelCount - 1; i >= 0; i--)
if (deleteNode[i] != null && deleteNode[i].forwards[i].data == value)
// 相当于把中间要删除的那个节点的连接断开，跨到它后面那个节点
deleteNode[i].forwards[i] = deleteNode[i].forwards[i].forwards[i];
}
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
private int randomLevel() {
int level = 0;
for (int i = 0; i < MAX_LEVEL; i++) {
if (random.nextInt() % 2 == 1) {
level++;
}
}
return level;
}
}
public class main {
public static void main(String[] args) {
SkipList list = new SkipList();
list.insert(1);
list.insert(4);
list.insert(3);
list.insert(5);
list.printAll();
}
}