連結リスト（リスト構造）とは？

連結リスト（リスト構造）の意味

各データ要素（ノード）が次の要素へのポインタ（参照）を持つことでデータを連結して並べる構造。配列と異なり、要素の挿入・削除の際に他の要素を移動させる必要がない。

連結リスト（リスト構造）の具体例

配列の途中にデータを挿入すると後続の要素をすべて1つずつずらす必要があるが、連結リストならポインタのつなぎ替えだけで済むため、頻繁な挿入・削除がある場合に有利。

連結リスト（リスト構造）は試験でどう引っ掛けられる？

連結リストは特定の位置（n番目）への直接アクセスが苦手（先頭から順にたどる必要がある）で、この点は配列より劣る。

連結リスト（リスト構造）と関連する用語

• スタックとキュー

連結リスト（リスト構造）が出た過去問

• 双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員Gを社員Aと社員Kの間に追加する。追加後の表のポインタa〜fの中で追加前と比べて値が…

  正解：a, f

  要点：双方向リスト挿入で変わるのは前後2本のポインタだけ

  双方向リストの途中に要素を挿入するとき、値が変わるのは挿入位置の前後にある既存要素のポインタだけである。前側の要素では次ポインタが新要素を指すように変わり、後側の要素では前ポインタが新要素を指すように変わる。前側の前ポインタと後側の次ポインタは影響を受けない。したがって変化するのは社員Aの次ポインタと社員Kの前ポインタの二つになる。

  出典：令和5年度 （公開問題） 基本情報技術者試験 kamokuA 問2（IPA）