＜目次＞
(１) Javaで実装したLinkedListのサンプルプログラムをご紹介
(１-１) LinkedListの概要
(１-２) LinkedListの特徴
(１-３) LinkedListのサンプルプログラム概要
(１-４) LinkedListのサンプルプログラム
(１) Javaで実装したLinkedListのサンプルプログラムをご紹介
(１-１) LinkedListの概要
LinkedListは各要素に値のみならず「次の要素のアドレス」を持っています。
（図１１１）
そして最後の要素には「次の要素」は無いので、次の要素のアドレス＝nullになります。
(１-２) LinkedListの特徴
①メモリ消費が多い
通常のArrayListが持つ情報に加えて、「次の要素のアドレス」を保持している分、余計にメモリを消費します。
②探索は遅い
加えて、N番目のデータを探す際はリンク（次の要素のアドレス）をN個辿っていくので、ArrayListと比較して遅いです。ただし、この欠点を克服するために「前の要素」へのリンクを持っている場合もあります。
③要素の追加削除は速い
一方で要素の追加削除はリンクを付け替えるのみなので、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();
}
}
（図１４１）実行結果
