Javaで実装したLinkedListのサンプルプログラムをご紹介

投稿日：2021年3月12日更新日：2021年1月23日

＜目次＞

(１) Javaで実装したLinkedListのサンプルプログラムをご紹介
　 (１-１) LinkedListの概要
　 (１-２) LinkedListの特徴
　 (１-３) LinkedListのサンプルプログラム概要
　 (１-４) LinkedListのサンプルプログラム

(１) Javaで実装したLinkedListのサンプルプログラムをご紹介

(１-１) LinkedListの概要

LinkedListは各要素に値のみならず「次の要素のアドレス」を持っています。

（図１１１）

そして最後の要素には「次の要素」は無いので、次の要素のアドレス＝nullになります。

＞目次にもどる

(１-２) LinkedListの特徴

①メモリ消費が多い
通常のArrayListが持つ情報に加えて、「次の要素のアドレス」を保持している分、余計にメモリを消費します。

②探索は遅い
加えて、N番目のデータを探す際はリンク（次の要素のアドレス）をN個辿っていくので、ArrayListと比較して遅いです。ただし、この欠点を克服するために「前の要素」へのリンクを持っている場合もあります。

③要素の追加削除は速い
一方で要素の追加削除はリンクを付け替えるのみなので、ArrayListよりも高速に行えます。

⇒（参考）LinkedListとArrayListの比較

＞目次にもどる

(１-３) LinkedListのサンプルプログラム概要

①Nodeクラスについて

NodeクラスというのはLinkedListの各要素を表すクラスです。各要素ではそれぞれ「次の要素へのリンク」と「要素の値」を持っています。

（図１３１）Nodeクラスのイメージ

（例：Nodeクラス）

この例ではリストに格納できる値はString型の「value」のみですが、ここは自由にカスタマイズ可能です。

    class Node {
        //次の要素のアドレス（リンク）
        Node next = null;
        //現在の要素の値
        String data;
        //コンストラクタ
        public Node(String d) {data=d;}
    }

＞目次にもどる

②先頭要素へのポインタ作成

LinkedListではまず最初に、値を持たない「先頭要素へのポインタ」を用意します。具体的にはNodeクラスのインスタンスを引数nullで作成します。

（例）

    //先頭要素へのポインタ
    Node head = new Node(null);

これはプログラム処理的には、headに次の要素への「アドレスを代入」しているため、イメージとしては次のようにheadから次の先頭要素へリンクしており、その値がnullという状態です。

（図１３２）

③末尾への要素追加メソッド

次にLinkedListの末尾に要素を追加する「addLast」メソッドを定義します。このメソッドはまずhead（先頭要素へのポインタ）を起点に、while文でnext（次の要素へのアドレス）を辿っていき、末尾に辿り着いた所で、新規の要素を追加するメソッドです。

（例）

    public void addLast(String d) {
        //先頭から辿るために、先頭要素へのポインタheadを取得
        Node n = head;
        //末尾の要素を探索
        while(n.next != null) {
            n = n.next;
        }
        //末尾に新規要素を追加
        n.next = new Node(d);
    }

このメソッドの実装を簡易にする都合上、先頭要素の値はnullで、実際に値が入っているのは2個目の要素以降になっています。その分、先頭要素と以降の要素を区別せずにループ処理を一気に行えます。

（図１３３）

＞目次にもどる

④コンソール出力用メソッド

次にリストの内容をコンソールに出力（print）するためのメソッド「toString()」を作ります。toStringメソッドは、クラスのインスタンス（例ではListControllerクラスのインスタンス）を引数にprintする事で、メソッドが実行されて値がprintされます。

（例）

    public String toString() {
        StringBuilder sb = new StringBuilder();
        //先頭から辿るために、先頭要素へのポインタheadを取得
        Node n = head;
        //各要素を順番に辿り、値を追加
        while(n.next != null) {
            n = n.next;
            sb.append(n.data+"\n");
        }
        return sb.toString();
    }

＞目次にもどる

(１-４) LinkedListのサンプルプログラム

前述の①～④に加えて、実際にLinkedListに要素を追加して表示するmain文も併せた、プログラムをご紹介します。

public class IT0279_LinkedListTest {
    public static void main(String args[]) {
        ListController lc = new ListController();
        lc.addLast("Monday");
        lc.addLast("Tueseday");
        lc.addLast("Wednesday");
        lc.addLast("Thursday");
        lc.addLast("Friday");
        lc.addLast("Saturday");
        lc.addLast("Sunday");
        System.out.println(lc);
    }
}

class ListController{

    class Node {
        //次の要素のアドレス（リンク）
        Node next = null;
        //現在の要素の値
        String data;
        //コンストラクタ
        public Node(String d) {data=d;}
    }

    //先頭要素へのポインタ
    Node head = new Node(null);

    public void addLast(String d) {
        //先頭から辿るために、先頭要素へのポインタheadを取得
        Node n = head;
        //末尾の要素を探索
        while(n.next != null) {
            n = n.next;
        }
        //末尾に新規要素を追加
        n.next = new Node(d);
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        //先頭から辿るために、先頭要素へのポインタheadを取得
        Node n = head;
        //各要素を順番に辿り、値を追加
        while(n.next != null) {
            n = n.next;
            sb.append(n.data+"\n");
        }
        return sb.toString();
    }
}

（図１４１）実行結果

＞目次にもどる