基本情報技術者 2017年 春期 午前（科目A） 問04

配列実装のリスト特性【午前解説】

正解の理由

解法ステップ

1. 問題文で「配列を用いたリスト」と「ポインタを用いたリスト（連結リスト）」の実装差を確認する。
2. 配列：要素が連続格納 → インデックスから直接アクセス可能（O(1））。連結リスト：ポインタで接続 → 先頭から辿る必要。
3. 各選択肢を「ランダムアクセス」「挿入・削除」「要素移動」の観点で評価する。
4. 最も配列の特性に合致する選択肢を選ぶ（本問ではランダムアクセスが該当）。

選択肢別の誤答解説

• ア: 正解。配列は要素のアドレスを計算して直接参照できるため、任意位置へのランダムアクセスが効率的です。
• イ: 誤り。配列では先頭に挿入すると以降の要素を全て一つずつ後ろにシフトする必要があり O(n) であり、連結リストであれば先頭挿入は O(1) です。
• ウ: 誤り。説明は連結リストの特徴（参照は先頭から辿るため非効率だが挿入削除はポインタ操作で効率的）を示しており、配列の特徴とは逆です。
• エ: 誤り。配列で任意のデータを別位置へ移す場合、通常は要素の移動（またはシフト）が必要であり「隣接データを移動せずにできる」は連結リストの参照の付け替えで可能な挙動ですが、データ自体を移動しないという意味では連結リストの方が有利です。

よくある誤解

• 「配列は常に挿入・削除が速い」と誤解しやすい：任意位置での挿入・削除は要素のシフトが必要で O(n) です。
• 「ポインタを使ったリストでもインデックスで即アクセスできる」と誤る：連結リストは先頭から順に辿る必要がありランダムアクセスは効率的ではありません。
• 動的配列（伸縮する配列）と静的配列を混同して、増長コストを軽視するミス。

補足コラム

• 動的配列（例えば配列を倍増して容量を確保する実装）では、末尾への追加は平均的に O(1)（アモルタイズド）ですが、再割当て時には O(n) のコストが発生します。
• メモリ局所性（キャッシュ効果）は配列の大きな利点で、連続走査が多い処理では配列が著しく高速になります。
• 逆に頻繁な任意位置への挿入削除が多い用途（例：キューの中間操作）では連結リストや別データ構造を選択する方が適切です。

FAQ