ポインタを用いた線形リストのデータ構造と特徴

正解は「エ」です。 ポインタを用いた線形リスト（連結リスト）は、各要素がデータ本体と次の要素へのポインタ（参照）を組にして保持するデータ構造です。 リストの途中に要素を挿入・削除する際、前後のポインタの繋ぎ替え（参照の更新）のみで操作が完了するため、配列のように後続の要素全体を物理的にシフト（移動）させるオーバーヘッドが発生しないという大きな利点があります。 配列（静的配列）の特徴です。線形リストは各要素がメモリ上に分散して配置されるため、要素の追加・削除に伴う動的なメモリ確保・解放に適しています。 循環リスト（環状リスト）の説明です。通常の単方向線形リストの末尾ポインタは NULL を指しており、自動的に先頭へ戻ることはありません。 配列の特徴です。配列はインデックスを用いた定数時間 $O(1)$ のランダムアクセスが可能ですが、線形リストで $k$ 番目の要素にアクセスするには先頭からポインタを順に手繰る必要があり、$O(n)$ の時間がかかります。

ポインタを用いた線形リストの特徴として，適切なものはどれか。

出典令和2年度 10月 応用情報技術者試験 午前 問5
ア
要素を連続した物理的記憶領域に配置する必要があるため，メモリの動的な確保や解放には適さない。
イ
最後の要素から最初の要素への巡回参照が常に自動的に行われるため，ループ構造を容易に実装できる。
ウ
添字を指定することによって，任意の位置にある要素へ O(1)O(1) の計算量で高速にランダムアクセスできる。
エ
ポインタを書き換えることによって，要素の挿入や削除を他の要素の移動を伴わずに行うことができる。