基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

連結リストは、値の後ろに次の要素のデータ位置を示すポインタを付けデータを連結していくデータ構造です。配列との比較ですが、配列ではポインタをたどっていく必要がないためデータの更新や参照は高速です。しかし配列への要素の挿入・削除の際には、位置が変化することになる対象要素すべてを移動しなければなりませんので、数個の要素のポインタを付け替えるだけでできる連結リストのほうが高速に処理できます。

• 更新対象の要素までポインタをたどっていく分、リスト構造の更新処理は配列より遅くなります。
• 要素の削除時はポインタの付け替えで順番を変更できるリスト構造のほうが高速です。
• 連結リストはデータにランダムにアクセスできず、目的のデータを参照するためには先頭（双方向リストでは末尾も可）から順番にポインタをたどっていく必要があります。
• 正しい。要素の挿入をする際は、挿入する要素のポインタを正しくセットして、前の要素のポインタを挿入する要素に向けるだけなので、全体を移動しなければならない配列と比較して高速です。