基本情報技術者 一問一答｜A 第61問

解説

連結リストは、各要素（ノード）がデータと次の要素へのポインタを持ち、要素同士をポインタでつないだデータ構造である。挿入・削除はポインタの付け替えだけで済むため、対象位置が分かっていればO(1)と高速であり、要素の移動（詰め直し）が不要な点が配列に対する利点である。一方、目的の要素へは先頭からポインタを順にたどる必要があるため、添字による直接参照（ランダムアクセス）はできず、探索にはO(n)かかる。メモリの連続確保とランダムアクセスは配列の特徴であり、検索が配列より速いという記述も誤り（整列済み配列なら二分探索が使える）である。基本情報技術者試験では配列との比較（挿入・削除はリストが有利、参照は配列が有利）が最頻出ポイントである。