連結リストが配列より優れている操作とは¶
原文¶
Interviewer:
Why is a linked list better than an array for some operations?
要約¶
連結リストは先頭・途中への挿入・削除が O(1) で可能（配列は O(n) のシフトが必要）。また動的にサイズが変わるデータに向いている。一方、ランダムアクセスは O(n) と遅く、メモリ局所性が悪い。
回答¶
連結リストが配列より優れているケース：
- 先頭/途中への挿入・削除が O(1) → 配列は要素のシフトで O(n) かかる
- 動的なサイズ変更 → 事前にサイズを確保する必要がない
- メモリの断片的な確保 → 連続したメモリ領域が不要
解説¶
計算量の比較¶
| 操作 | 配列（Array） | 連結リスト（Linked List） |
|---|---|---|
| 先頭への挿入 | O(n)（シフト必要） | O(1) |
| 末尾への挿入 | O(1)（末尾がわかっている場合） | O(n)（末尾まで辿る）/ O(1)（tail ポインタあり） |
| 中間への挿入 | O(n)（シフト必要） | O(1)（ノードのポインタ変更のみ） |
| 削除 | O(n)（シフト必要） | O(1)（ポインタ変更のみ） |
| ランダムアクセス | O(1) | O(n)（辿る必要がある） |
| 検索 | O(n) / O(log n)（ソート済み） | O(n) |
具体的な使いどころ¶
連結リストが向いている： - キューの実装（先頭からの削除が多い） - LRU キャッシュの実装（中間ノードの削除） - テキストエディタの undo/redo スタック - メモリプール管理
配列が向いている： - インデックスによるランダムアクセスが必要な場合 - キャッシュ効率が重要な処理（CPU キャッシュラインを活用） - バイナリサーチ（ソート済み配列 + O(log n)）
Go での実装例¶
// 連結リストのノード
type Node struct {
Value int
Next *Node
}
// 先頭への挿入 O(1)
func prepend(head *Node, val int) *Node {
return &Node{Value: val, Next: head}
}
面接での答え方¶
「連結リストは先頭や中間への挿入・削除が O(1) で行えます。配列の場合はシフト処理が O(n) 必要です。一方、ランダムアクセスは配列の O(1) に対して連結リストは O(n) です。キューやLRUキャッシュのように頻繁に先頭から削除する場合は連結リストが適しています。」
→ 関連: シニア昇格トピック