社区精选 | 数据结构与算法-跳表
今天小编为大家带来的是社区作者 半夏之沫 的文章，在这篇文章中他将带领大家学习跳表的实现。
让我们一起来了解吧~
前言
跳表可以达到和红黑树一样的时间复杂度 O(logN)，且实现简单，Redis 中的有序集合对象的底层数据结构就使用了跳表。本篇文章将对跳表的实现进行学习。
正文
一. 跳表的基础概念
跳表，即跳跃表（Skip List），是基于并联的链表数据结构，操作效率可以达到O(logN)，对并发友好，跳表的示意图如下所示。
跳表的特点，可以概括如下。
跳表是多层（level）链表结构；
跳表中的每一层都是一个有序链表，并且按照元素升序（默认）排列；
跳表中的元素会在哪一层出现是随机决定的，但是只要元素出现在了第 k 层，那么 k 层以下的链表也会出现这个元素；
跳表的底层的链表包含所有元素；
跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数；
跳表中的节点包含两个指针，一个指针指向同层链表的后一节点，一个指针指向下层链表的同元素节点。
二. 跳表的节点
public class SkiplistNode {
public int data;
public SkiplistNode next;
public SkiplistNode down;
public int level;
public SkiplistNode(int data, int level) {
this.data = data;
this.level = level;
}
}
三. 跳表的初始化
public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;
public int curLevel;
public Random random;
public Skiplist() {
random = new Random();
//headNodes用于存储每一层的头节点
headNodes = new LinkedList<>();
//tailNodes用于存储每一层的尾节点
tailNodes = new LinkedList<>();
//初始化跳表时，跳表的层数随机指定
curLevel = getRandomLevel();
//指定了跳表的初始的随机层数后，就需要将每一层的头节点和尾节点创建出来并构建好关系
SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
for (int i = 0; i <= curLevel; i++) {
head.next = tail;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
}
}
四. 跳表的添加方法
public void add(int num) {
//获取本次添加的值的层数
int level = getRandomLevel();
//如果本次添加的值的层数大于当前跳表的层数
//则需要在添加当前值前先将跳表层数扩充
if (level > curLevel) {
expanLevel(level - curLevel);
}
//curNode表示num值在当前层对应的节点
SkiplistNode curNode = new SkiplistNode(num, level);
//preNode表示curNode在当前层的前一个节点
SkiplistNode preNode = headNodes.get(curLevel - level);
for (int i = 0; i <= level; i++) {
//从当前层的head节点开始向后遍历，直到找到一个preNode
//使得preNode.data < num <= preNode.next.data
while (preNode.next.data < num) {
preNode = preNode.next;
}
//将curNode插入到preNode和preNode.next中间
curNode.next = preNode.next;
preNode.next = curNode;
//如果当前并不是0层，则继续向下层添加节点
if (curNode.level > 0) {
SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
//curNode指向下一层的节点
curNode.down = downNode;
//curNode向下移动一层
curNode = downNode;
}
//preNode向下移动一层
preNode = preNode.down;
}
}
private void expanLevel(int expanCount) {
SkiplistNode head = headNodes.getFirst();
SkiplistNode tail = tailNodes.getFirst();
for (int i = 0; i < expanCount; i++) {
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
}
}
五. 跳表的搜索方法
目标值大于当前节点的后一节点值时，继续在本层链表上向后搜索；
目标值大于当前节点值，小于当前节点的后一节点值时，向下移动一层，从下层链表的同节点位置向后搜索；
目标值等于当前节点值，搜索结束。
public boolean search(int target) {
//从顶层开始寻找，curNode表示当前遍历到的节点
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == target) {
//找到了目标值对应的节点，此时返回true
return true;
} else if (curNode.next.data > target) {
//curNode的后一节点值大于target
//说明目标节点在curNode和curNode.next之间
//此时需要向下层寻找
curNode = curNode.down;
} else {
//curNode的后一节点值小于target
//说明目标节点在curNode的后一节点的后面
//此时在本层继续向后寻找
curNode = curNode.next;
}
}
return false;
}
六. 跳表的删除方法
首先按照跳表的搜索的方式，搜索待删除节点，如果能够搜索到，此时搜索到的待删除节点位于该节点层数的最高层；
从待删除节点的最高层往下，将每一层的待删除节点都删除掉，删除方式就是让待删除节点的前一节点直接指向待删除节点的后一节点。
public boolean erase(int num) {
//删除节点的遍历过程与寻找节点的遍历过程是相同的
//不过在删除节点时如果找到目标节点，则需要执行节点删除的操作
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == num) {
//preDeleteNode表示待删除节点的前一节点
SkiplistNode preDeleteNode = curNode;
while (true) {
//删除当前层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点
preDeleteNode.next = curNode.next.next;
//当前层删除完后，需要继续删除下一层的待删除节点
//这里让preDeleteNode向下移动一层
//向下移动一层后，preDeleteNode就不一定是待删除节点的前一节点了
preDeleteNode = preDeleteNode.down;
//如果preDeleteNode为null，说明已经将底层的待删除节点删除了
//此时就结束删除流程，并返回true
if (preDeleteNode == null) {
return true;
}
//preDeleteNode向下移动一层后，需要继续从当前位置向后遍历
//直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值
//此时preDeleteNode就又变成了待删除节点的前一节点
while (preDeleteNode.next.data != num) {
preDeleteNode = preDeleteNode.next;
}
}
} else if (curNode.next.data > num) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}
七. 跳表完整代码
public class Skiplist {
public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;
public int curLevel;
public Random random;
public Skiplist() {
random = new Random();
//headNodes用于存储每一层的头节点
headNodes = new LinkedList<>();
//tailNodes用于存储每一层的尾节点
tailNodes = new LinkedList<>();
//初始化跳表时，跳表的层数随机指定
curLevel = getRandomLevel();
//指定了跳表的初始的随机层数后，就需要将每一层的头节点和尾节点创建出来并构建好关系
SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
for (int i = 0; i <= curLevel; i++) {
head.next = tail;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
}
}
public boolean search(int target) {
//从顶层开始寻找，curNode表示当前遍历到的节点
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == target) {
//找到了目标值对应的节点，此时返回true
return true;
} else if (curNode.next.data > target) {
//curNode的后一节点值大于target
//说明目标节点在curNode和curNode.next之间
//此时需要向下层寻找
curNode = curNode.down;
} else {
//curNode的后一节点值小于target
//说明目标节点在curNode的后一节点的后面
//此时在本层继续向后寻找
curNode = curNode.next;
}
}
return false;
}
public void add(int num) {
//获取本次添加的值的层数
int level = getRandomLevel();
//如果本次添加的值的层数大于当前跳表的层数
//则需要在添加当前值前先将跳表层数扩充
if (level > curLevel) {
expanLevel(level - curLevel);
}
//curNode表示num值在当前层对应的节点
SkiplistNode curNode = new SkiplistNode(num, level);
//preNode表示curNode在当前层的前一个节点
SkiplistNode preNode = headNodes.get(curLevel - level);
for (int i = 0; i <= level; i++) {
//从当前层的head节点开始向后遍历，直到找到一个preNode
//使得preNode.data < num <= preNode.next.data
while (preNode.next.data < num) {
preNode = preNode.next;
}
//将curNode插入到preNode和preNode.next中间
curNode.next = preNode.next;
preNode.next = curNode;
//如果当前并不是0层，则继续向下层添加节点
if (curNode.level > 0) {
SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
//curNode指向下一层的节点
curNode.down = downNode;
//curNode向下移动一层
curNode = downNode;
}
//preNode向下移动一层
preNode = preNode.down;
}
}
public boolean erase(int num) {
//删除节点的遍历过程与寻找节点的遍历过程是相同的
//不过在删除节点时如果找到目标节点，则需要执行节点删除的操作
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == num) {
//preDeleteNode表示待删除节点的前一节点
SkiplistNode preDeleteNode = curNode;
while (true) {
//删除当前层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点
preDeleteNode.next = curNode.next.next;
//当前层删除完后，需要继续删除下一层的待删除节点
//这里让preDeleteNode向下移动一层
//向下移动一层后，preDeleteNode就不一定是待删除节点的前一节点了
preDeleteNode = preDeleteNode.down;
//如果preDeleteNode为null，说明已经将底层的待删除节点删除了
//此时就结束删除流程，并返回true
if (preDeleteNode == null) {
return true;
}
//preDeleteNode向下移动一层后，需要继续从当前位置向后遍历
//直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值
//此时preDeleteNode就又变成了待删除节点的前一节点
while (preDeleteNode.next.data != num) {
preDeleteNode = preDeleteNode.next;
}
}
} else if (curNode.next.data > num) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}
private void expanLevel(int expanCount) {
SkiplistNode head = headNodes.getFirst();
SkiplistNode tail = tailNodes.getFirst();
for (int i = 0; i < expanCount; i++) {
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
}
}
private int getRandomLevel() {
int level = 0;
while (random.nextInt(2) > 1) {
level++;
}
return level;
}
}
总结
关注公众号：拾黑（shiheibook）了解更多
赞助链接：
关注数据与安全，洞悉企业级服务市场：https://www.ijiandao.com/
四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/
关注网络尖刀微信公众号随时掌握互联网精彩
赞助链接
微信扫码关注公众号