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中文網其他相關文章！