跳表在Java中的实现-一休教程

跳表是一种数据结构，用于借助连接到元素子序列的链表层次结构来存储元素的排序列表。跳表允许以有效的方式处理项目查找。跳表是一种概率数据结构，这意味着它跳过整个列表中的几个元素，因此称为跳表。我们可以将跳表作为链表的扩展版本。与链表允许插入、删除和搜索元素的方式类似，跳表也允许搜索元素、从列表中删除元素和插入元素。它将包含一个基本列表，其中包含一组元素，这些元素将维护后续元素的链接层次结构。

语法：

跳表没有特定的语法，但它有一个算法。在研究算法之前，我们需要检查基本跳表操作的类型。

插入操作：在跳表中，用于在特定情况下向特定位置添加新节点
搜索操作：在跳表中，用于搜索特定节点
删除操作：在跳表中，用于删除特定情况下的节点

让我们看看跳表是如何以算法的方式工作的。

插入算法：

步骤1：确定节点级别，因为列表中的每个元素都由节点表示，并且在插入列表时随机选择节点的级别

步骤2：根据以下步骤确定节点的级别

步骤3：找到最大级别是跳表中级别计数的上限，该上限由L（N）=logp/2N确定。这确保了随机级别将大于最大级别

步骤4：插入从最高级别开始，并比较当前节点的下一个节点

步骤5：如果“下一个节点关键点”小于“插入的关键点”，则可以使用相同级别继续前进

步骤6：如果next node key大于inserted key，那么我们需要存储一个指向当前节点I的指针，并向下移动一级继续搜索。

搜索算法：

步骤1：因为搜索元素非常类似于搜索一个点以在跳表中插入元素。

步骤2：如果下一个节点键小于搜索键，那么我们可以在同一级别上前进

步骤3：如果next node key大于inserted key，那么我们需要存储一个指向当前节点I的指针，并向下移动一级继续搜索。

步骤4：在最低级别，如果最右侧元素的下一个元素具有与搜索键相等的键，那么我们已经找到了键，否则这是一个失败。

删除算法：

步骤1：要删除任何元素，比如k，首先我们需要使用搜索算法在跳表中定位该元素。

第2步：一旦我们使用搜索算法找到了元素，指针重新排列将从列表中删除该元素，就像我们在单个链接列表中所做的那样。

步骤3：我们需要从跳过列表的最低级别开始，重新排列I not元素k旁边的元素。

步骤4：删除元素后，可能会出现没有元素的级别的情况，因此我们需要通过减少跳表级别来删除这些级别。

示例：Java中的跳表

