最終更新日:2026年10月15日
fe fe-technology data-structure algorithm
まず結論
連結リストとは、各要素がデータ部と、次の要素の場所を示すポインタ部を持ち、参照によって順番につながるデータ構造です。
基本情報技術者試験では、次の切り分けが重要です。
データ部+次の要素を指すポインタ部
→ 連結リスト
次の要素だけをたどる
→ 単方向連結リスト
前後どちらにもたどれる
→ 双方向連結リスト
配列のように連続した領域へ並べるのではなく、参照によって要素同士をつなぎます。
直感的な説明
連結リストは、数珠つなぎになったカードをイメージすると分かりやすいです。
各カードには、データと次のカードの場所が書かれています。
[10 | 次へ] → [20 | 次へ] → [30 | 終端]
先頭から順番に「次へ」をたどることで、目的の要素へ進みます。
定義・仕組み
連結リストの一つ一つの要素は、一般にノード(節点)と呼ばれます。
基本的な単方向連結リストのノードは、次の二つから構成されます。
| 構成要素 | 役割 |
|---|---|
| データ部 | 値や情報を保存する |
| ポインタ部 | 次のノードの格納先を指す |
[データ部 | ポインタ部] → [データ部 | ポインタ部] → 終端
単方向連結リスト
単方向連結リストでは、各要素が次の要素への参照だけを持ちます。
A → B → C
前へ戻るための参照はありません。
双方向連結リスト
双方向連結リストでは、各要素が前と次の両方への参照を持ちます。
A ⇄ B ⇄ C
前後どちらにも移動できます。
配列との違い
| 比較項目 | 配列 | 連結リスト |
|---|---|---|
| 要素の配置 | 連続して並ぶ | 参照でつながる |
| 添字によるアクセス | 速い | 先頭からたどる必要がある |
| 挿入・削除 | 要素の移動が必要になることがある | 参照の付け替えで対応しやすい |
| メモリ | 要素本体が中心 | 参照用の領域も必要 |
科目Aでどう出る?
科目Aでは、説明文から該当するデータ構造を選ぶ問題として出題されます。
次の表現を見分けます。
データ部と、次のデータの格納先を指すポインタ部
→ 連結リスト
前後どちらにもたどれる
→ 双方向連結リスト
添字で直接アクセスする
→ 配列
先頭から順番にたどる
→ 連結リスト
また、途中への挿入や削除では、参照の付け替えが中心になる点も問われます。
| 問題文の表現 | 判断 |
|---|---|
| ポインタの付け替えで挿入・削除する | 連結リスト |
| 要素をずらして挿入・削除する | 配列 |
| 後入れ先出し | スタック |
| 先入れ先出し | キュー |
科目Bでどう使う?
科目Bでは、参照の付け替えを追う問題に使われます。
たとえば、次の単方向連結リストに X を挿入します。
A → B → C
A と B の間に入れる場合は、次のように参照を変更します。
A → X → B → C
処理のポイントは、データ自体を大きく移動するのではなく、参照先を変更することです。
参照をたどる操作と、つなぎ替える操作の違い
科目Bの疑似言語で prev が出てきたときは、配列ではなく、ある一つのノードを指す変数として考えます。
listHead → A → B → C → D → 終端
prev → A
各ノードは値 val と、次のノードへの参照 next を持つとします。
| 式 | prevがAを指している場合 |
|---|---|
prev |
Aへの参照 |
prev.next |
Bへの参照 |
prev.next.next |
Cへの参照 |
配列の data[1] のように番号で取り出すのではなく、.next を一つずつたどります。
prev ← prev.next
これは prev自身の参照先をAからBに変える 操作です。Aのnextは変わらないため、リストのつながりも変わりません。
一方、prev がBを指しているとき、
prev.next ← prev.next.next
は Bが持つnextをCからDに変更する 操作です。先頭からは A → B → D とたどるため、Cがリストから外れます。これはCのメモリを直接解放する命令とは別です。
図解:prevの移動と、nextの書き換え
見るポイント:同じ「next」が登場しても、左辺の位置によって変わるものが違います。
prevはAを指しています。まず移動を押してみましょう。
Pythonでも確認する
class Node:
def __init__(self, val):
self.val = val
self.next = None
a, b, c, d = (Node(v) for v in "ABCD")
a.next, b.next, c.next = b, c, d
prev = a
prev = prev.next # prevはBを指す。A→B→C→Dは変わらない
prev.next = prev.next.next # Bの次をDに変更する
print(a.next.next.val) # D
ここで、prev = prev.next は変数の代入、prev.next = ... はノードのメンバ変数の変更です。この区別が科目Bのトレースで重要になります。
削除位置までの繰返し
先頭を1番目とし、削除位置を pos とする場合、先頭以外の削除では対象の一つ前を探します。
prev ← listHead
for (iを2からpos-1まで1ずつ増やす)
prev ← prev.next
endfor
prev.next ← prev.next.next
| pos | 繰返し回数 | 変更前にprevが指すノード |
|---|---|---|
| 2 | 0回 | A |
| 3 | 1回 | B |
| 4 | 2回 | C |
pos = 1 の場合だけは一つ前のノードがないので、listHead ← listHead.next として先頭を更新します。なお、末尾を削除するときの右辺は「次の要素がない」状態になります。
削除でも同様です。
A → B → C
B を削除するなら、A の次を C に変更します。
A → C
配列で連結リストを表す問題
FEでは、連結リストを二つの1次元配列で表す問題があります。
例えば、
box[i]
→ 要素の値を保存する
next[i]
→ 次の要素が入っている配列番号を保存する
とします。
このとき、配列番号そのものがリスト上の順番を表すとは限りません。
例えば、次のような状態を考えます。
box[2] = A
box[5] = B
box[1] = C
next[0] = 2
next[2] = 5
next[5] = 1
next[1] = 0
next[0] が先頭を指すとすると、実際のリスト順は
next[0] = 2
↓
box[2] = A
next[2] = 5
↓
box[5] = B
next[5] = 1
↓
box[1] = C
next[1] = 0
↓
終端
なので、
A → B → C
です。
重要なのは、
配列番号ではなく、nextをたどってリスト上の順番を作ること
です。
挿入するときの考え方
例えば、B と C の間に新しい要素 X を入れます。
X が box[7] に入っているとします。
変更前は、
B
box[5]
next[5] = 1
↓
C
box[1]
です。
これを、
B
box[5]
next[5] = 7
↓
X
box[7]
next[7] = 1
↓
C
box[1]
にします。
つまり、挿入時は次の二つを更新します。
新しい要素のnext
→ 後ろの要素を指す
前の要素のnext
→ 新しい要素を指す
試験中は、次の順で追うと安全です。
① next[0] から開始する
↓
② next をたどって実際のリスト順を書く
↓
③ 挿入位置の前後を確認する
↓
④ 新しい要素の next を後ろへつなぐ
↓
⑤ 前の要素の next を新しい要素へつなぐ
配列の添字と値の違いがあいまいな場合は、配列とは?も確認すると整理しやすくなります。
なぜ値と「次の場所」を別々に管理するのか
普通に順番に読むだけなら、配列 [10, 20, 30, 40] で十分です。それでも連結リストを使う理由の一つは、途中へ要素を追加・削除するとき、要素を大量にずらさず、つながりを変更できることです。ただし、追加位置の探索は別に必要な場合があり、連結リストが常に配列より高速という意味ではありません。
配列で連結リストを表すのは、値の保存場所と、リスト上の順番を分離する実装です。例えば値が 10, 30, 20, 40 の順に保存されていても、次の場所が 1 → 3 → 2 → 4 なら、読み出し順は 10 → 20 → 30 → 40 です。実務ではノードが値と参照を一緒に持つ実装も多く、必ず二つの配列にするわけではありません。
関数の目的を先に読む:連結リストを配列に変換する
科目Bでは、コードを細かく追う前に、その関数が何を返すのかを言葉にすると理解しやすくなります。連結リストを先頭からたどり、その順に値を新しい配列へコピーする関数を考えます。これは連結リストを使った追加・削除ではなく、読み出し順を通常の配列として取り出す処理です。
この独立した例では、配列番号を 1から 数え、未定義 は「次の要素がない」ことを表します。
| 配列番号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
dataList(値) |
10 | 30 | 20 | 40 |
pointerList(次の番号) |
3 | 4 | 2 | 未定義 |
関数 orderList()
p ← 1
result ← 空の配列
繰り返す
resultの末尾に dataList[p] を追加
if (pointerList[p] が未定義)
繰り返しを終了
endif
p ← pointerList[p]
繰り返し終了
return result
| 回 | 現在のp | 追加する値 dataList[p] |
次のp pointerList[p] |
結果 |
|---|---|---|---|---|
| 1 | 1 | 10 | 3 | [10] |
| 2 | 3 | 20 | 2 | [10, 20] |
| 3 | 2 | 30 | 4 | [10, 20, 30] |
| 4 | 4 | 40 | 未定義 → 終了 | [10, 20, 30, 40] |
ここでの p は値ではなく、現在の配列番号です。dataList[p] で値を取り、pointerList[p] で次に進む場所を決めます。末尾の値を結果に追加してから終了判定するため、40も失われません。
この変換は、連結リストの値を通常の配列として別の処理に渡すときなどに利用できます。ただし、どの実装でも変換が必要という意味ではありません。
解く前の確認:「この関数は何を参照し、何を返すか」→「現在の位置を表す変数はどれか」→「次の位置と終了条件は何か」の順で整理しましょう。
よくある誤解・混同
誤解0:prevを配列や、すべての要素を持つ変数だと思う
prev はノード一つへの参照です。prev.next は配列の次の添字ではなく、ノードが持つ次の参照です。また、prev ← prev.next は参照変数の移動、prev.next ← prev.next.next はノード間のつながりの変更です。
誤解1:連結リストは添字で直接アクセスできる
基本的にはできません。
目的の要素まで、先頭から順番にたどる必要があります。
誤解2:双方向連結リストは単方向より常に優れている
前後に移動できる一方、前向き・後ろ向きの参照を保持するため、必要な領域や更新処理は増えます。
誤解3:連結リストは挿入・削除が必ず高速
挿入位置が分かっていれば参照の付け替えで済みます。
ただし、位置を探すために先頭からたどる必要がある場合は、その探索時間も考えます。
誤解4:スタックやキューと同じ
スタックやキューは、データを取り出す順番に注目した考え方です。
連結リストは、要素同士を参照でつなぐ構造です。
連結リストを使ってスタックやキューを実装することはできますが、用語の意味は異なります。
誤解5:配列もポインタの付け替えだけで挿入・削除できる
配列では、途中に要素を入れたり削除したりすると、後ろの要素を移動する必要があることがあります。
ポインタの付け替えでつなぎ方を変えるのは、連結リストの特徴です。
誤解6:box[3] はリストの3番目
そうとは限りません。
box[3] の 3 は配列番号です。
リスト上の「何番目か」は、先頭から next をたどって初めて分かります。
配列番号
→ 保存場所
リスト上の順番
→ nextをたどった順番
この二つを分けて考えることが、配列で連結リストを表す問題の最重要ポイントです。
まとめ(試験直前用)
- 連結リストは、データ部とポインタ部を持つ要素を参照でつなぐ
- 単方向は次だけ、双方向は前後をたどれる
- 配列は添字で直接アクセスしやすい
- 連結リストは参照の付け替えで挿入・削除しやすい
prev ← prev.nextは変数の参照先の変更、prev.next ← prev.next.nextはリストのつながりの変更- 「データ部+次の格納先を指すポインタ部」とあれば連結リスト
- 二つの配列で表す問題では、
box[i]が値、next[i]が次の配列番号 - 配列番号とリスト上の順番は別物
- 挿入時は「新しい要素→後ろ」「前の要素→新しい要素」の2本をつなぎ直す
- 位置を探す時間と参照用の領域にも注意する