検索

スキップ リスト 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结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 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ヘンタイを無料で生成します。

ホットツール

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

EditPlus 中国語クラック版

EditPlus 中国語クラック版

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

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール