增加了向前指针(或者叫向下指针)的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
实现场景
如果我们给有一个有序的链表，需要找到属性值为x的节点。 因为链表自身的特性，每次查找都需要一次遍历O（n）。现在我们需要对它进行优化来提高查找效率，在保持原有链表不变的情况下（如：不把链表变成数组通过散列映射，见散列表）有哪些优化方法呢？其中一个比较好的办法就是跳表（就是比较废内存...）
在说跳表之前首先需要说的是二分查找。
猜数字游戏（应该都写过吧~）：给定1 - 100中的随机一个数x，玩家猜一个数字，告诉你大了还是小了或者猜到了。问需要猜几次？每次我们取其中一半，逐渐缩小。如：50，25，12...对于n个数字，猜到的时间复杂度为O（logn）非常高效。
同理，如果我们在链表中找数字x前，先看x/2节点的值是大还是小，再向前遍历不就可以了吗？当然当我们在x/2节点过程中不能用遍历。
时间不够空间来凑。我们只需要在原有的链表基础上创建一个新的节点对象Node_m,其中 Node_m 包含中间节点的引用（其实是随机出的节点）和排序的分值。每次通过 Node_m 去找到对应的中间节点即可，然后判断大了还是小了进行向前或者向后查找（如果是单链表，就是从头开始，还是从中间开始向后查找）。就可以了
继续优化
如果我们要找的数字刚好在这个链表在前半部分或者最后。如：1 - 10亿，而我们要找的数字刚好是4_9999_9999。不还是从头开始遍历吗？这个时候，我们就可以考虑拆分粒度。二分查找可以变成三查找，四分查找，五分查找..X分查找（其实是概率函数）。
这样我们需要的外部节点就不是只有 Node_m 一个节点了，而是x个节点组成的集合，我们将这m个节点组成一个新的线性表。就相当于在原来的链表上面再加一层链表（索引），链表中的每一个节点都额外加指向原始链表的引用：
继续优化
如果原始链表的大小实在太大，如：10亿数据，我们上层的索引平均对应每100个一个节点，那么索引也要1千万个节点。遍历1千万节点的链表也需要一定的时间，有没有什么更快的办法呢？很简单，这就回到了我们最初问题的递归。有没有什么办法可以让一个链表查找速度更快呢？有加一层索引~
上述这种链表加多级索引的结构就称之为——跳表了。
插入和删除
跳表的查询操作实际上，如上所示。而且跳表的插入、删除操作的时间复杂度也是 O(logn)！在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是 O(1)。但是，这里为了保证原始链表中数据的有序性，我们需要先找到要插入的位置，这时就需要遍历O（n）来找到要插入位置。但是，对于跳表来说，查找的复杂度是 O(logn)，所以这里查找某个数据应该插入的位置，方法也是类似的，时间复杂度也是 O(logn)。如下：
再来看删除操作。
如果删除的这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点。当然，如果我们用的是双向链表，就不需要考虑这个问题了。
索引的更新
当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。
作为一种动态数据结构，跳表需要维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。
这里可以通过随机函数来维护前面提到的“平衡性”。当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。
也就是前面我们所谓的“n分查找”，不是基于一半或者多少个而是随机函数。
随机函数的选择很有讲究，从概率上来讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能过度退化。至于随机函数的选择，感兴趣的话，可以去了解Redis 中关于有序集合的跳表实现。
import java.util.Random;
/**
* 1，跳表的一种实现方法，用于练习。跳表中存储的是正整数，并且存储的是不重复的。
* 2，本类是参考作者zheng ，自己学习，优化了添加方法
* 3，看完这个，我觉得再看ConcurrentSkipListMap 源码，会有很大收获
* Author：ldb
*/
public class SkipList2 {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
/**
* 带头链表
*/
private Node head = new Node(MAX_LEVEL);
private Random r = new Random();
public Node find(int value) {
Node p = head;
// 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
/**
* 优化了作者zheng的插入方法
*
* @param value 值
*/
public void insert(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一层，如果条件满足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
Node p = head;
// 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
// levelCount 会 > level，所以加上判断
if (level > i) {
update[i] = p;
}
}
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
}
/**
* 优化了作者zheng的插入方法2
*
* @param value 值
*/
public void insert2(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一层，如果条件满足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node p = head;
// 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
// levelCount 会 > level，所以加上判断
if (level > i) {
if (p.forwards[i] == null) {
p.forwards[i] = newNode;
} else {
Node next = p.forwards[i];
p.forwards[i] = newNode;
newNode.forwards[i] = next;
}
}
}
}
/**
* 作者zheng的插入方法，未优化前，优化后参见上面insert()
*
* @param value
* @param level 0 表示随机层数，不为0，表示指定层数，指定层数
* 可以让每次打印结果不变动，这里是为了便于学习理解
*/
public void insert(int value, int level) {
// 随机一个层数
if (level == 0) {
level = randomLevel();
}
// 创建新节点
Node newNode = new Node(level);
newNode.data = value;
// 表示从最大层到低层，都要有节点数据
newNode.maxLevel = level;
// 记录要更新的层数，表示新节点要更新到哪几层
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
/**
*
* 1，说明：层是从下到上的，这里最下层编号是0，最上层编号是15
* 2，这里没有从已有数据最大层（编号最大）开始找，（而是随机层的最大层）导致有些问题。
* 如果数据量为1亿，随机level=1 ，那么插入时间复杂度为O（n）
*/
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
// 这里update[i]表示当前层节点的前一节点，因为要找到前一节点，才好插入数据
update[i] = p;
}
// 将每一层节点和后面节点关联
for (int i = 0; i < level; ++i) {
// 记录当前层节点后面节点指针
newNode.forwards[i] = update[i].forwards[i];
// 前一个节点的指针，指向当前节点
update[i].forwards[i] = newNode;
}
// 更新层高
if (levelCount < level) levelCount = level;
}
public void delete(int value) {
Node[] update = new Node[levelCount];
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];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}
/**
* 随机 level 次，如果是奇数层数 +1，防止伪随机
*
* @return
*/
private int randomLevel() {
int level = 1;
for (int i = 1; i < MAX_LEVEL; ++i) {
if (r.nextInt() % 2 == 1) {
level++;
}
}
return level;
}
/**
* 打印每个节点数据和最大层数
*/
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
/**
* 打印所有数据
*/
public void printAll_beautiful() {
Node p = head;
Node[] c = p.forwards;
Node[] d = c;
int maxLevel = c.length;
for (int i = maxLevel - 1; i >= 0; i--) {
do {
System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
} while (d[i] != null && (d = d[i].forwards)[i] != null);
System.out.println();
d = c;
}
}
/**
* 跳表的节点，每个节点记录了当前节点数据和所在层数数据
*/
public class Node {
private int data = -1;
/**
* 表示当前节点位置的下一个节点所有层的数据，从上层切换到下层，就是数组下标-1，
* forwards[3]表示当前节点在第三层的下一个节点。
*/
private Node forwards[];
/**
* 这个值其实可以不用，看优化insert()
*/
private int maxLevel = 0;
public Node(int level) {
forwards = new Node[level];
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
}