連結リストとは？単方向・双方向と配列の違い【基本情報技術者試験】

まず結論

連結リストとは、各要素が次の要素への参照を持ち、順番につながっているデータ構造です。

基本情報技術者試験では、次の切り分けが重要です。

次の要素だけをたどる
→ 単方向連結リスト

前後どちらにもたどれる
→ 双方向連結リスト

配列のように連続した領域へ並べるのではなく、参照によって要素同士をつなぎます。

連結リストは、数珠つなぎになったカードをイメージすると分かりやすいです。

各カードには、データと次のカードの場所が書かれています。

[10 | 次へ] → [20 | 次へ] → [30 | 終端]

先頭から順番に「次へ」をたどることで、目的の要素へ進みます。

単方向連結リストでは、各要素が次の要素への参照だけを持ちます。

A → B → C

前へ戻るための参照はありません。

双方向連結リストでは、各要素が前と次の両方への参照を持ちます。

A ⇄ B ⇄ C

前後どちらにも移動できます。

科目Aでは、用途や特徴の比較が中心です。

次の表現を見分けます。

前後どちらにもたどれる
→ 双方向連結リスト

添字で直接アクセスする
→ 配列

先頭から順番にたどる
→ 連結リスト

また、途中への挿入や削除では、参照の付け替えが中心になる点も問われます。

科目Bでは、参照の付け替えを追う問題に使われます。

たとえば、次の単方向連結リストに X を挿入します。

A → B → C

A と B の間に入れる場合は、次のように参照を変更します。

A → X → B → C

処理のポイントは、データ自体を大きく移動するのではなく、参照先を変更することです。

削除でも同様です。

A → B → C

B を削除するなら、A の次を C に変更します。

A → C

基本的にはできません。

目的の要素まで、先頭から順番にたどる必要があります。

前後に移動できる一方、前向き・後ろ向きの参照を保持するため、必要な領域や更新処理は増えます。

挿入位置が分かっていれば参照の付け替えで済みます。

ただし、位置を探すために先頭からたどる必要がある場合は、その探索時間も考えます。

スタックやキューは、データを取り出す順番に注目した考え方です。

連結リストは、要素同士を参照でつなぐ構造です。

連結リストを使ってスタックやキューを実装することはできますが、用語の意味は異なります。