Java 跳过列表

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

广告 该类别中的热门课程 JAVA 掌握 - 专业化 | 78 课程系列 | 15 次模拟测试

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

语法：

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

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

Java 中跳跃列表的工作

那么让我们看看跳过列表实际上是如何以算法方式工作的。

插入算法

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

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

第 3 步： 查找最大级别为跳跃列表中级别计数的上限，由 L(N) = logp/2N 确定。这确保随机级别将大于最大级别

第四步：从最高层开始插入，比较当前节点的下一个节点

第5步：如果下一个节点的key小于插入的key，那么我们可以以相同的级别前进

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

搜索算法

第 1 步： 由于搜索元素与在跳过列表中搜索位置插入元素非常相似。

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

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

第 4 步： 在最低级别，如果最右边元素的下一个元素的键等于搜索键，那么我们就找到了该键，否则失败。

删除算法

第 1 步： 要删除任何元素（例如 k），首先我们需要使用搜索算法在跳过列表中找到该元素。

第 2 步： 一旦我们使用搜索算法找到了元素，就会像在单链表中一样，进行指针重新排列以从列表中删除该元素。

第3步：我们需要从跳跃列表的最低级别开始，重新排列I而不是元素k旁边的元素。

第4步：删除元素后，可能会出现级别没有元素的情况，所以我们需要通过递减Skip list级别来删除这些级别。

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();
}
}

输出：

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

结论

至此，我们就结束这个主题“Skip List Java”了。我们已经了解了 Java 的跳跃列表是什么以及它如何与搜索、插入和从跳跃列表中删除/删除元素的算法一起使用。另外，有一个很好的例子，一次性完成了跳跃列表的所有操作。您仍然可以尝试使用您可能想到的其他示例或逻辑。跳表的概念在任何编程语言中都是一样的，是数据结构中的主要算法之一。

以上是Java 跳过列表的详细内容。更多信息请关注PHP中文网其他相关文章！