BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
連結リスト
参照で要素をつなぐ
連結リストは、各要素が次の要素への参照を持ち、それをたどって順序を表すデータ構造です。配列のように全要素が連続した位置に置かれることを前提にしません。データと参照を持つ要素を節と呼ぶことがあります。先頭の参照から順にたどることで、離れた場所にある要素でも一つの列として扱えます。
挿入の考え方
Aの次がCになっているところへBを入れるなら、Bの次をCにし、Aの次をBに変更します。後ろにある全データを一つずつ移動する必要はありません。ただし、Aの場所を探す時間は別です。挿入位置への参照が既にある場合の費用と、位置を見つけるまでを含む費用を分けて評価します。
参照を書き換える例
Before: head -> A -> C -> null
new_node.value = B
new_node.next = current.next
current.next = new_node
After: head -> A -> B -> C -> null
先に元の次の参照を保存することが重要です。順序を誤って参照を失うと、残りの要素をたどれなくなる可能性があります。先頭へ挿入する場合は、head自体を更新します。
種類と探索
単方向リストは次への参照を持ち、双方向リストは前への参照も持ちます。末尾から先頭へつなぐ循環リストもあります。双方向なら逆向きにたどれますが、参照の保存領域や更新する箇所が増えます。配列の添字のように、任意の何番目へ直接移動できるとは限らず、順にたどる探索には時間がかかります。
試験での要点
削除では、前の要素の参照を次の要素へつなぎ直します。削除対象が先頭や末尾の場合、空になる場合も確認します。メモリーを自分で管理する言語では、不要な領域の解放にも注意が必要です。試験では、値の並びだけでなく矢印の向きを書き、代入を一行ずつ反映すると安全です。配列との比較では、位置の探索、挿入・削除、参照の記憶量という三つの費用を分けましょう。
参考資料
内容確認日:2026-11-13