問題

問６　配列と比較した場合の連結リストの特徴に関する記述として，適切なものはどれか。

ア　要素を更新する場合，ポインタを順番にたどるだけなので，処理時間は短い。
イ　要素を削除する場合，削除した要素から後ろにあるすべての要素を前に移動するので，処理時間は長い。
ウ　要素を参照する場合，ランダムにアクセスできるので，処理時間は短い。
エ　要素を挿入する場合，数個のポインタを書き換えるだけなので，処理時間は短い。

テクノロジ系>基礎理論>アルゴリズムとプログラミング>データ構造

解説と解答

　配列は，最初から何番目かを表すインデックスがあり，それを利用してアクセスします。インデックスを利用すると，何番目でも瞬時にアクセスできます。

　連結リストは，要素を格納するときに次を示すポインタも一緒に格納します。途中の要素にアクセスするときは，最初から順にたどる必要があります。また，連結リストの利点として，途中にデータを挿入することが容易なことが挙げられます。

　それぞれの選択肢を検討してみましょう。

　インデックスでアクセスする配列の方が更新処理は高速です。そのため選択肢アは間違いです。

　連結リストの場合，削除した要素へのポインタの値を，その次の要素に変更するだけで削除となります。要素の移動は必要ありません。このため選択肢イは間違いです。

　連結リストは，先頭から順にポインタをたどりながらアクセスする必要があるため，ランダムアクセスができません。このため選択肢ウは間違いです。

　以上より正解は，選択肢エです。

佐塚 彰夫（さづか あきお）
アイティ・アシスト 代表取締役
ITに関するコンサルティングや教育を実施するアイティ・アシストの代表。新人研修やプロジェクトマネージャ育成研修をはじめ，基本情報技術者試験，応用情報技術者試験，プロジェクトマネージャ試験などの試験対策研修の実績も豊富。著書に「短期完全マスター 基本情報技術者 2009年版」などがある。