Java 二重リンクリスト

Java 二重リンク リストは、データの保存以外の各ノードが 2 つのリンクを持つリンク リストの一種です。最初のリンクはリストの前のノードを指し、もう 1 つのリンクはリストの次のノードを指します。 DLL とも略される Double Linked List は、Single Linked List によく似ています。両方のリンク リストには、次のノードへのポインタと、ノードに格納される実際の値を表すデータ フィールドが含まれています。主な違いは、DLL にはリスト内の前のノードへのポインターが含まれていることです。つまり、DLL 内のノードは前のノードと次のノードの両方を認識します。この記事では、Java の二重リンクリストを見て、いくつかの例を調べ、その実装について学びます。

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

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

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

構文

Java の二重リンク リストには特定の構文はありませんが、「Java で二重リンク リストを宣言する方法」を参照してください。 Double Linked List の宣言を検討する前に、Double Linked List の実装の背後にある概念を見てみましょう。

二重リンクリスト内のノード:

Prev Node

Data

Next Node

前のノード データ 次のノード テーブル>

ここで、Prev Node と Next Node は、それぞれノードの前と次の要素へのポインターです。 「データ」は、データが保存される実際の要素です。

以下は、理解する必要がある重要な用語の一部です。

• Prev: リンク リストの各リンクには、Prev.
という前のノードへのリンクがあります。
• Next: リンク リストの各リンクには、Next
という次のノードへのリンクがあります。
• リンク: リンク リストの各リンクは、要素と呼ばれるデータを保存できます。
• リンク済み リスト: 最初のリンクと最後のリンクへの接続リンクが含まれます。

アルゴリズム

• リンクされたリスト内のノードを表す Node クラスを定義します。 3 つのプロパティ (前のノード、データ、次のノード) が必要です
• 別のクラスを定義して、2 つのノード (先頭と末尾) を持つ二重リンクリストを作成します。最初は、これらの値は null になります。
• リンクされたリストにノードを追加する関数を作成します。
• 最初にヘッドが null かどうかを確認し、次にノードをヘッドとして挿入します。
• ヘッドとテールの両方が新しいノードを指すようになります。
• 末尾が null でない場合、新しいノードのポインタが末尾を指すように、新しいノードがリストの最後に挿入されます。
• したがって、新しいノードは新しい末尾になります。

Java での二重リンクリストのノードの宣言:

class Node {
public int data;
public Node prev;
public Node next;
public void displayData() {
//content of the function}
}

ご覧のとおり、二重リンクリストの場合は追加の宣言または参照 (Node prev) があります。

二重リンクリストの基本操作

以下は二重リンクリストで利用できる基本的な操作です。

• 挿入: リンクされたリストの先頭に要素を追加します
• 削除: リンクされたリストの先頭にある要素を削除します
• 後に挿入: リンクされたリストの項目の後に要素を追加します
• Insert Last: リンクされたリストの末尾に要素を追加します
• 最後を削除: リンクされたリストの末尾の要素を削除します
• 削除: キーを使用してリンク リストから要素を削除します。
• 順方向に表示: 完全なリストを順方向に表示します
• 逆方向に表示: 完全なリストを逆方向に表示します

Java 二重リンクリストの例

以下は Java Double Linked List のさまざまな例です:

例 #1: ノードの宣言と表示へのノードの追加

コード:

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
Node headNode, tailNode = null;
public void addDLLNode(int data) {
Node newDLLNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newDLLNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newDLLNode;
newDLLNode.prevNode = tailNode;
tailNode = newDLLNode;
tailNode.nextNode = null;
}
}
public void displayNode() {
Node currentNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
System.out.println("Nodes in Doubly Linked List: ");
while(currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.nextNode;
}
}
public static void main(String[] args) {
DLL dLinkedList = new DLL();
dLinkedList.addDLLNode(9);
dLinkedList.addDLLNode(7);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(1);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(7);
dLinkedList.displayNode();
}
}

出力:

ここでは、二重リンクリストを宣言し、DLL の値を表示する Node クラスを作成しています。

例 #2: リンクされたリストの先頭を削除して表示します

コード:

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
public void displayNode() {
Node tempNode = headNode;
while (tempNode != null) {
System.out.print(tempNode.data + "–>");
tempNode = tempNode.nextNode;
}
System.out.println("END");
}
Node headNode, tailNode = null;
public void addNode(int data) {
Node newNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newNode;
newNode.prevNode = tailNode;
tailNode = newNode;
tailNode.nextNode = null;
}
}
public void deleteInitialNode() {
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
else {
if(headNode != tailNode) {
headNode = headNode.nextNode;
}
else {
headNode = tailNode = null;
}
}
}
void printNode() {
Node currNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
while(currNode != null)
{
System.out.print(currNode.data + " ");
currNode = currNode.nextNode;
}
System.out.println();
}
public static void main(String[] args) {
DLL doublyLL = new DLL();
doublyLL.addNode(3);
doublyLL.addNode(5);
doublyLL.addNode(7);
doublyLL.addNode(9);
doublyLL.addNode(11);
System.out.println("Doubly linked list: ");
doublyLL.printNode();
doublyLL.addNode(15);
doublyLL.addNode(17);
doublyLL.addNode(19);
doublyLL.deleteInitialNode();
doublyLL.addNode(21);
System.out.println("Doubly Linked List after deleting at the beginning: ");
doublyLL.printNode();
}
}

出力:

ここでは、リンクされたリストの先頭でノードが削除されます。つまり、ノード 3 が削除/削除されます。

DLL は、順方向と逆方向にトラバースできます。削除するノード ポインターが指定されている場合、DLL での削除操作はより効率的になります。 DLL 内のすべてのノードには、前のポインター用に追加のスペースが必要です。すべての操作には追加のポインターを維持する必要があります。

これで、「Java 二重リンクリスト」のトピックを終了します。 Java Double Linked Listとは何なのか、そしてそれがJavaプログラミングでどのように実装されるのかをいくつかの例とともに見てきました。また、二重リンク リストのアルゴリズムについても説明し、DLL に適用できるいくつかの操作をリストしました。最初の操作で挿入と削除を実装しました。同様に、作業できる他の操作も利用できます。

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