Java实现跳跃表的示例详解（跳跃表原理和实现）

跳表全称叫做跳跃表，简称跳表，是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序列表上面增加多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也提高插入和删除的性能，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 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继续进行查找，直到当前节点值与查找值相等，则直接返回当前节点，返回的节点可http://能是索引节点，也可能是原始数据节点，如果需要找到原始数据节点，则通过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);

}

至此，我们实现了一个跳表的定义，初始化，查找，节点新增与删除。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。