検索

スキップ リスト 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>, 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)  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>, 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>, 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 
<p><strong>出力:</strong></p>
<p><img  src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172500410830437.png?x-oss-process=image/resize,p_40" class="lazy" alt="スキップリストJava" ></p>
<p>スキップ リストへの追加、スキップ リスト内での検索、スキップ リストからの削除を行うためにこのコードを作成しました。</p>
<h3 id="結論">結論</h3>
<p>これで、このトピック「スキップ リスト Java」を終了します。スキップ リスト Java とは何か、およびスキップ リストからの要素の検索、挿入、削除/削除のアルゴリズムと Java がどのように連携するかを見てきました。また、スキップ リストのすべての操作を一度に実行する良い例も用意してください。思いついた他の例やロジックを試してみることもできます。スキップ リストの概念は、データ構造における主要なアルゴリズムの 1 つであるどのプログラミング言語でも同じです。</p></integer></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k>

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

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?Mar 17, 2025 pm 05:46 PM

この記事では、Javaプロジェクト管理、自動化の構築、依存関係の解像度にMavenとGradleを使用して、アプローチと最適化戦略を比較して説明します。

適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?Mar 17, 2025 pm 05:45 PM

この記事では、MavenやGradleなどのツールを使用して、適切なバージョン化と依存関係管理を使用して、カスタムJavaライブラリ(JARファイル)の作成と使用について説明します。

カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?Mar 17, 2025 pm 05:44 PM

この記事では、カフェインとグアバキャッシュを使用してJavaでマルチレベルキャッシュを実装してアプリケーションのパフォーマンスを向上させています。セットアップ、統合、パフォーマンスの利点をカバーし、構成と立ち退きポリシー管理Best Pra

キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?Mar 17, 2025 pm 05:43 PM

この記事では、キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPAを使用することについて説明します。潜在的な落とし穴を強調しながら、パフォーマンスを最適化するためのセットアップ、エンティティマッピング、およびベストプラクティスをカバーしています。[159文字]

Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Mar 17, 2025 pm 05:35 PM

Javaのクラスロードには、ブートストラップ、拡張機能、およびアプリケーションクラスローダーを備えた階層システムを使用して、クラスの読み込み、リンク、および初期化が含まれます。親の委任モデルは、コアクラスが最初にロードされ、カスタムクラスのLOAに影響を与えることを保証します

分散コンピューティングにJavaのRMI(リモートメソッドの呼び出し)を使用するにはどうすればよいですか?分散コンピューティングにJavaのRMI(リモートメソッドの呼び出し)を使用するにはどうすればよいですか?Mar 11, 2025 pm 05:53 PM

この記事では、分散アプリケーションを構築するためのJavaのリモートメソッドの呼び出し(RMI)について説明します。 インターフェイスの定義、実装、レジストリのセットアップ、およびクライアント側の呼び出しを詳述し、ネットワークの問題やセキュリティなどの課題に対処します。

ネットワーク通信にJavaのソケットAPIを使用するにはどうすればよいですか?ネットワーク通信にJavaのソケットAPIを使用するにはどうすればよいですか?Mar 11, 2025 pm 05:53 PM

この記事では、ネットワーク通信のためのJavaのソケットAPI、クライアントサーバーのセットアップ、データ処理、リソース管理、エラー処理、セキュリティなどの重要な考慮事項をカバーしています。 また、パフォーマンスの最適化手法も調査します

Javaでカスタムネットワークプロトコルを作成するにはどうすればよいですか?Javaでカスタムネットワークプロトコルを作成するにはどうすればよいですか?Mar 11, 2025 pm 05:52 PM

この記事では、カスタムJavaネットワーキングプロトコルの作成を詳述しています。 プロトコルの定義(データ構造、フレーミング、エラー処理、バージョン化)、実装(ソケットを使用)、データシリアル化、およびベストプラクティス(効率、セキュリティ、メンテナ

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

WebStorm Mac版

WebStorm Mac版

便利なJavaScript開発ツール

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

AtomエディタMac版ダウンロード

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター