二重連結リストと単一連結リストの違いは何ですか？

Question

Accepted Answer

**二重連結リスト**は各ノードに**2つの**ポインタ — `next` *と* `prev` — を持たせるため、**両方向**にトラバーサでき、ノードへの参照を既に持っている場合、O(1)でノードを削除できます（ヘッドから前ノードを探すために歩く必要がありません）。 ## 構造 ```text null <- [10] <-> [20] <-> [30] -> null prev/next links in BOTH directions ``` ## 既知ノードのO(1)削除 ```python class Node: def __init__(self, val): self.val, self.prev, self.next = val, None, None def remove(node): # O(1) — no traversal needed if node.prev: node.prev.next = node.next if node.next: node.next.prev = node.prev ``` *単一*連結リストでは、ノードを削除するにはまずその前ノードを見つける必要があります → **O(n)**。 ## 比較 | 側面 | 単一 | 二重 | |---|---|---| | ノードあたりのポインタ | 1 (next) | 2 (next, prev) | | 後方へのトラバーサ | いいえ | はい | | 既知ノードの削除 | O(n) | **O(1)** | | メモリオーバーヘッド | 低い | 高い | ## いつ使用するか - **二重：** LRUキャッシュ、ブラウザ履歴、アンドゥ/リドゥ、および中間からのO(1)削除が必要な構造。 - **単一：** メモリが限定的で、前方にのみ移動する場合。 ## なぜ重要なのか既知ノードのO(1)スプライスアウトは、二重連結リストを**LRUキャッシュ**のハッシュマップの相棒として機能させる重要な特性です。追加の`prev`ポインタは、双方向移動と定時間削除の柔軟性のためにメモリをトレードします。

側面	単一	二重
ノードあたりのポインタ	1 (next)	2 (next, prev)
後方へのトラバーサ	いいえ	はい
既知ノードの削除	O(n)	O(1)
メモリオーバーヘッド	低い	高い