連結リストとは (定義、ノード構造、ポインタ)

**連結リストとは (定義、ノード構造、ポインタ)**は、値と次ノードへの参照を持つノードを連鎖させた線形データ構造である。

仕組み

先頭参照からnextを順にたどる。既知ノードの直後への挿入は参照を付け替えるだけで、要素移動を伴わない。

計算量・性質

既知位置での挿入・削除はO(1)だが、位置探索とランダムアクセスはO(n)。

具体例

A→CでAのnextをB、BのnextをCにすればBを挿入できる。

限界と注意点

ポインタ領域と低いキャッシュ局所性が必要で、末尾操作はtail保持の有無で変わる。