import java.util.Iterator;
import java.util.Random;
import java.util.NoSuchElementException;
public class SkipListJava<K extends Comparable<K>, V> implements Iterable<K> {
private int listsize;
private double pb;
protected static final Random randomGen = new Random();
protected static final double DEFAULT_PB = 0.5;
private NodeKeyValue<K, V> head;
public SkipListJava() {
this(DEFAULT_PB);
}
public SkipListJava(double pb) {
this.head = new NodeKeyValue<K, V>(null, null, 0);
this.pb = pb;
this.listsize = 0;
}
public V get(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey().compareTo(key) == 0)
return listnode.getValue();
else
return null;
}
public void add(K key, V value) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) {
listnode.setValue(value);
return;
}
NodeKeyValue<K, V> newlistNode = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, newlistNode);
int curLevel = listnode.getLevel();
int headlistLevel = head.getLevel();
while (isBuildLevel()) {
if (curLevel >= headlistLevel) {
NodeKeyValue<K, V> newHeadEle = new NodeKeyValue<K, V>(null, null, headlistLevel + 1);
verticalLink(newHeadEle, head);
head = newHeadEle;
headlistLevel = head.getLevel();
}
while (listnode.getUp() == null) {
listnode = listnode.getPrevious();
}
listnode = listnode.getUp();
NodeKeyValue<K, V> tmp = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, tmp);
verticalLink(tmp, newlistNode);
newlistNode = tmp;
curLevel++;
}
listsize++;
}
public void remove(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode == null || listnode.getKey().compareTo(key) != 0)
throw new NoSuchElementException("Key does not exist!");
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
NodeKeyValue<K, V> previous = null;
NodeKeyValue<K, V> next = null;
for (; listnode != null; listnode = listnode.getUp()) {
previous = listnode.getPrevious();
next = listnode.getNext();
if (previous != null)
previous.setNext(next);
if (next != null)
next.setPreviousVal(previous);
}
while (head.getNext() == null && head.getDownList() != null) {
head = head.getDownList();
head.setUp(null);
}
listsize--;
}
public boolean contains(K key) {
return get(key) != null;
}
public int listsize() {
return listsize;
}
public boolean empty() {
return listsize == 0;
}
protected NodeKeyValue<K, V> findNode(K key) {
NodeKeyValue<K, V> listnode = head;
NodeKeyValue<K, V> next = null;
NodeKeyValue<K, V> down = null;
K nodeKey = null;
while (true) {
next = listnode.getNext();
while (next != null && lessThanEqual(next.getKey(), key)) {
listnode = next;
next = listnode.getNext();
}
nodeKey = listnode.getKey();
if (nodeKey != null && nodeKey.compareTo(key) == 0)
break;
down = listnode.getDownList();
if (down != null) {
listnode = down;
} else {
break;
}
}
return listnode;
}
protected void checkKeyValid(K key) {
if (key == null)
throw new IllegalArgumentException("Key must be not null!");
}
protected boolean lessThanEqual(K a, K b) {
return a.compareTo(b) <= 0;
}
protected boolean isBuildLevel() {
return randomGen.nextDouble() < pb;
}
protected void horizontalInsertList(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
b.setPreviousVal(a);
b.setNext(a.getNext());
if (a.getNext() != null)
a.getNext().setPreviousVal(b);
a.setNext(b);
}
protected void verticalLink(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
a.setDown(b);
b.setUp(a);
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
NodeKeyValue<K, V> listnode = head;
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
while (listnode != null) {
stringbuild.append(listnode.toString()).append("\n");
listnode = listnode.getNext();
}
return stringbuild.toString();
}
@Override
public Iterator<K> iterator() {
return new SkipListIterator<K, V>(head);
}
protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
private NodeKeyValue<K, V> listnode;
public SkipListIterator(NodeKeyValue<K, V> listnode) {
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
this.listnode = listnode;
}
@Override
public boolean hasNext() {
return this.listnode != null;
}
@Override
public K next() {
K result = listnode.getKey();
listnode = listnode.getNext();
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
protected static class NodeKeyValue<K extends Comparable<K>, V> {
private K key;
private V value;
private int skiplevel;
private NodeKeyValue<K, V> up, down, next, previous;
public NodeKeyValue(K key, V value, int skiplevel) {
this.key = key;
this.value = value;
this.skiplevel = skiplevel;
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
stringbuild.append("Node[")
.append("key:");
if (this.key == null)
stringbuild.append("None");
else
stringbuild.append(this.key.toString());
stringbuild.append(", value:");
if (this.value == null)
stringbuild.append("None");
else
stringbuild.append(this.value.toString());
stringbuild.append("]");
return stringbuild.toString();
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public int getLevel() {
return skiplevel;
}
public void setLevel(int skiplevel) {
this.skiplevel = skiplevel;
}
public NodeKeyValue<K, V> getUp() {
return up;
}
public void setUp(NodeKeyValue<K, V> up) {
this.up = up;
}
public NodeKeyValue<K, V> getDownList() {
return down;
}
public void setDown(NodeKeyValue<K, V> down) {
this.down = down;
}
public NodeKeyValue<K, V> getNext() {
return next;
}
public void setNext(NodeKeyValue<K, V> next) {
this.next = next;
}
public NodeKeyValue<K, V> getPrevious() {
return previous;
}
public void setPreviousVal(NodeKeyValue<K, V> previous) {
this.previous = previous;
}
}
public static void main(String[] args) {
SkipListJava<Integer, String> skip = new SkipListJava<>();
for (int i = 20; i < 35; i++) {
skip.add(i, String.valueOf(i));
}
System.out.println(skip);
assert skip.listsize() == 10;
int count = 0;
for (Integer i : skip)
assert i.equals(count++);
skip.remove(23);
System.out.println(skip);
skip.remove(25);
skip.remove(33);
skip.remove(30);
System.out.println(skip);
skip.remove(28);
skip.add(25, "25");
System.out.println(skip);
assert skip.listsize() == 0;
assert skip.empty();
}
}

输出：

跳表在Java中的实现插图

我们编写了此代码，用于添加到跳表、在跳表中搜索以及从跳表中删除。

小结

跳表的概念在任何编程语言中都是相同的，它是数据结构中的主要算法之一。

免责声明：本文系转载，版权归原作者所有；旨在传递信息，不代表一休教程网的观点和立场。

跳表在Java中的实现

语法：

插入算法：

搜索算法：

删除算法：

小结

文章展示

Java9中新增的Collector

Java线程优先级

Java正则表达式API系列一

Java8接口–默认方法和静态方法

Java中的按值调用和按引用调用

Java 8中的Collectors API详解

排行榜展示

hs2姿势mod教程（hs2解锁姿势插件）

如何将Windows10电脑的默认下载位置更改为D盘

华夏网赚论坛（华夏免费版论坛）

哪里可以写黄文赚钱（哪里可以写黄文赚钱的软件）

上传91视频可以赚钱吗（91上传作品能赚钱吗）

美国赚钱可以拿回中国用吗（美国挣得钱能拿回中国吗）

跳表在Java中的实现

语法：

插入算法：

搜索算法：

删除算法：

小结

相关文章

文章展示

排行榜展示