スキップリストJava

スキップ リスト Java は、要素のサブシーケンスに接続するリンク リスト階層を利用して要素の並べ替えリストを保存するために使用されるデータ構造です。スキップ リストを使用すると、アイテムの検索を効率的に処理できます。スキップ リストは確率的データ構造です。つまり、リスト全体のいくつかの要素をスキップするため、スキップ リストと呼ばれます。スキップ リストをリンク リストの拡張バージョンとみなすことができます。リンク リストで要素の挿入、削除、検索を実行できるのと同様に、スキップ リストでも要素の検索、リストからの要素の削除、および要素の挿入が可能です。これには、後続の要素のリンク階層を維持する一連の要素を含む基本リストが含まれます。

広告 このカテゴリーの人気コース JAVA マスタリー - スペシャライゼーション | 78 コース シリーズ | 15 回の模擬テスト

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

構文:

スキップ リストには特定の構文はありませんが、アルゴリズムがあります。アルゴリズムを見る前に、基本的なスキップ リスト操作の種類を確認する必要があります。

• 挿入操作: スキップ リストでは、特定の状況で特定の場所に新しいノードを追加するために使用されます
• 検索操作: スキップリストでは、特定のノードを検索するために使用されます
• 削除操作: スキップリストでは、特定の状況でノードを削除するために使用されます

Java でのスキップ リストの仕組み

それでは、スキップ リストが実際にアルゴリズム的にどのように機能するかを見てみましょう。

挿入アルゴリズム

ステップ 1: リスト内の各要素がノードで表され、ノードのレベルがリストへの挿入時にランダムに選択されるため、ノード レベルを決定します

ステップ 2: ノードのレベルは以下の手順に基づいて決定されます

ステップ 3: スキップ リスト内のレベル数の上限となる最大レベルを見つけます。これは、L(N) = logp/2N によって決定されます。これにより、ランダム レベルが最大レベル

より大きくなることが保証されます。

ステップ 4: 挿入は最上位レベルから開始され、現在のノードの次のノードを比較します

ステップ 5: 次のノード キーが挿入されたキーより小さい場合、同じレベルで先に進むことができます

ステップ 6: 次のノード キーが挿入されたキーよりも大きい場合は、現在のノード I へのポインターを保存し、1 レベル下に移動して検索を続行する必要があります。

検索アルゴリズム

ステップ 1: 要素の検索は、スキップ リストに要素を挿入する場所を検索するのとよく似ています。

ステップ 2: 次のノード キーが検索キーより小さい場合、同じレベルに進むことができます

ステップ 3: 次のノード キーが挿入されたキーよりも大きい場合は、現在のノード I へのポインターを保存し、1 レベル下に移動して検索を続行する必要があります。

ステップ 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 とは何か、およびスキップ リストからの要素の検索、挿入、削除/削除のアルゴリズムと Java がどのように連携するかを見てきました。また、スキップ リストのすべての操作を一度に実行する良い例も用意してください。思いついた他の例やロジックを試してみることもできます。スキップ リストの概念は、データ構造における主要なアルゴリズムの 1 つであるどのプログラミング言語でも同じです。

以上がスキップリストJavaの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。