連結リスト とは？

配列はデータがメモリ上に連続して並んでいる。連結リストは各データが「次のデータがある場所」を記録していて、メモリ上でバラバラに置かれていても繋がっているんだ。電車の各車両が「次の車両はこっち」という連結器で繋がっているイメージだよ。

途中への挿入や削除が多い場面だよ。配列の途中に要素を追加すると、後ろの要素を全部ずらさないといけない。でも連結リストは「前のノードのポインタ先を変える」だけで挿入できる。ただし「3番目の要素を取得して」という場面は先頭から順番に辿らないといけないから遅い。

多くの言語のキューやスタックの内部実装に使われているよ。Pythonのdeque（両端キュー）も連結リスト的な仕組みだし、Javaのリンクドリストクラスもある。直接自分で連結リストを書く機会は少ないけど、データ構造の考え方の基礎として理解しておくと応用が利くよ。

通常の連結リスト（単方向）は各ノードが「次」へのポインタだけ持つけど、双方向は「前」へのポインタも持つ。後ろから前にも辿れるから、末尾からの削除がO(1)でできる。Javaの LinkedList やPythonの collections.deque は内部で双方向連結リストを使っているよ。

ポインタ操作の理解を試すのに最適だからだよ。「連結リストの逆転」「サイクル検出（フロイドのウサギとカメ）」「2つの連結リストの合流点」は定番問題。これらが解ければポインタ・再帰・二重ポインタの基本が身についている証拠。実務で連結リストを自作する機会は少ないけど、データ構造の理解度を測る良い指標として面接で重宝されるんだ。