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

まず結論

連結リストとは、各要素がデータ部と、次の要素の場所を示すポインタ部を持ち、参照によって順番につながるデータ構造です。

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

データ部＋次の要素を指すポインタ部
→ 連結リスト

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

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

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

直感的な説明

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

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

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

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

定義・仕組み

連結リストの一つ一つの要素は、一般にノード（節点）と呼ばれます。

基本的な単方向連結リストのノードは、次の二つから構成されます。

構成要素	役割
データ部	値や情報を保存する
ポインタ部	次のノードの格納先を指す

[データ部 | ポインタ部] → [データ部 | ポインタ部] → 終端

単方向連結リスト

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

A → B → C

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

双方向連結リスト

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

A ⇄ B ⇄ C

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

配列との違い

比較項目	配列	連結リスト
要素の配置	連続して並ぶ	参照でつながる
添字によるアクセス	速い	先頭からたどる必要がある
挿入・削除	要素の移動が必要になることがある	参照の付け替えで対応しやすい
メモリ	要素本体が中心	参照用の領域も必要

科目Aでどう出る？

科目Aでは、説明文から該当するデータ構造を選ぶ問題として出題されます。

次の表現を見分けます。

データ部と、次のデータの格納先を指すポインタ部
→ 連結リスト

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

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

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

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

問題文の表現	判断
ポインタの付け替えで挿入・削除する	連結リスト
要素をずらして挿入・削除する	配列
後入れ先出し	スタック
先入れ先出し	キュー

科目Bでどう使う？

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

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

A → B → C

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

A → X → B → C

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

削除でも同様です。

A → B → C

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

A → C

よくある誤解・混同

誤解1：連結リストは添字で直接アクセスできる

基本的にはできません。

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

誤解2：双方向連結リストは単方向より常に優れている

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

誤解3：連結リストは挿入・削除が必ず高速

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

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

誤解4：スタックやキューと同じ

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

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

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

誤解5：配列もポインタの付け替えだけで挿入・削除できる

配列では、途中に要素を入れたり削除したりすると、後ろの要素を移動する必要があることがあります。

ポインタの付け替えでつなぎ方を変えるのは、連結リストの特徴です。

まとめ（試験直前用）

連結リストは、データ部とポインタ部を持つ要素を参照でつなぐ
単方向は次だけ、双方向は前後をたどれる
配列は添字で直接アクセスしやすい
連結リストは参照の付け替えで挿入・削除しやすい
「データ部＋次の格納先を指すポインタ部」とあれば連結リスト
位置を探す時間と参照用の領域にも注意する

🔗 関連記事

🏠 基本情報技術者トップに戻る