Javaでのリンクリストの使用の概要

データ構造は、さまざまな事前定義されたメソッドを使用してデータを格納、取得、および削除し、効率的なプログラムを作成します。リンクリストは一般的なデータ構造であり、接続されている(またはリンクされている)ノードのリストで構成されています。

しかし、Javaでリンクリストを作成するにはどうすればよいでしょうか。見てみましょう。

リンクリストはどのように機能しますか?

すべてのリンクリストは、「ヘッド」と呼ばれることが多い特別なノードで始まります。このノードは、常にリストの先頭を指す責任があります。リンクリスト内の各ノードは、後続ノードを物理的に追跡する必要がないため、ヘッドは重要です(つまり、先行ノードと後続ノードは物理的に隣接している必要はありません)。

すべてのデータ構造と同様に、リンクリストは、開発者が使用できる一連の事前定義された関数を通じて、作成、取得、挿入、および破棄を容易にします。

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

リンクリストを作成および操作するように設計されたJavaプログラムには、3つの特徴的なセクションがあります。ノードクラス、リンクリストクラス、およびドライバ。これらの3つのセクションを1つのファイルにまとめることができますが、コンピュータサイエンスには、すべての開発者が知っておくべき「関心の分離」と呼ばれる設計原則があります。

関心の分離の原則は、特定の関心に対処するコードの各セクションを分離する必要があることを示しています。この原則は、よりクリーンな(より読みやすい)コードを作成するのに役立ち、データ構造の作成に理想的です。

Javaでリンクリストを作成する最初のステップは、ノードクラスを作成することです。ノードクラスには2つの属性が必要です。属性の1つはノードのデータ部分を表し、もう1つの属性はリンクされた部分を表します。ノードクラスには、コンストラクター、ゲッター、およびセッターも必要です。

関連: Javaでクラスを作成する方法を学ぶ

ゲッターとセッターは、他のクラス(リンクリストクラスなど)がリンクリスト内のさまざまなノードにアクセスできるようにします。

ノードクラスの例

以下は、私たちが何を意味するのかを理解するためのノードクラスの例です。

 
public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return NextNode;
}
public void setNextNode(Node nextNode) {
NextNode = nextNode;
}
}

この例では、data属性は整数値を格納します。ノードクラスができたので、次はリンクリストに移動します。

リンクリストの例

以下は、Javaのリンクリストの例です。

 public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}

上記のコードはリンクリストクラスを作成しますが、さまざまな操作がなければ、クラスは空のシェルと同等であると見なすことができます。リンクリストのデータ構造には、データを取り込むために使用できるいくつかの操作があります。

  • 前面に挿入します。
  • 真ん中に挿入します。
  • 後ろに挿入します。

関連: JavaScriptES6クラスを使用してデータ構造を構築する方法

挿入方法のリンクリストコレクションは、開発者がスタックなどの別のデータ構造(上からの挿入と削除のみを許可する)よりもこのデータ構造を使用することを選択する理由の1つです。

フロントメソッドでの挿入の使用

フロントメソッドでの挿入は、その名前が示すように、リンクリストの先頭に新しいデータ(または新しいノード)を挿入します。

フロントメソッドの例に挿入

以下は、リストの先頭に新しいデータを挿入する方法の例です。

 //insert node at front method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);

//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = Temp;
}
}
}

上記の例のinsertAtFrontメソッドを使用すると、ユーザーは特定のリンクリストに新しいノードを追加できます。

フロントの例でインサートを適用する

以下は、前面にインサートを適用する方法の例です。

 public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
List.insertAtFront(10);
List.insertAtFront(8);
List.insertAtFront(6);
List.insertAtFront(4);
List.insertAtFront(2);
}
}

Driverクラス(Javaの実行可能クラスに割り当てられることが多い名前)は、LinkedListクラスを利用して、5つの偶数のリンクリストを作成します。上記のコードを見ると、リンクリストの先頭に数字「2」があることが簡単にわかります。しかし、どうすればこれを確認できますか?

すべてのノードを表示する方法の使用

全ノード表示方式は、必須のリンクリスト方式です。これがないと、開発者はリンクリスト内のノードを表示できません。リンクリストを(先頭から)移動して、リストを形成する各ノードに格納されているデータを印刷します。

すべてのノードを表示するメソッドの例

以下は、Javaで「すべてのメモを表示」メソッドを使用する例です。

 //display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println("The list is empty.");
return;
}
System.out.println("The List:");

while(Temp != null) {
//print the data in each node to the console(starting from the head)
System.out.print(Temp.getData() + " ");
Temp = Temp.getNextNode();
}
}

displayAllNodesメソッドがLinkedListクラスに追加されたので、ドライバークラスに1行のコードを追加することで、リンクリストを表示できます。

すべてのノードを表示する方法の例を使用する

以下に、すべてのノードを表示する方法を使用する方法を示します。

 //print the nodes in a linked list
List.displayAllNodes();

上記のコード行を実行すると、コンソールに次の出力が生成されます。

リスト:

 2 4 6 8 10

ノード検索メソッドの使用

ユーザーがリンクリストで特定のノードを見つけたい場合があります。

たとえば、何百万もの顧客を抱える銀行が、特定の顧客の詳細を確認するだけでよい場合に、データベース内のすべての顧客を印刷することは現実的ではありません。

したがって、 displayAllNodesメソッドを使用する代わりに、より効率的な方法は、必要なデータを含む単一のノードを見つけることです。これが、リンクリストのデータ構造で単一ノードメソッドの検索が重要である理由です。

ノードメソッドの例を見つける

以下は、ノード検索メソッドの使用例です。

 //search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println("The node is in the list");
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println("The node is not in the list");
return false;
}

displayAllNodesメソッドを使用して、 LinkedListに2から10までの5つの偶数が含まれていることを確認しました。上記のfindNodeの例では、ドライバークラスのメソッドを呼び出して番号を指定するだけで、これらの偶数の1つが数字4であるかどうかを確認できます。パラメータ。

ノード検索メソッドの例の使用

以下は、実際にノード検索メソッドを使用する方法の例です。

 //check if a node is in the linked list
List.findNode(4);

上記のコードは、コンソールに次の出力を生成します。

 The node is in the list

ノードの削除メソッドの使用

上記と同じ銀行の例を使用すると、銀行のデータベースの顧客は自分の口座を閉鎖したいと思うかもしれません。ここで、ノードの削除メソッドが役立ちます。これは最も複雑なリンクリスト方式です。

Delete a Nodeメソッドは、指定されたノードを検索し、そのノードを削除して、前のノードを、削除されたノードの次のノードにリンクします。

ノードメソッドの例を削除する

以下は、ノードの削除メソッドの例です。

 public void findAndDelete(int key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
Temp = Temp.getNextNode();
}
}

ノードの削除メソッドの例の使用

以下は、実際にノードを削除する方法を使用する例です。

 //delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

既存のDriverクラスで上記の2行のコードを使用すると、コンソールに次の出力が生成されます。

 The List:
2 6 8 10

これで、Javaでリンクリストを作成できます

このチュートリアル記事の最後に到達した場合は、次のことを学習しているはずです。

  • ノードクラスを作成する方法。
  • リンクリストクラスを作成する方法。
  • リンクリストクラスに事前定義されたメソッドを設定する方法。
  • ドライバークラスを作成し、さまざまなリンクリストメソッドを使用して目的の結果を達成する方法。

リンクリストは、データの保存、取得、削除に使用できる多くのデータ構造の1つにすぎません。始めるために必要なものがすべて揃っているので、Javaでこれらの例を自分で試してみませんか?