連結リストとは？

詳細解説

連結リスト（Linked List）は、各要素（ノード）が「データ」と「次のノードへのポインタ（参照）」を持ち、ポインタを通じて要素を鎖状に連結したデータ構造です。配列と異なりメモリ上で連続した領域は不要で、各ノードは散在した領域に配置できます。主な種類：単方向連結リスト（各ノードが次のノードのみを指す）、双方向連結リスト（前後両方向のポインタを持つ）、循環リスト（末尾が先頭を指す）。操作の計算量は、先頭への挿入・削除O(1)、特定位置（n番目）の要素へのアクセスO(n)（先頭からポインタを順番に辿る必要あり）です。配列との比較：配列はランダムアクセスO(1)・挿入削除O(n)、連結リストはランダムアクセスO(n)・先頭挿入削除O(1)というトレードオフがあります。FE試験では「連結リストのノードへのポインタの挿入・削除操作のトレース（ポインタの付け替え手順）」が典型問題です。双方向リストの中間ノード削除（前後のポインタを正しく付け替える手順）も出題されます。

FE試験での出題ポイント

• 1先頭挿入・削除O(1)：配列（O(n)）と逆のトレードオフ
• 2ランダムアクセスO(n)：先頭から順番にポインタを辿る
• 3挿入・削除時のポインタ付け替え手順のトレース（FE科目B頻出）
• 4単方向・双方向・循環リストの3種類と各特徴

関連用語