基本情報 平成25年度 春期 問6：テクノロジ系に関する問題

答えは a です。

リスト（データを順番に並べた構造）には2つの作り方があります：

• 配列で作る：あらかじめ大きな箱を用意。広い駐車場のようなイメージ。空いてても枠は取られたまま
• ポインタで作る：必要なときに次のデータを指でつないでいく。電車の車両連結のイメージ

配列方式は最初に最大サイズ分の場所を確保するので、実際には使わない領域も発生します。

👉 覚え方：「配列＝広い駐車場（場所先取り）／ポインタ＝電車連結（必要時に追加）」。

ほかの選択肢：b 一定時間で挿入削除はポインタの特徴／c 順番にたどるのもポインタの話／d 次の要素を指す領域はポインタの特徴。

なぜこれが正解か

正解は a。配列実装のリストは、最大要素数分の連続メモリ領域を静的に確保するため、実際の要素数が少ない場合に未使用領域が発生する。一方、ランダムアクセス（O(1) で任意要素参照）が可能なのが配列の利点。

各選択肢の解説（ポインタ実装の特徴）

• b 挿入・削除が一定時間 → ポインタ実装（連結リスト）の特徴（位置特定後はO(1)）。配列は挿入時に要素シフトが必要でO(n)。
• c 中間要素参照に先頭から順番にたどる → ポインタ実装の特徴。配列はインデックスでO(1)アクセス可能。
• d 次の要素を指すための領域が必要 → ポインタ実装の特徴（next ポインタ用メモリ）。

覚え方・ひっかけ注意

配列リスト：ランダムアクセスO(1)、挿入削除O(n)、メモリ静的確保で領域固定。連結リスト（ポインタ）：順次アクセスO(n)、挿入削除O(1)、メモリ動的確保で領域可変。「配列=高速アクセス重視、連結リスト=動的更新重視」と用途で選択。

理論的背景

データ構造としてのリストは抽象データ型（ADT）で、実装方式により計算量とメモリ特性が異なる：

| 操作 | 配列実装 | 単方向連結リスト |

|------|---------|-----------|

| ランダムアクセス | O(1) | O(n) |

| 末尾追加 | O(1) 償却 | O(1)（末尾ポインタ保持時） |

| 先頭追加 | O(n) | O(1) |

| 中間挿入 | O(n) | O(1)（位置特定後） |

| メモリ | 静的確保（最大サイズ） | 動的確保（次ポインタ＋データ） |

| キャッシュ局所性 | 高 | 低（メモリ分散） |

動的配列（ArrayList、std::vector）は満杯時に容量を倍増（償却O(1)）させて静的領域の限界を補う。

実務での使われ方

言語ごとの実装：JavaのArrayList=動的配列、LinkedList=双方向連結リスト。Pythonのlistは動的配列。C++のstd::vector=動的配列、std::list=双方向連結リスト。用途による選択：ランダムアクセス頻発（インデックスでの参照、ソート）→配列、頻繁な挿入削除（キュー、イベント管理）→連結リスト。現代CPUのキャッシュ階層を考慮すると配列の方が実測性能で有利なケースが多い（メモリ局所性によるキャッシュヒット率）。

試験での位置づけ

FE・APアルゴリズム・データ構造の頻出。配列/連結リストの計算量比較、双方向リスト、循環リスト、スタック/キューの配列vs連結リスト実装が定番。応用情報・データベーススペシャリストではB木・B+木・ハッシュテーブルとの比較、計算量解析（漸近表記法、アムダールの法則）まで踏み込む。

関連事項・発展補足

本問の選択肢設計は配列とポインタの対比を明確に問う構造。双方向連結リスト（doubly linked list）は前後ポインタを持ち、後方走査も可能だがメモリオーバーヘッド増。スキップリスト（確率的データ構造）は連結リストに階層を加えてO(log n)検索を実現。B+木はディスクIOを考慮した多分木で、データベースのインデックス実装で広く利用。Java HashMapはハッシュテーブル+連結リスト+赤黒木のハイブリッド構造（衝突時の最適化）。データ構造選定はアクセスパターン（読み多vs書き多）、サイズ（小規模なら配列でも十分）、ハードウェア（CPUキャッシュ、SIMD命令最適化）を総合考慮する実務スキルが求められる。