linked list

linked listは、データ要素がメモリ上の連続した領域に配置されるのではなく、各要素が次の要素への参照（ポインタ）を持つことで鎖のように繋がっている構造を指します。このため、データの挿入や削除を行う際に、他の要素をずらす必要がなく、非常に効率的に操作できるという特徴があります。

配列との決定的な違い

一般的な配列（array）はメモリ上に連続して配置されるため、インデックスを指定して特定の要素に即座にアクセスすることが可能です。一方でlinked listは、先頭から順番に辿らなければ目的の要素に到達できないため、ランダムアクセスには不向きです。しかし、動的にサイズを変更しやすく、メモリの断片化を有効に活用できるため、柔軟なデータ管理が必要な場面で重宝されます。

実装上のバリエーション

linked listには、用途に応じていくつかの形態が存在します。

単方向連結リスト：各ノードが次のノードへのポインタのみを持つ形式です。
双方向連結リスト：各ノードが前後の両方のノードへのポインタを持つため、逆方向への移動が可能です。
環状連結リスト：最後のノードが先頭のノードを指し示すことで、リストが円状に繋がっている形式です。