Javaのデータ構造とアルゴリズム、パート5:二重リンクリスト

単一リンクリストには多くの用途がありますが、いくつかの制限もあります。一つには、単一リンクリストはノードトラバーサルを単一方向に制限します。最初にノードリンクを逆にしない限り、単一リンクリストを逆方向にトラバースすることはできません。これには時間がかかります。逆トラバーサルを実行し、ノードトラバーサルを元の方向に復元する必要がある場合は、反転を繰り返す必要があり、これにはさらに時間がかかります。単一リンクリストもノードの削除を制限します。このタイプのリストでは、ノードの先行ノードにアクセスせずに任意のノードを削除することはできません。

幸い、Javaには、Javaプログラムに格納されているデータを検索およびソートするために使用できるいくつかのタイプのリストが用意されています。データ構造とアルゴリズムシリーズのこの最後のチュートリアルでは、二重リンクリストと循環リンクリストを使用した検索と並べ替えを紹介します。ご覧のとおり、これら2つのデータ構造カテゴリは、単一リンクリストに基づいて構築されており、Javaプログラムでより幅広い検索およびソート動作を提供します。

二重リンクリスト

二重リンクリストは、各ノードがリンクフィールドの対を有するノードのリンクされたリストです。一方のリンクフィールドではリストを順方向にトラバースでき、もう一方のノードではリストを逆方向にトラバースできます。順方向の場合、参照変数は最初のノードへの参照を保持します。各ノードは、「次の」リンクフィールドを介して次のノードにリンクします。ただし、最後のノードの「次の」リンクフィールドには、リストの終わり(順方向)を示すnull参照が含まれます。逆方向も同様に機能します。参照変数は、順方向の最後のノードへの参照を保持します。これは、最初のノードとして解釈されます。各ノードは、「前の」リンクフィールドを介して前のノードにリンクします。最初のノードの「前」リンクフィールドには、リストの終わりを示すnullが含まれています。

二重にリンクされたリストを、それぞれが同じノードを相互接続する単一にリンクされたリストのペアと考えてみてください。図1の図は、topForward-referencedおよびtopBackward-referencedの単一リンクリストを示しています。

二重リンクリストでのCRUD操作

ノードの作成、挿入、および削除はすべて、二重リンクリストの一般的な操作です。これらは、単一リンクリストについて学習した操作に似ています。(二重リンクリストは、同じノードを相互接続する単一リンクリストのペアにすぎないことに注意してください。)次の擬似コードは、図1に示す二重リンクリストへのノードの作成と挿入を示しています。擬似コードはノードも示しています。削除:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

アプリケーション例:二重リンクリストのCRUD

サンプルのJavaアプリケーションDLLDemoは、二重リンクリストでノードを作成、挿入、および削除する方法を示しています。アプリケーションのソースコードをリスト1に示します。

リスト1.二重リンクリストでCRUDを示すJavaアプリケーション

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

リスト4を次のようにコンパイルします。

 javac DLLDemo.java 

結果のアプリケーションを次のように実行します。

 java DLLDemo 

次の出力を確認する必要があります。

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

二重リンクリストでのシャッフル

JavaコレクションフレームワークにはCollectionsjava.utilパッケージの一部であるユーティリティメソッドのクラスが含まれています。このクラスには、void shuffle(List list)デフォルトのランダム性のソースを使用して、指定されたリストをランダムに並べ替える」メソッドが含まれています。たとえば、このメソッドを使用して、二重リンクリストとして表現されたカードのデッキをシャッフルすることができます(java.util.LinkedListクラスは例です)。以下の擬似コードでは、シャッフルアルゴリズムが二重リンクリストをシャッフルする方法を確認できます。

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

シャッフルアルゴリズムは、ランダム性のソースを取得し、最後のノードから2番目のノードまでリストを逆方向にトラバースします。ランダムに選択されたノード(実際には単なる名前フィールド)を「現在の位置」に繰り返し交換します。ノードは、最初のノードから現在の位置までのリストの部分からランダムに選択されます。このアルゴリズムは、void shuffle(List list)のソースコードから大まかに抜粋されていることに注意してください。

シャッフルアルゴリズムの擬似コードは、順方向にトラバースする単一リンクリストのみに焦点を当てているため、怠惰です。これは合理的な設計上の決定ですが、時間の複雑さの代償を払っています。時間計算量はO(n 2)です。まず、を呼び出すO(n)ループがありますswap()。次に、内swap()に2つの連続したO(n)ループがあります。パート1の次のルールを思い出してください。

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

パート(a)はシーケンシャルアルゴリズムを扱います。ここでは、2つのO(n)ループがあります。ルールによれば、結果として生じる時間計算量はO(n)になります。パート(b)は、ネストされたアルゴリズムを扱います。この場合、我々はO(有するN O(乗じ)nはO(その結果、)N 2)。

シャッフルのスペースの複雑さはO(1)であり、宣言されたヘルパー変数に起因することに注意してください。

アプリケーション例:二重リンクリストでのシャッフル

Shuffleリスト2のアプリケーションは、シャッフルアルゴリズムのデモンストレーションです。

リスト2.Javaのシャッフルアルゴリズム

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

リスト5を次のようにコンパイルします。

 javac Shuffle.java 

結果のアプリケーションを次のように実行します。

 java Shuffle 

1回の実行で次の出力を確認する必要があります。

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

循環リンクリスト

単一リンクリストの最後のノードのリンクフィールドにヌルリンクが含まれています。これは、前方および後方の単一リンクリストの最後のノードのリンクフィールドを含む二重リンクリストにも当てはまります。代わりに、最後のノードに最初のノードへのリンクが含まれているとします。この状況では、図2に示すように、循環リンクリストが作成されます。

Circular-linked lists, also known as circular buffers or circular queues, have many uses. For example, they're used by operating system interrupt handlers to buffer keystrokes. Multimedia applications use circular-linked lists to buffer data (for example, buffering data being written to a sound card). This technique is also used by the LZ77 family of lossless data compression algorithms.

Linked lists versus arrays

Throughout this series on data structures and algorithms, we've considered the strengths and weaknesses of different data structures. Since we've focused on arrays and linked lists, you might have questions about these types specifically. What advantages and disadvantages do linked lists and arrays offer? When do you use a linked list and when do you use an array? Can data structures from both categories be integrated into a useful hybrid data structure? I'll try to answer these questions below.

Linked lists offer the following advantages over arrays:

  • They don't require extra memory to support expansion. In contrast, arrays require extra memory when expansion is necessary. (Once all elements contain data items, no new data items can be appended to an array.)
  • これらは、同等のアレイベースの操作よりも高速なノードの挿入/削除を提供します。挿入/削除位置を特定した後、リンクのみを更新する必要があります。配列の観点から、データ項目の挿入では、空の要素を作成するために他のすべてのデータ項目を移動する必要があります。同様に、既存のデータ項目を削除するには、他のすべてのデータ項目を移動して空の要素を削除する必要があります。すべてのデータ項目の移動には時間がかかります。

対照的に、配列には、リンクリストに比べて次の利点があります。

  • 要素はリンクフィールドを必要としないため、配列要素はノードよりも少ないメモリを占有します。
  • 配列は、整数ベースのインデックスを介して、データ項目へのより高速なアクセスを提供します。