単方向リストと双方向リスト
山崎講師単方向リスト
単方向リスト【Singly Linked List】は、複数の要素を順序付けて格納するデータ構造の一つです。単方向リストでは、各要素がリスト内で一方向にのみつながる（線形）構造を持ちます。
単方向リストの要素は、通常は「ノード」と呼ばれます。各ノードは、データを保持するためのフィールドと、次のノードへの参照を格納するためのフィールドを持ちます。リストの先頭ノードは「ヘッド」、末尾ノードは「テール」と呼ばれます。
単方向リストは、データの追加や削除が高速に行えるという利点があります。一方で、要素の検索にはO(n)の時間が必要となるという欠点もあります。また、各要素が次の要素の参照しか持っていないため、リスト内の要素を逆方向にたどることはできません。
なお、JavaのArrayListクラスは、今回紹介した単方向リストではなく、配列の応用です。つまり、可変長配列を実装したリスト（動的配列）です。初期化時には、内部の配列は指定された初期容量（デフォルトは10）で作成されます。要素の追加や削除が行われるときに、内部配列のサイズが不足する場合は自動的にリサイズされます。ArrayListはランダムアクセス（インデックスを指定しての要素へのアクセス）において高速ですが、検索に関しては要素を順番に調べる線形検索となるため、効率はあまり高くありません。
以下の練習問題でリストの理解度を確かめてください。
練習問題
基本情報技術者試験 平成29年春期 午前問4
練習問題
基本情報技術者試験 平成30年春期 午前問6
練習問題
基本情報技術者試験 平成27年秋期 午前問5
＜サンプルプログラム＞
public class SinglyLinkedList {
Node head;
//内部クラス
private class Node {
int data;
Node next;//次のノード
// ノードのコンストラクタ
public Node(int data) {
this.data = data;
this.next = null;
}
}
// 単方向リストのコンストラクタ
public SinglyLinkedList() {
this.head = null;
}
// 新しいノードをリストの末尾に挿入する
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
// リストが空の場合、新しいノードをヘッドとして設定する
head = newNode;
} else {
// リストの末尾に到達するまで移動し、新しいノードを追加する
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// リストの要素を表示する
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
// データをリストに挿入する
list.insert(5); // データ5を挿入
list.insert(8); // データ8を挿入
list.insert(3); // データ3を挿入
list.insert(2); // データ2を挿入
// リストの要素を表示する
list.display(); // 結果: 5 8 3 2
}
}＜出力結果＞
| 5 8 3 2 |
双方向リスト
双方向リスト【Doubly Linked List】は、リスト内の各ノードが前後のノードへの参照を持つデータ構造です。各ノードがデータと前後のポインタ（参照）を持ち、リストの前方から後方、後方から前方の両方向に操作が可能です。
通常の単方向リスト【Singly Linked List】では、各ノードが次のノードへの参照を持ちますが、前のノードへの参照は持ちません。一方、双方向リストでは、各ノードが次のノードへの参照だけでなく、前のノードへの参照も持つため、リストの前後の移動や操作が容易になります。
双方向リストの主な利点は、以下の点です：
順方向と逆方向のトラバース（走査）が容易：各ノードが前後のポインタを持っているため、リストを順方向または逆方向に移動しながら要素にアクセスすることができます。
要素の挿入と削除が効率的：双方向リストでは、挿入や削除時に前後のポインタを調整するだけで済みます。一方、単方向リストでは、挿入や削除を行う場合には前方のノードを探索する必要があります。
リストの逆順アクセスが可能：双方向リストでは、最後のノードから最初のノードに向かって逆順にアクセスすることも容易です。
双方向リストの欠点は、単方向リストと比べて各ノードが前方への参照を保持するためにメモリ使用量が多くなることです。また、リストの操作に伴う実装の複雑さも挙げられます。
双方向リストは、特に要素の追加や削除が頻繁に行われる場合や、順方向および逆方向のアクセスが必要な場合に有用です。
＜サンプルプログラム＞
public class DoublyLinkedList {
private class Node {
int data;
Node prev; //次のノードへの参照
Node next; //前のノードへの参照
// ノードのコンストラクタ
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node head; //先頭ノードへの参照
private Node tail;//末尾ノードへの参照
// 双方向リストのコンストラクタ
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
// 新しいノードをリストの末尾に挿入する
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
// リストが空の場合、新しいノードをヘッドとテールに設定する
head = newNode;
tail = newNode;
} else {
// 新しいノードをリストの末尾に追加する
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// リストの要素を順方向に表示する
public void displayForward() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// リストの要素を逆方向に表示する
public void displayBackward() {
Node current = tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
// データをリストに挿入する
list.insert(5); // データ5を挿入
list.insert(8); // データ8を挿入
list.insert(3); // データ3を挿入
list.insert(2); // データ2を挿入
// 双方向リストを順方向で表示する
System.out.print("Forward: ");
list.displayForward(); // 結果: 5 8 3 2
// 双方向リストを逆方向で表示する
System.out.print("Backward: ");
list.displayBackward(); // 結果: 2 3 8 5
}
}＜出力結果＞
| Forward: 5 8 3 2 Backward: 2 3 8 5 |
