線形リストの種類

線形リストは、各要素を前後関係で一列に結び、ポインタ又は参照をたどって順序どおりにアクセスするデータ構造です。

■ 試験で押さえるポイント

• 単方向リストは各ノードが次ノードだけを指し、先頭から後方へ走査します。ノード位置が分かれば挿入・削除時の要素移動は不要です。

• 双方向リストは次と前の両方を指し、両方向走査と削除をしやすい一方、参照領域と更新箇所が増えます。

• 循環リストは末尾が先頭へつながり、開始位置に依存せず巡回できます。終了条件を誤ると無限ループになります。

• 配列は添字によるランダムアクセスが$O(1)$ですが、連結リストの指定位置探索は$O(n)$です。用途に応じて選びます。

■ 選択肢での判断ポイント

単方向は次だけ、双方向は前後、循環は末尾から先頭へつながります。連結リストは挿入・削除で要素の一括移動が不要ですが、位置探索は順次です。

例: 再生曲を前後へ移動する一覧は双方向リスト、各利用者へ順番にCPUを割り当てて末尾から先頭へ戻る構造は循環リストで表せます。