はじめに: 連結リストは「次の場所をたどる」データ構造
これまで、配列、スタック、キュー、木構造、ハッシュテーブルなどのデータ構造を見てきました。今回扱う連結リストは、データを順番に並べるための基本的なデータ構造です。
配列もデータを順番に並べます。では、連結リストは何が違うのでしょうか。
連結リストでは、1つ1つのデータが「次のデータはどこにあるか」という情報を持ちます。先頭から順番に、その次、その次、というようにたどっていくことで、全体の並びを表します。
基本情報技術者試験では、連結リストはポインタ、挿入、削除、探索といった話題と一緒に出てきます。JavaScriptにはポインタという言葉を直接使う場面は少ないですが、オブジェクト同士の参照を使うと、連結リストの考え方をコードで確認できます。
連結リストは、各データが次のデータへの参照を持ち、先頭から順番にたどるデータ構造です。
配列と連結リストの違い
配列は、添字を使って要素にアクセスできます。
const values = ["A", "B", "C"];
console.log(values[1]);この例では、values[1] で2つ目の要素を取り出せます。配列は、位置が分かっている要素へアクセスしやすいデータ構造です。
一方、連結リストでは、基本的に先頭から順番にたどります。2つ目の要素を見たい場合も、まず先頭を見て、そこから「次」を見ます。3つ目なら、さらに次をたどります。
配列は、メモリ上に要素が並んでいるイメージで説明されることが多いです。連結リストは、要素がバラバラの場所にあっても、それぞれが次の要素を指していれば順番を表せます。
そのため、配列と連結リストでは得意な処理が違います。配列は添字によるアクセスが得意です。連結リストは、つながりを付け替えることで挿入や削除を表しやすい場面があります。
配列は添字で目的の位置へアクセスしやすく、連結リストは次への参照をたどって順番を表します。
ノードとポインタをJavaScriptで表す
連結リストでは、1つ1つの要素をノードと呼びます。ノードは、値と次のノードへの参照を持ちます。
JavaScriptでは、次のようなオブジェクトでノードを表せます。
const nodeA = { value: "A", next: null };
const nodeB = { value: "B", next: null };
const nodeC = { value: "C", next: null };
nodeA.next = nodeB;
nodeB.next = nodeC;value はノードが持つ値です。next は次のノードを指すためのプロパティです。nodeA.next に nodeB を入れることで、Aの次はBだと表しています。
A -> B -> C -> null最後のノードであるCの next は null のままです。これは、次のノードがないことを表します。
基本情報ではポインタという言葉が出てきます。ここでは、ポインタを「次のデータを指す情報」と考えると理解しやすくなります。
連結リストのノードは、値と次のノードへの参照を持ちます。
JavaScriptで連結リストを作ってみる
ここでは、学習用の小さな連結リストを作ります。まず、ノードを表す Node クラスを用意します。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}次に、連結リスト全体を表す LinkedList クラスを作ります。先頭のノードを head として持たせます。
class LinkedList {
constructor() {
this.head = null;
}
append(value) {
const newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
toArray() {
const result = [];
let current = this.head;
while (current !== null) {
result.push(current.value);
current = current.next;
}
return result;
}
}
const list = new LinkedList();
list.append("A");
list.append("B");
list.append("C");
console.log(list.toArray());append() は、末尾に新しいノードを追加するメソッドです。リストが空なら、新しいノードをそのまま head にします。
すでにノードがある場合は、current.next をたどりながら末尾まで進みます。末尾のノードは next が null なので、そこに新しいノードをつなぎます。
toArray() は、確認用のメソッドです。連結リストを先頭からたどり、値だけを配列に入れて返しています。
連結リストでは、先頭ノードから next をたどることで、順番にデータへアクセスします。
追加・探索・削除の考え方
連結リストの操作は、「つながりをどう変えるか」として考えると分かりやすくなります。
末尾への追加では、最後のノードの next を新しいノードに向けます。
A -> B -> nullここにCを追加するなら、Bの next をCにします。
A -> B -> C -> null探索では、先頭から順番に next をたどります。たとえば、値が "B" のノードを探すなら、Aを見て、違えばBへ進みます。
function includes(list, target) {
let current = list.head;
while (current !== null) {
if (current.value === target) {
return true;
}
current = current.next;
}
return false;
}削除では、前のノードの next を付け替えます。たとえば、A、B、Cの並びからBを削除する場合、Aの next をCに向けます。
A -> B -> C
A ------> CBそのものを移動するというより、Bを指していたつながりを飛ばすイメージです。
連結リストの追加や削除は、ノード同士の参照を付け替える操作として理解できます。
計算量: 得意な処理と苦手な処理
連結リストは、配列と同じように順番を持つデータ構造ですが、計算量の特徴は異なります。
まず、先頭への追加は得意です。新しいノードの next を現在の先頭に向け、その新しいノードを head にすればよいからです。
new -> A -> B -> C一方で、添字を使って直接アクセスするのは苦手です。配列なら array[2] のように書けますが、連結リストでは3つ目のノードへ行くために、先頭から順番にたどる必要があります。
そのため、特定の値を探す処理は O(n) になりやすいです。要素数が増えるほど、最悪の場合は最後まで確認する必要があります。
また、末尾への追加も、末尾を毎回先頭から探す実装では O(n) になります。末尾のノードを tail として持てば、末尾追加を速くできます。
連結リストは、つながりの付け替えが得意な一方、添字による直接アクセスは苦手です。
試験ではどう問われるか
基本情報技術者試験では、連結リストの図を見て、挿入や削除のあとにどのノードがどこを指すかを問われることがあります。
特に重要なのは、ポインタや参照の付け替えです。新しいノードを間に入れる場合は、前のノードと新しいノード、新しいノードと次のノードのつながりを正しく考える必要があります。
削除では、削除したいノードの前にあるノードが、削除したいノードの次を指すようにします。ここを間違えると、リストの一部がたどれなくなります。
また、配列との違いも問われやすいところです。配列は添字アクセスが得意で、連結リストは参照をたどります。探索が O(n) になりやすい点も押さえておくとよいです。
試験では、ノード同士の参照が挿入や削除でどう変わるかを追う力が重要です。
実務ではどう使われるか
JavaScriptの実務で、連結リストを自分で実装する場面は多くありません。多くの場合、配列、Map、標準APIを使ったほうが読みやすく、保守もしやすいです。
それでも、連結リストを学ぶ意味はあります。データ構造は、標準機能の使い方だけでなく、データをどう持つかを考えるための道具だからです。
たとえば、キューやスタックは連結リストで実装できます。履歴をたどる処理、順番につながるタスク、低レベルなメモリ管理の説明でも、連結リストの考え方が出てくることがあります。
Web開発では、直接連結リストを書く機会が少なくても、参照をつなぐ、付け替える、たどる、という考え方は役立ちます。オブジェクト同士の関係を扱うときにも、この感覚は土台になります。
実務で連結リストを直接書く場面は多くありませんが、参照をたどるデータ構造の考え方は多くの設計理解につながります。
まとめ: 連結リストはデータ構造のつながりを理解する入口
連結リストは、ノードが次のノードへの参照を持ち、先頭から順番にたどるデータ構造です。配列と同じように順番を持ちますが、データの持ち方は大きく違います。
配列は添字によるアクセスが得意です。一方、連結リストは参照の付け替えによって、挿入や削除を考えやすい場面があります。ただし、目的の要素を探すには先頭からたどる必要があり、探索は O(n) になりやすいです。
JavaScriptでは、オブジェクトの next プロパティを使うことで、連結リストの考え方を確認できます。基本情報の学習では、ポインタ、参照、挿入、削除の理解につながる重要な題材です。
連結リストを理解すると、配列とは違うデータの持ち方や、参照を付け替える処理の考え方が身につきます。
コメント