Rainbow Engine

IT技術を分かりやすく簡潔にまとめることによる学習の効率化、また日常の気付きを記録に残すことを目指します。

Java

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

投稿日:2021年3月12日 更新日:

<目次>

(1) Javaで実装したLinkedListのサンプルプログラムをご紹介
 (1-1) LinkedListの概要
 (1-2) LinkedListの特徴
 (1-3) LinkedListのサンプルプログラム概要
 (1-4) LinkedListのサンプルプログラム

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

(1-1) LinkedListの概要

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

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

(1-2) LinkedListの特徴

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

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

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

(参考)LinkedListとArrayListの比較

目次にもどる

(1-3) LinkedListのサンプルプログラム概要

①Nodeクラスについて

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

(図131)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という状態です。
 
(図132)

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

次に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個目の要素以降になっています。その分、先頭要素と以降の要素を区別せずにループ処理を一気に行えます。

(図133)

目次にもどる

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

次にリストの内容をコンソールに出力(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();
    }

目次にもどる

(1-4) 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();
    }
}

(図141)実行結果

目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

JavaのArrrayListとLinkedListの違いについて

<目次> (1) JavaのArrrayListとLinkedListの違いについて  (1-1) 比較表(ArrayList vs LinkedList)  (1-2) まとめ  (1-3) 参考 …

サーバサイドJava(JSP&サーブレット)のFORM認証を用いたログイン画面の開発

(0)目次&概説 (1) サーバー側JavaのFORM認証  (1-1) 認証の種類  (1-2) FORM認証の特徴  (1-3) FORM認証の実装概要 (2) FORM認証の実装手順  (2-1 …

InputStreamやInputStreamReaderやBufferedReaderの機能や役割の違い+速度測定で比較をした結果共有

(0)目次&概説 (1) 記事の目的  (1-1) 目的  (1-2) 前提条件 (2) InputStreamやBufferedReaderとは?  (2-1) 概要  (2-2) InputStr …

TwitterのAPIでハッシュタグからツイートを探すJavaプログラムのご紹介

<目次> (1) TwitterのAPIでハッシュタグからツイートを探すJavaプログラムのご紹介  (1-1) プログラムの概要  (1-2) サンプルプログラム  (1-3) 操作イメージ (1) …

JFreeChartで描画したグラフをJSP/Servlet画面に表示する方法

(0)目次&概説 (1) 記事の目的  (1-1) 目的 (2) 表示方法の概要  (2-1) 表示の仕組み  (2-2) 実装の手順 (3) サンプルプログラム  (3-1) JSPのサンプルプログ …

  • English (United States)
  • 日本語
Top