単方向連結リスト：構造、操作、走査

単方向連結リストの基礎

単方向連結リストは各要素（ノード）がデータと次のノードへのポインタを含む線形データ構造です。配列とは異なり、連結リストの要素は連続したメモリに格納されません。

ノード構造

class Node:
    data: any
    next: Node | null

各ノードは値と次のノードへの参照（next）を保持します。最後のノードのnextポインタはnullで、リストの終わりを示します。

コア操作

先頭への挿入 — O(1)：

newNode.next = head
head = newNode

末尾への挿入 — O(n)： 最後のノードまで走査し、lastNode.next = newNodeを設定。tailポインタがあればO(1)になります。

ノードの削除 — O(n)： 対象の前のノードを見つけ、prev.next = target.nextを設定。先頭の削除はO(1)。

検索 — O(n)： headから走査し、各ノードのデータを比較して見つかるかnullに到達するまで。

配列に対する利点

• 動的サイズ：事前にサイズを宣言する必要なし。必要に応じて成長・縮小。
• 効率的な挿入/削除：先頭での挿入・削除はO(1)。要素のシフト不要。
• 無駄なスペースなし：各ノードは必要なメモリのみを使用（ポインタオーバーヘッドを除く）。

欠点

• ランダムアクセス不可：n番目の要素へのアクセスにn個のノード走査が必要 — 配列のO(1)に対してO(n)。
• 追加メモリ：各ノードがデータに加えてポインタを格納。
• キャッシュ性能が悪い：ノードがメモリ上に散在し、走査時にキャッシュミスが発生。