数据结构基础06——线性数据结构之跳表
增加了向前指针(或者叫向下指针)的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
实现场景
如果我们给有一个有序的链表，需要找到属性值为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
* @p