JavaでLinkedList（連結リスト）を実装するプログラムの書き方

この記事では、Javaで連結リスト（Linked List）を実装する方法を詳しく解説します。java.util.LinkedListクラスは、双方向連結リストとして期待される操作を提供するクラスです。インデックスを指定して要素にアクセスする場合、指定されたインデックスに近い方から、リストの先頭または末尾のいずれかを起点として走査が行われます。

以下に、その実装例を示します。

実行結果の例

入力：

プログラムを実行する

期待される出力：

The elements of the linked list are:
100 150 200 250

アルゴリズム

ステップ1 - 開始
ステップ2 - 必要なメンバーを持つクラスを作成する。
ステップ3 - リストに要素を追加するための「insert」メソッドを定義する。
ステップ4 - mainメソッド内で、クラスの新しいインスタンスを生成する。
ステップ5 - リストを作成し、「insert」メソッドを使って要素を追加する。
ステップ6 - リストを反復処理し、現在のノードに格納されている値を表示する。
ステップ7 - 次のノードへ移動し、同じ操作を繰り返す。
ステップ8 - リストの末尾に到達するまでこの処理を続ける。
ステップ9 - 結果を表示する。
ステップ10 - 終了。

例1：mainメソッドにすべての処理をまとめる方法

ここでは、すべての操作を「main」関数内にまとめて記述します。ノードを表す内部クラスNodeを定義し、insertメソッドでリストの末尾に要素を追加していきます。

public class Demo {
   Node head;
   static class Node {
      int data;
      Node next_element;
      Node(int element){
      data = element;
      next_element = null;
   }
}
public static Demo insert(Demo input_list, int data){
   Node new_node = new Node(data);
   new_node.next_element = null;
   if (input_list.head == null) {
      input_list.head = new_node;
   }
   else {
      Node last = input_list.head;
      while (last.next_element != null) {
         last = last.next_element;
      }
      last.next_element = new_node;
   }
   return input_list;
   }
   public static void main(String[] args){
      Demo input_list = new Demo();
      System.out.print("A linked list is declared: \n");
      input_list = insert(input_list, 100);
      input_list = insert(input_list, 150);
      input_list = insert(input_list, 200);
      input_list = insert(input_list, 250);
      Node current_node = input_list.head;
      System.out.print("The elements of the linked list are: \n");
         while (current_node != null) {
         System.out.print(current_node.data + " ");
         current_node = current_node.next_element;
      }
   }
}

出力

A linked list is declared:
The elements of the linked list are:
100 150 200 250

例2：オブジェクト指向で関数に分割する方法

次に、各操作を独立したメソッドとしてカプセル化し、オブジェクト指向プログラミングのスタイルで実装した例を紹介します。表示処理をprint_listメソッドとして切り出すことで、コードの再利用性と可読性が向上します。

public class Demo {
   Node head;
   static class Node {
      int data;
      Node next_element;
      Node(int element){
         data = element;
         next_element = null;
      }
   }
   public static Demo insert(Demo input_list, int data){
      Node new_node = new Node(data);
      new_node.next_element = null;
      if (input_list.head == null) {
         input_list.head = new_node;
      }
      else {
         Node last = input_list.head;
         while (last.next_element != null) {
            last = last.next_element;
         }
         last.next_element = new_node;
      }
      return input_list;
   }
   public static void print_list(Demo input_list){
      Node current_node = input_list.head;
      System.out.print("The elements of the linked list are: \n");
      while (current_node != null) {
         System.out.print(current_node.data + " ");
         current_node = current_node.next_element;
      }
   }
   public static void main(String[] args){
      Demo input_list = new Demo();
      System.out.print("A linked list is declared: \n");
      input_list = insert(input_list, 100);
      input_list = insert(input_list, 150);
      input_list = insert(input_list, 200);
      input_list = insert(input_list, 250);
      print_list(input_list);
   }
}

出力

A linked list is declared:
The elements of the linked list are:
100 150 200 250

まとめ

このように、Javaでは内部クラスとしてNodeを定義し、headポインタとnext参照を組み合わせることで、独自の連結リストを簡単に実装できます。例1はシンプルに全体をmainメソッドにまとめた形、例2は処理をメソッドごとに分離したオブジェクト指向らしい設計となっており、目的に応じて使い分けることができます。データ構造の基礎を理解するうえで、ぜひ実際にコードを動かして挙動を確認してみてください。