Javaのデータ構造とアルゴリズム、パート4:単一リンクリスト

このチュートリアルシリーズのパート3で紹介した配列と同様に、リンクリストは、より複雑なデータ構造の基礎となる基本的なデータ構造カテゴリです。ただし、要素のシーケンスとは異なり、リンクリストはノードのシーケンスであり、各ノードはシーケンス内の前のノードと次のノードにリンクされます。ノードは自己参照クラスから作成されたオブジェクトであり、自己参照クラスには、参照タイプがクラス名であるフィールドが少なくとも1つあることを思い出してください。リンクリスト内のノードは、ノード参照を介してリンクされます。次に例を示します。

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

この例でEmployeeは、nextフィールドのタイプがであるため、は自己参照クラスEmployeeです。このフィールドは、そのクラスの別のオブジェクト(この場合は別のオブジェクト)への参照を格納できるため、リンクフィールドの例ですEmployee

このチュートリアルでは、Javaプログラミングにおける単一リンクリストの詳細を紹介します。単一リンクリストの作成、単一リンクリストへのノードの挿入、単一リンクリストからのノードの削除、単一リンクリストの別の単一リンクリストへの連結、および単一リンクリストの反転の操作について学習します。また、単一リンクリストの並べ替えに最も一般的に使用されるアルゴリズムについても説明し、挿入並べ替えアルゴリズムを示す例で締めくくります。

ダウンロードコードを入手するこの記事の3つのサンプルアプリケーションをダウンロードしてください。JavaWorld用にJeffFriesenによって作成されました。

単一リンクリストとは何ですか?

単独でリンクされたリストは、各ノードが単一のリンクフィールドを持つノードのリンクされたリストです。このデータ構造では、参照変数には最初の(または最上位の)ノードへの参照が含まれています。各ノード(最後のノードまたは一番下のノードを除く)は次のノードにリンクします。最後のノードのリンクフィールドには、リストの終わりを示すnull参照が含まれています。参照変数には一般的に名前が付けられていtopますが、任意の名前を選択できます。

図1は、3つのノードを持つ単一リンクリストを示しています。

以下は、単一リンクリストの擬似コードです。

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodeは、nameデータフィールドとnextリンクフィールドを持つ自己参照クラスです。topは、単一リンクリストのNode最初のNodeオブジェクトへの参照を保持する型の参照変数です。リストがまだ存在しないため、topの初期値はNULLです。

Javaで単一リンクリストを作成する

単一のNodeオブジェクトをアタッチすることにより、単一リンクリストを作成します。次の擬似コードは、Nodeオブジェクトを作成し、その参照をに割り当て、topそのデータフィールドを初期化し、NULLそのリンクフィールドに割り当てます。

 top = NEW Node top.name = "A" top.next = NULL 

図2は、この擬似コードから出現する最初の単一リンクリストを示しています。

この操作の時間計算量はO(1)-定数です。O(1)は「BigOhof1」と発音されることを思い出してください。(時間と空間の複雑さの測定値を使用してデータ構造を評価する方法については、パート1を参照してください。)

単一リンクリストへのノードの挿入

考慮すべき3つのケースがあるため、単一リンクリストへのノードの挿入は、単一リンクリストの作成よりもいくらか複雑です。

  • 最初のノードの前に挿入します。
  • 最後のノードの後の挿入。
  • 2つのノード間の挿入。

最初のノードの前に挿入

最上位ノードの参照を新しいノードのリンクフィールドに割り当て、新しいノードの参照をtop変数に割り当てることにより、新しいノードが最初のノードの前に挿入されます。この操作は、次の擬似コードによって示されます。

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

結果の2つのNodeリストを図3に示します。

この操作の時間計算量はO(1)です。

最後のノードの後の挿入

次の擬似コードが示すように、新しいノードのリンクフィールドにnullを割り当て、単一リンクリストをトラバースして最後のノードを見つけ、新しいノードの参照を最後のノードのリンクフィールドに割り当てることにより、新しいノードが最後のノードの後に​​挿入されます

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

図4は、AのNode後にCを挿入した後のリストを示していますNode

この操作の時間計算量はO(n)-linearです。最後のノードへの参照を維持することにより、その時間計算量をO(1)に改善できます。その場合、最後のノードを検索する必要はありません。

2つのノード間の挿入

2つのノードの間にノードを挿入するのが最も複雑なケースです。リストをトラバースして新しいノードの前にあるノードを見つけ、見つかったノードのリンクフィールドの参照を新しいノードのリンクフィールドに割り当て、新しいノードの参照を見つかったノードのリンクに割り当てることで、2つのノードの間に新しいノードを挿入します。フィールド。次の擬似コードは、これらのタスクを示しています。

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

図5は、sAとCのNode間にDを挿入した後のリストを示していますNode

この操作の時間計算量はO(n)です。

単一リンクリストからのノードの削除

単一リンクリストからノードを削除することも、単一リンクリストを作成するよりもいくらか複雑です。ただし、考慮すべきケースは2つだけです。

  • 最初のノードの削除。
  • 最初のノード以外のノードの削除。

最初のノードの削除

最初のノードを削除するには、最初のノードのリンクフィールドのリンクを、最初のノードを参照する変数に割り当てる必要がありますが、最初のノードがある場合に限ります。

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

図6は、最初のリストNodeが削除されたリストのビューの前後を示しています。ノードがB消え、NodeAが最初になりNodeます。

この操作の時間計算量はO(1)です。

最初のノード以外のノードの削除

最初のノード以外のノードを削除するには、削除するノードの前にあるノードを特定し、削除するノードのリンクフィールド内の参照を前のノードのリンクフィールドに割り当てる必要があります。次の擬似コードを検討してください。

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

図7は、中間体Nodeが削除されたリストのビューの前後を示しています。NodeDが消えます。

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

SLLDemo連結と反転を示すJavaアプリケーションの2番目のバージョンを作成しました。リスト2は、このアプリケーションのソースコードを示しています。