Java跳跃表
Carol淋 人气:0跳表全称叫做跳跃表，简称跳表，是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序列表上面增加多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也提高插入和删除的性能，redis中的有序集合set就是用跳表实现的，面试时候也经常会问。
这里我们原始数据个数n=10，以间隔k=2建立索引，则第一层索引10/2=5个，第二层⌈10/2^2⌉=3个，第三层⌈10/2^3⌉=2个，第四层⌈10/2^4⌉=1个。根据上图我们来分析一下，跳表的结构是一棵树（除原始数据层外），树的左指针指向对应的下一层链表的节点，右指针指向当前链表的下一个节点，且树高为log(n)，对于每一层需要比较的次数最多为k，则时间复杂度为O(k*log(n))，k为常数项，所以跳表查询时间复杂度为O(log(n))。因为需要额外的空间存储索引，是典型的以空间换时间，空间复杂度为O(n)。
接下来我们自己实现一个跳表：
节点数据结构定义：根据跳表结构，节点首先需要一个value存储当前节点值，需要一个next指针指向同一层的下一个节点，需要一个nodeValue指针指向下一层对应节点，但是这里为了插入删除方便，引入了一个prev指针，指向同一层的上一个节点。
class Node {
//当前节点值
private Integer value;
//当前节点所属链表下一个节点
private Node next;
//当前节点所属链表上一个节点
private Node prev;
//当前节点指向的另一个索引链表/原始值链表节点
private Node nodeValue;
Node(Integer value) {
this.value = value;
}
}初始化一个跳表：跳表的建立需要在数据有序的基础上，然后从下往上在下一层的基础上，间隔k生成当前层的节点，新生成的节点需要与当前层上一个节点连接起来，并且指向生成它的下一层节点。
/**
* 原始数据链表
*/
private Node head ;
/**
* 最终的跳表结构：保存索引链表及原始链表
*/
private List<Node> indexList;
/**
* 跳表层数
*/
private int level;
/**
* 初始化
*/
public void init() {
//带头节点的链表，便于操作
head = new Node(-1);
head.next = head;
indexList = new ArrayList<>();
level = 0;
}
/**
* 初始化跳表
* @param k 间隔
* @param nums 原始数据（已排序）
*/
public void init(int k, int[] nums) {
//初始化数据链表
Node temp = head;
for (int num : nums) {
Node cur = new Node(num);
cur.prev = temp;
temp.next = cur;
temp = temp.next;
}
//新节点保存（最底层）
indexList.add(head);
//循环生成索引结构，结束条件，当层仅一个元素
temp = head.next;
while (true) {
//当前链表第几个元素
int i = 0;
//生成另一条链表长度
int size = 0;
Node indexNode = new Node(-1);
indexNode.next = indexNode;
Node indexNodeTemp = indexNode;
while (null != temp) {
//间隔k生成节点
if (i % k == 0) {
Node curNode = new Node(temp.value);
curNode.nodeValue = temp;
curNode.prev = indexNodeTemp;
indexNodeTemp.next = curNode;
indexNodeTemp = indexNodeTemp.next;
++ size;
}
++ i;
temp = temp.next;
}
indexList.add(indexNode);
temp = indexNode.next;
//当生成的索引链表仅1时不需要再继续生成
if (size == 1) {
break;
}
}
level = indexList.size();
}从跳表中查找元素：从最顶层索引链表开始查找，找到第一个大于当前节点的元素，则需要查找的元素在当前节点与之前节点之间，则从当前节点的上一个节点prev往下nodevalue继续进行查找，直到当前节点值与查找值相等，则直接返回当前节点，返回的节点可能是索引节点，也可能是原始数据节点，如果需要找到原始数据节点，则通过nodeValue继续往下找。
/**
* 是否存在num
* @param num
* @return
*/
public boolean hasNum(int num) {
Node result = this.findNum(num);
return null != result;
}
/**
* 查找num（返回的可能是索引，也可能是原始数据，根据nodeValue可以判断，也可以找到原始数据）
* @param num
*/
public Node findNum(int num) {
//跳表结构indexList是数据-》第一层索引-》第二层索引-》。。。。
//1.直接匹配到
//2.找到第一个大于当前元素的数，找前一个
Node node = indexList.get(indexList.size() - 1).next;
Node last = null;
while (null != node) {
if (node.value == num) {
//已经找到元素
return node;
}
if (node.value > num) {
if (null == last) {
//比最小值还小
return null;
}
//找到了第一个大于num的索引node
//到下一层去继续找
node = last.nodeValue;
last = null;
continue;
}
last = node;
node = null != node.next ? node.next : node.nodeValue;
}
return null;
}删除节点：首先通过上面的查找方法找到目标节点，如果目标节点是索引值，则需要从当前索引层，层层往下删除包括原始数据链表，如果是原始数据值，则直接删除，暂不调整。
/**
* 构建索引时：自底向上逐层构建，如果索引需要删除（当两个索引之间没有任何数据时候，删除）
* @param num
* @return
*/
public boolean remove(int num) {
Node node = this.findNum(num);
if (null == node) {
//不需要移除
return false;
}
if (null == node.nodeValue) {
//数据链表，可以直接移除
//是否最后一个节点
if (null == node.next) {
node.prev.next = null;
return true;
}
node.next.prev = node.prev;
node.prev.next = node.next;
return true;
}
//当前在索引上，自上而下删除索引及数据
while (null != node) {
Node cur = node.nodeValue;
if (null == node.next) {
node.prev.next = null;
} else {
node.next.prev = node.prev;
node.prev.next = node.next;
}
node = cur;
}
return true;
}新增节点：新增节点时候，如果不对索引进行调整，极端情况下，每次新增的节点都在之前第一层两个节点之间，当这之间的链表越变越长，时间复杂度直接退化为O(n)，所以需要同时新增索引，维持跳表的高效性。但是我们如何新增，有一个方法就是，在新增节点时，随机选择k，即第k级索引，从1～k新增索引。
/**
* 首先需要查找插入位置，如果比最小的还小，直接在前面插入
* 否则需要从最顶级一直查找到数据链表，找到插入位置，插入，在查找的过程中，就可以开始插入索引节点，
* 从上往下进行插入
* @param num
*/
public void add(int num) {
int k = this.generatorLevelK();
//寻找插入点的过程和查找过程基本一致
//顶级索引链表
Node node = indexList.get(indexList.size() - 1).next;
int index = 1;
while (null != node) {
//找到第一个node.value >= num的元素，在前面插入
if (node.value >= num) {
//已经找到,前插
if (index >= k) {
Node newNode = new Node(num);
Node temp = node.prev;
newNode.next = temp.next;
temp.next.prev = newNode;
newNode.prev = temp;
temp.next = newNode;
}
//找的时候往后面找的，但是当前已经先于num了，下一次再往后面找，就出现问题
if (null == node.prev.prev) {
//第一个节点就符合条件
node = node.nodeValue;
continue;
}
node = node.prev.nodeValue;
++ index;
continue;
}
//没有找到，但是当前已经是链表最后一个元素了
if (null == node.next) {
if (index >= k) {
Node newNode = new Node(num);
newNode.prev = node;
node.next = newNode;
}
if (null == node.prev.prev) {
//第一个节点就符合条件
node = node.nodeValue;
continue;
}
node = node.prev.nodeValue;
++ index;
continue;
}
node = node.next;
}
}
private int generatorLevelK() {
Random random = new Random();
return random.nextInt(level);
}至此，我们实现了一个跳表的定义，初始化，查找，节点新增与删除。
加载全部内容