リンクリスト構築と長さの計算
リンクリストとは何か
このレッスンで分かること
- 連結リスト (Linked List) は「データ + 次のノードへの参照」を持つノードが鎖状につながる構造
- 配列とは違い、メモリ上で連続している必要はなく、対象ノードへの参照が既にあれば
挿入 / 削除がO(1)で可能（位置を先頭から探す場合はO(n)）- 本レッスンでは配列を「入力」として、自分で
Nodeを組み立て、headからnextを辿って長さを数える- Python 最小実装は次の通り
Python
class Node: def __init__(self, v): self.value = v; self.next = None def buildList(arr): head = tail = None for v in arr: node = Node(v) if head is None: head = tail = node else: tail.next = node; tail = node return head
リンクリスト構築と長さの計算 とは
配列から仮想的なリンクリストを構築し、その長さを返す関数を実装してデータ構造の基本を理解する。本レッスンでは、リンクリスト構築と長さの計算 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
配列は便利ですが、要素を途中に挿入したり削除したりすると、後ろの要素を全部ずらす必要があり、O(n) の時間がかかります。これを 連結リスト で書き換えると、その場所のノードへの参照を持っていれば前後の next ポインタを付け替えるだけで挿入や削除が O(1) で行えます（位置を先頭から探す場合は O(n) の探索コストが加わります）。連結リストは「データ」と「次のノードへのポインタ」をペアで持つ ノード が、鎖のように繋がった構造です。
本レッスンでは入力の配列から実際に Node オブジェクトを 手で組み立てて、head から next を辿りながらノード数を数える、という練習をします。配列の長さを返すだけでは連結リストを学んだことにならないので、配列はあくまで「ビルダーへの入力」と捉えてください。
配列は連続したメモリにデータを並べる。連結リストは ノードがポインタで繋がる ため、メモリ上では離れていても良い。
連結リストの強みと弱み
挿入や削除は強い反面、ランダムアクセスは弱いです。配列なら arr[100] で 100 番目に一瞬で行けますが、連結リストは先頭から next ポインタを 100 回辿る必要があり O(n) です。配列 と 連結リスト のどちらを使うかは、用途次第です。検索が多いなら 配列、頻繁な挿入削除があるなら 連結リスト が向いています。
配列 vs 連結リスト — 計算量の比較
| 操作 | 配列 | 連結リスト |
|---|---|---|
ランダムアクセス (arr[i]) | O(1) | O(n) |
末尾追加 (push) | O(1) 平均 | O(1) (tail を持てば) |
| 先頭挿入 | O(n) | O(1) |
| 任意位置の削除 | O(n) | O(1) (ノード参照済みなら) |
| メモリ使用量 | データだけ | データ + ポインタ |
ランダムアクセスは
配列が圧倒的。挿入削除は連結リストが有利。
ノードの定義
連結リストの 1 単位は ノード です。ノードは value (中身) と next (次のノードへの参照、末尾なら null) の 2 つを持ちます。
Python
class Node:
def __init__(self, value):
self.value = value
self.next = NoneJavaScript
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}ビジュアルで理解する
図の読み方 (同じ情報を箇条書きで再掲)
headは先頭ノードNode 1を指しているNode 1.nextはNode 2を指しているNode 2.nextはNode 3を指しているNode 3.nextはnull(= リスト末尾の合図)headからnextを辿ってnullに到達するまでの個数がリストの 長さ
配列からリンクリストを構築する
入力の配列 [10, 20, 30] から 10 -> 20 -> 30 -> null のリストを組み立てる手順は次の通りです。
- 最初の要素から
headノードを作る - 次の要素ごとに新しいノードを作り、前のノードの
nextに繋ぐ - 末尾を覚えておくと毎回先頭から辿らずに済む (
tailポインタを保持)
Python での実装例は次の通りです。
Python
def buildList(arr):
if not arr:
return None
head = Node(arr[0])
tail = head
for v in arr[1:]:
tail.next = Node(v)
tail = tail.next
return headJavaScript も同じ考え方で書けます。先頭ノードを作り、tail を進めながら next で繋いでいきます。
JavaScript
function buildList(arr) {
if (arr.length === 0) return null;
const head = new Node(arr[0]);
let tail = head;
for (let i = 1; i < arr.length; i++) {
tail.next = new Node(arr[i]);
tail = tail.next;
}
return head;
}head から辿って長さを数える
リストを組み立てたら、head から next を辿って末尾 (null) まで到達する間に通ったノード数を数えます。
Python
def listLength(head):
count = 0
cur = head
while cur is not None:
count += 1
cur = cur.next
return countwhile cur is not None: の条件で末尾 (next が None のノードの次) に到達した瞬間にループが止まる、というのが連結リストの典型的な走査パターンです。
よくある間違い
1 つ目は arr.length で済ませてしまう ケースです。配列の長さを返すだけでは連結リストを「辿った」ことにならず、本レッスンの趣旨を外します。必ず Node を作って next で繋ぎ、head から辿って数えてください。
2 つ目は tail を更新し忘れる ケース。tail.next = new の後に tail = tail.next を書かないと、tail が先頭のままになり next が次々上書きされ、結果として 2 要素のリストしかできません。
3 つ目は 空配列の扱い。空配列 [] の場合は head = null で、長さは 0 です。buildList([]) の戻り値を None にしておけば、listLength 側で自然と 0 が返ります。
やってみよう
[10, 20, 30, 40, 50]を渡したら5が返ることを確認する- 空配列
[]を渡したら0が返ることを確認する - 値に
0や負数 (-5など) が混ざっていても正しく数えられるか確認する - 走査ループを再帰で書き直してみる。
listLength(head)を0 if head is None else 1 + listLength(head.next)で書ける - 入力の配列を 使い切らずに走査する バージョン (途中で止める) を書いてみる。例えば最初の
nullで止める、など
連結リストが活躍するシーン
連結リストは、ブラウザの履歴管理 (戻る / 進む) や、音楽プレーヤーの再生キュー、エディタの undo/redo 履歴など、挿入 と 削除 が頻繁に起きるデータで威力を発揮します。配列 だと中央への挿入で全要素を後ろにずらす必要があり O(n) ですが、連結リストなら前後の next ポインタを付け替えるだけで O(1) です。
また、OS のメモリ管理でも 空きメモリブロックのリスト を連結リストで持っており、必要な時に先頭から取り出して使う、という運用が一般的です。malloc の内部実装もこのような連結リストベースで動いています。
連結リストは 頻繁な挿入削除 が起きる場面で輝く。OS やブラウザ内部でも実は多用されている。
計算量の確認
リンクリストの長さを返す処理は、head から末尾まで全ノードを 1 回ずつ訪れる必要があるため O(n) 時間です。各ノードでの作業は count += 1 だけなので定数時間。トータルでも O(n) 時間、O(1) 追加空間で完結します。リスト自体は O(n) メモリを占めますが、走査中に新しく確保するメモリはありません。
連結リストの長さ取得は
O(n)。配列のlenはO(1)なので、頻繁に長さを取るなら配列の方が有利。
本コースではこの後、反転 / サイクル検出 / マージ / 中央取得 / 重複削除 と、より高度なアルゴリズムを学んでいきます。すべて head から next を辿る 感覚が土台になっているので、本レッスンでしっかり手に馴染ませてください。
連結リストは ノードを辿る イメージを掴むことが大事。
buildListでリストを組み立て、headからnextを辿って末尾のnullまでカウントする、という一連の流れを身体に覚え込ませよう。
よくある質問
Q. リンクリストと配列はどう使い分けますか？
A. 配列はランダムアクセス O(1)、リンクリストは先頭への追加 O(1) が強みです。ほとんどの実用ケースで配列の方が速く、リンクリストはアルゴリズム問題の練習や特殊用途（OS のスケジューラ等）で使われる程度です。
Q. サイクル検出はどう実装しますか？
A. Floyd の循環検出（2 ポインタ法、tortoise and hare）が定番です。slow を 1 ステップ、fast を 2 ステップ進めると、ループがあれば必ず同じノードで出会います。空間 O(1) で動くのが優秀な点です。
Q. リンクリストを反転するコツは？
A. prev, curr, next の 3 ポインタを使い、curr.next = prev で 1 個ずつ繋ぎ替えます。再帰版でも書けますが、反復版の方がスタック消費が無く安全です。LeetCode の Reverse Linked List が定型問題なので解いておくと良いです。
次のレッスン
次は リンクリストの反転 で、配列から仮想的なリンクリストを構築し、その長さを返す関数を実装してデータ構造の基本を理解する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- リンクリスト構築 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. リンクリスト構築 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 内部で Node オブジェクト (value + next) を組み立てること
- head から next ポインタを辿ってノード数を数えること
- arr.length / len(arr) を直接返さないこと (走査が前提)
入出力例
test-cases.txt
listLength([1,2,3]) → 3
listLength([42]) → 1
listLength([5,6,7,8,9]) → 5
listLength([0,0,0,0]) → 4
listLength([-1,-2,-3]) → 3
listLength([1,2,3,4,5,6,7,8,9,10]) → 10