プログラミング基礎初級
連結リスト
一言で言うと
各要素が次の要素へのポインタを持つ構造。
もう少し詳しく
一言で言うと
各要素が次の要素へのポインタを持つ構造。先頭への挿入・削除はO(1)だが、任意位置への操作は目的ノードへの参照が必要なため探索コストを含めるとO(n)になる。特定位置へのアクセスもO(n)。メモリが連続している必要がない。
もう少し詳しく
各要素が次の要素へのポインタを持つ構造。先頭への挿入・削除はO(1)だが、任意位置への操作は目的ノードへの参照が必要なため探索コストを含めるとO(n)になる。特定位置へのアクセスもO(n)。メモリが連続している必要がない。
連結リストは「ノード」と呼ばれる単位でデータを管理し、各ノードが次のノードへのポインタ（参照）を保持することでデータを連結します。配列と異なりメモリ上で連続した領域を確保する必要がなく、実行時に動的にサイズを変更できる点が大きな利点です。