基本情報技術者 予想問題｜A 第17問

解説

連結リストは、各要素（ノード）がデータと次の要素へのポインタを持つデータ構造である。要素の挿入・削除は、対象位置が分かっていればポインタの付け替えだけで完了するためO(1)で実行でき、イが正解である。アについて、i番目の要素へは先頭からポインタを順に辿る必要があるためランダムアクセスはできず、アクセスにはO(n)を要する。これは添字で直接アクセスできる配列との大きな違いである。ウについて、各ノードはメモリ上に散在してよく、連続領域への確保が必要なのは配列である。エについて、検索も先頭から順に辿るしかなく、整列済み配列の二分探索のような高速化は直接はできない。基本情報技術者試験では、配列と連結リストの比較（参照は配列が有利、挿入・削除はリストが有利）が頻出ポイントであり、両者の長所と短所を対で覚えることが重要である。