連結リスト とは？

配列のように番号から直接要素へアクセスする代わりに、先頭などから次の参照をたどるよ。ノードはメモリ上で連続している必要がない。ただし参照を保存する領域が増え、順にたどる処理も必要なので、配列よりいつも速いわけではないんだ。

挿入場所の直前のノードが分かっているなら、新しいノードのnextを後ろへ向け、直前のnextを新ノードへ向ける、といった付け替えで挿入できる。場所を探す時間は別で、番号で指定すると最悪O(n)かかる。削除でも必要な参照を用意するんだ。

単方向でも末尾への参照を持てば、末尾追加の付け替えはO(1)だよ。でも末尾削除は、その直前を探すために先頭からたどる場合がある。双方向で末尾への参照もあれば、前をすぐ取得して削除できる。どの参照を持つ実装かが大切だね。

スタックやキューを作る方法の一つだよ。JavaのLinkedListは双方向連結リストで、番号でアクセスすると近い側の端からたどる。CPython 3.13のcollections.dequeは、要素ごとのノードではなく固定長ブロックを双方向につなぐ実装。教科書の単純なリストと同一とはしないんだ。

次だけでなく前のノードへの参照も持つので、逆向きにもたどれるよ。挿入や削除では両側の参照を正しく更新する必要がある。ノードが分かれば速く付け替えられるけれど、番号指定で探す時間は残る。単方向より参照の保存や更新も増えるんだ。