基本情報技術者 2013年 秋期 午前（科目A） 問06

リストを配列で実現した場合の特徴【午前2 解説】

要点まとめ

• 結論→配列で実現したリストは、事前に最大長分の領域を確保する方式が一般的で実際の要素数に関わらず未使用領域が生じる可能性がある。
• 根拠→固定長配列は容量が固定で、挿入や削除で要素をシフトする必要があり中間操作は要素数に比例した時間を要するがランダムアクセスは高速である。
• 差がつくポイント→動的配列（再割当てあり）と固定配列を区別し、挿入・削除・参照の時間計算量とメモリ効率の違いを具体的に理解しておくこと。

正解の理由

よくある誤解

• 「配列だから挿入も削除も常に高速」：配列はランダムアクセスは O(1) ですが、先頭や中間への挿入・削除は要素移動が必要で O(n) になります。
• 「配列実装＝常に固定長」：動的配列は自動的に再割当てして容量を拡張するが、その際にはコピーコストが必要で一時的に余分なメモリを使うことがある。
• 「連結リストのように次要素用領域が必要」：これは連結リストの特徴であり、配列実装では要素格納領域以外に“次ポインタ”領域は通常不要です。

解法ステップ

1. 各選択肢が「配列実装の特徴」として一般的に当てはまるかを確認します。
2. 「メモリの確保方法」「要素参照時間」「挿入・削除の時間」「追加のポインタ領域」の4点で評価します。
3. 配列はランダムアクセスが速い（インデックスで直接参照）こと、固定容量や余分領域の可能性があることを思い出す。
4. それぞれの選択肢と配列の特徴を照合し、最も合致するものを選びます。

選択肢別の誤答解説

• ア: 正しい。配列実装では最大長分の領域を確保する設計があり、実際に使用されない領域（空き）が生じる可能性がある。静的配列を念頭に置いた記述として正確です。
• イ: 誤り。配列は挿入・削除が常に一定時間でできるわけではありません。先頭や中間への挿入削除は要素のシフトが必要で $O(n)$ です（末尾への追加は動的配列で平均 $O(1)$ だが常に一定時間ではない）。
• ウ: 誤り。リストの中間要素を先頭から順にたどる必要があるのは連結リストの性質で、配列ではインデックスで直接アクセスできるため $O(1)$ です。
• エ: 誤り。次要素を指すためのポインタ領域が別途必要なのは連結リスト（ポインタ実装）の特徴で、配列では通常不要です。

補足コラム

• 時間計算量の比較（典型例）
  • 配列（固定/動的）: 参照 $O(1)$、末尾追加（動的・平均）$O(1)$、挿入/削除（先頭/中間） $O(n)$
  • 単方向連結リスト: 参照（インデックス指定） $O(n)$、挿入/削除（位置が分かっている場合） $O(1)$
• メモリ面では配列は要素以外のポインタ領域が不要でオーバーヘッドが小さいが、最大容量を確保することで未使用領域が発生する。連結リストは各要素にポインタ分の追加メモリが必要で、要素数が多いほどオーバーヘッドが増える。
• 実装例（C言語で固定長配列と連結リストノードのイメージ）

// 固定長配列（最大100要素）
int list[100];   // 最大長分の領域を確保、実際の使用数は別管理

// 連結リストのノード（ポインタを持つ）
struct Node {
    int value;
    struct Node *next;  // 次要素へのポインタ領域が必要
};

FAQ