学ぶ JavaにおけるLinkedListの実装 | Javaの基本データ構造

メニューを表示するにはスワイプしてください

本格的な複雑な課題に挑戦する時です。

ここでは、簡易化したデータ構造、具体的には SinglyLinkedList を実装します。

まずは、値と次のNodeへの参照を保持する Node クラスを実装します。

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Node における SinglyLinkedList クラスの実装は前の章ですでに説明されているため、ここでは詳しく説明しません。

次に、データ構造のすべてのロジックを定義する SinglyLinkedList クラスを作成します。

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Node head フィールドを作成し、最初の要素を格納します。

通常の LinkedList には、最初と最後の要素を格納する head と tail があります。初期化時にはデータ構造が空である必要があるため、このフィールドは constructor で null に設定します。

本データ構造はすべての CRUD 操作をサポートする必要があります。

作成

それでは、リストの末尾に要素を追加するメソッド、つまり作成操作を段階的に実装していきます。

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

上記は、リストの末尾に要素を追加するメソッドの実装です。このメソッドの動作を分解して説明します。

NodeクラスのオブジェクトnewNodeを作成し、dataメソッドのパラメータから渡されたappend()をコンストラクタ経由で初期化します。
次に、リストが空かどうかを確認し、空であればリストの最初の要素（head）をnewNodeに再代入します。
その後、メソッドを終了するためにreturn文を追加します。
リストが空でない場合、このメソッドでは新たにcurrentというオブジェクトを作成し、これはこの文脈でのNode headを表します。
whileループを使って、current.nextがnullになるまで、つまりリストの次の要素が空であることを確認するまでリスト全体を反復処理します。
最後の非null要素を見つけたら、そのリンクをnewNodeに設定し、これによって要素がリストに追加されます。

つまり、appendメソッドの目的は最後の要素のリンクを新しい要素に設定することです。このようにして、新しい要素をリストに追加します。

読み取り

次に進みましょう。ここでは読み取り操作を実装します。

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

読み取り操作は非常にシンプルです。リストの各要素を順に走査し、画面に出力します。ここでは、current というプレースホルダーを使用し、Node head で初期化します。
次に、whileループの条件を current != null に設定し、data フィールドを画面に出力します。
リストを走査するために、参照を再代入して current を使用し、current = current.next; のようにします。
Node current が空になるまでこれを繰り返します。その後、ループを抜けて次の行に進みます。

ちなみに、この while ループを do-while ループに置き換える方法について考えてみてください。本当に可能でしょうか？

更新

次に、より興味深い実装となる update メソッドについて説明。

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

まず、index 文を使ってこの if がリスト内に存在するかを確認。不正な場合は「Invalid index」とメッセージを表示し、メソッドを終了。これはエラー回避のための処理;
インデックスがリストの範囲内であれば、よく知られたアルゴリズムを実行。最初に、Node クラスのオブジェクト current を作成し、head で初期化。
while ループの代わりに for ループを使用。ここでは必要な反復回数が明確なため、for ループがより適切。反復回数は index パラメータの値と等しい。
ループの構造は次の通り：
for (int i = 0; i < index; i++)。このループ内で、おなじみの操作 current = current.next を使い、目的の要素を探索;
目的の要素が見つかったら、その data 属性に新しい値を代入し、
current.data = newData の操作を実行。newData はメソッドのパラメータから取得。

すべて明確でしたか？

フィードバックありがとうございます！

セクション 1. 章 6

AIに質問する

何でも質問するか、提案された質問の1つを試してチャットを始めてください

セクション 1. 章 6