連結リストとは（全体像）
連結リストは、データに「次はこれ」という矢印（ポインタ）をつけて、一列につないだもの。一つひとつの要素が、自分の中身と「次の要素の場所」をセットで持っている。
配列との大きな違いは、置き場所がバラバラでもよいこと。配列は箱がぴったり隣り合って並ぶが、連結リストは離れた場所にあっても矢印でたどれる。
押さえるのは、つなぎ方で3種類に分かれること。
- 単方向リスト … 「次へ」の矢印だけ。前から後ろへの一方通行。
- 双方向リスト … 「前へ」「次へ」の両方の矢印を持ち、前後にたどれる。
- 循環リスト … 末尾の要素が先頭を指していて、ぐるっと一周する。
身近に置きかえると、単方向は順番待ちの行列（前の人しか見えない）、双方向は本のしおり（前後のページを行き来できる）、循環は観覧車（最後まで行くと先頭に戻る）というイメージだ。
詳しく：3種類と「速い・遅い」だけ覚えれば戦える
ここが記事の心臓部。連結リストの中身は、次の2つの表につまっている。
連結リストの3種類
| 種類 | 持っている矢印 | 特徴 |
|---|---|---|
| 単方向 | 次へ（1本） | 前から後ろへ一方通行・省メモリ |
| 双方向 | 前へ＋次へ（2本） | 前後どちらにもたどれる |
| 循環 | 次へ（末尾→先頭） | ぐるっと一周できる |
もう一つの心臓部が、得意・不得意（計算量）。`O(1)`は「一瞬」、`O(n)`は「数が増えると比例して時間がかかる」という意味だと思えばよい。
連結リストと配列の得意・不得意
| 操作 | 連結リスト | 配列 |
|---|---|---|
| 番号での取り出し | 遅い（O(n)・先頭からたどる） | 速い（O(1)） |
| 先頭の挿入・削除 | 速い（O(1)） | 遅い（O(n)・ずらす必要） |
| 置き場所 | バラバラでよい | 連続して並ぶ |
つまりポイントは、連結リストは「先頭の出し入れ」が得意で、「番号での取り出し」が苦手ということ。番号で取り出すには先頭から矢印を順にたどるしかないので、後ろのほうほど時間がかかる。逆に配列は番号で一発アクセスできるが、間に入れると後ろをずらすので遅い、というわけだね。
なお、「中間に入れる」のが速いと誤解しやすいが、入れる場所までたどるのにO(n)かかるので、ひとくちに速いとはいえない。
わかりやすく言い換えると
要するに、連結リストは「矢印でつないだ数珠」だ。
①単方向 … 次へ進む矢印だけ（順番待ちの行列）
②双方向 … 前にも後ろにも進める（本のしおり）
③循環 … 最後から先頭に戻る（観覧車）
そして性格は「先頭の出し入れは速い・番号での取り出しは遅い」。配列と正反対だと覚えると混ざらない。
試験のツボ
🔴 一番出る：3種類の違い
①単方向 ＝ 次への矢印だけ（一方通行）
②双方向 ＝ 前後どちらにもたどれる
③循環 ＝ 末尾が先頭を指して一周する
🔴 次に出る：先頭は速い・番号アクセスは遅い
①先頭の挿入・削除はO(1)（速い）
②番号での取り出しはO(n)（先頭からたどるので遅い）
🟡 押さえると安定：配列との対比
①配列は番号アクセスO(1)・先頭挿入O(n)
②連結リストはちょうど逆の性格
よくある間違い
①「連結リストは配列と同じもの」→ ✗ 連結リストは置き場所がバラバラで、矢印でつなぐ。配列は連続して並ぶ。
②「番号での取り出しもO(1)で速い」→ ✗ 番号アクセスは先頭からたどるのでO(n)。速いのは配列のほう。
③「中間への挿入は必ずO(1)」→ ✗ 入れる場所までたどるのにO(n)かかるので、ひとくちに速いとはいえない。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（3種類の違い）
連結リストの種類に関する次の記述のうち、正しいものはどれか。
- 単方向は次への矢印だけを持ち、双方向は前後の矢印、循環は末尾が先頭を指す
- 単方向リストは前後どちらにもたどれるが、双方向リストは前にしかたどれない
- 循環リストは矢印をいっさい持たず、要素どうしはまったくつながっていない並びだ
- 連結リストに種類の区別はなく、どれも前後と先頭への矢印を必ず3本ずつ持っている
解答は 1 だよ。
単方向は次への矢印だけ、双方向は前後の矢印、循環は末尾が先頭を指すんだ。「単（次だけ）・双（前後）・循（一周）」で覚えてね。
選択肢2は単方向と双方向が逆。選択肢3の「矢印がない」、選択肢4の「区別がない」はどちらも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 単＝次・双＝前後・循＝一周 |
| 2 | ✗ | 前後にたどれるのは双方向 |
| 3 | ✗ | 矢印でつながっている |
| 4 | ✗ | 種類ごとに矢印の数が違う |
オリジナル問題2（計算量の特徴）
連結リストの操作の速さに関する次の記述のうち、正しいものはどれか。
- 番号での取り出しはO(1)で一瞬だが、先頭への挿入や削除のほうはO(n)で遅い
- 番号での取り出しも先頭の挿入も、どちらもO(1)で一瞬に終わるものとされている
- 先頭への挿入や削除はO(1)で速く、番号での取り出しはO(n)で先頭からたどる
- すべての操作がO(n)で、要素の数が増えてもまったく速さは変わらないものである
解答は 3 だよ。
連結リストは先頭の挿入・削除がO(1)（速い）、番号での取り出しはO(n)（先頭からたどるので遅い）なんだ。配列とはちょうど逆の性格だよ。
選択肢1は速い・遅いが逆。選択肢2の「どちらもO(1)」、選択肢4の「速さが変わらない」も誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 速い・遅いが逆 |
| 2 | ✗ | 番号アクセスはO(n) |
| 3 | ✓ | 先頭O(1)・番号アクセスO(n) |
| 4 | ✗ | 操作で速さが異なる |
オリジナル問題3（配列との対比）
連結リストと配列の比較に関する次の記述のうち、正しいものはどれか。
- 配列も連結リストもまったく同じ性格で、どんな操作でも速さに違いは出ないものだ
- 配列は番号アクセスが速く先頭の挿入が遅い、連結リストはその逆の性格を持っている
- 配列は置き場所がバラバラで、連結リストは箱がぴったり連続して並ぶしくみである
- 配列は番号アクセスが遅く、連結リストは番号アクセスが速いという特徴を持っている
解答は 2 だよ。
配列は番号アクセスが速く（O(1)）・先頭の挿入が遅い（O(n)）、連結リストはその逆なんだ。よく先頭をいじるならリスト、よく番号で探すなら配列、と使い分けるよ。
選択肢1の「違いがない」、選択肢3の「置き場所が逆」、選択肢4の「番号アクセスが逆」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 操作で速さが異なる |
| 2 | ✓ | 配列とリストは正反対の性格 |
| 3 | ✗ | 連続して並ぶのは配列 |
| 4 | ✗ | 番号アクセスが速いのは配列 |
まとめ
押さえどころ
- 🔴 3種類 ＝ 単方向（次だけ）・双方向（前後）・循環（末尾→先頭で一周）。
- 🔴 速い・遅い ＝ 先頭の挿入・削除はO(1)で速い、番号での取り出しはO(n)で遅い。
- 🟡 配列との対比 ＝ 配列は番号アクセスが速く先頭挿入が遅い。連結リストはその逆。
次に学ぶ
執筆: SikakuQuest編集部