単方向リンクリストとは何か、どのような場合に使用しますか？

Question

Accepted Answer

**単方向リンクリスト**は**ノード**の鎖であり、各ノードは値と次の**ノードへのポインタを保持しています。配列とは異なり、ノードは連続していません — メモリ内のどこにでも存在でき、参照によって接続されています。

## 構造

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## 例

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## 計算量

| 操作 | 時間 |
|---|---|
| 先頭での挿入/削除 | O(1) |
| インデックスでのアクセス | O(n) |
| 検索 | O(n) |

## トレードオフ

- **強み:** 先頭での O(1) 挿入/削除; 再割り当てなしで成長; 無駄な容量なし。
- **弱み:** ランダムアクセスなし; すべてのノードはポインタオーバーヘッドを持つ; キャッシュ局所性が悪い（メモリが分散）。

## なぜ重要なのか

リンクリストは、末端で頻繁に追加または削除を行い、中間へのインデックスアクセスがほとんどない場合に活躍します — たとえば、スタック、キュー、隣接リストの基盤として。

ここでのポインタ操作の理解は、木、グラフ、および多くの面接問題の基礎となります。

操作	時間
先頭での挿入/削除	O(1)
インデックスでのアクセス	O(n)
検索	O(n)