双方向連結リスト：双方向ナビゲーションと操作

双方向連結リスト

双方向連結リストは各ノードにprevポインタを追加して単方向連結リストを拡張し、両方向の走査を可能にします。

ノード構造

class Node:
    data: any
    prev: Node | null
    next: Node | null

操作の比較

操作	単方向	双方向
先頭への挿入	O(1)	O(1)
末尾への挿入	O(n)*	O(1)
指定ノードの削除	O(n)**	O(1)
前方走査	O(n)	O(n)
後方走査	N/A	O(n)

削除の利点

双方向連結リストの最大の利点は、ノードへの参照がある場合のO(1)削除です。

センチネルノード

多くの実装ではエッジケースを排除するためにセンチネル（ダミー）ヘッドとテールノードを使用します。センチネルにより、nullヘッドやnullテールのチェックが不要になります。

LRUキャッシュ実装

双方向連結リストの最も有名なアプリケーションはLRU（Least Recently Used）キャッシュです：

1. ハッシュマップがキーによるO(1)ルックアップを提供。
2. 双方向連結リストがアクセス順序を維持。
3. アクセス時：ノードを先頭（最近使用）にO(1)で移動。
4. エビクション時：末尾のノード（最も長く使用されていない）をO(1)で削除。

この組み合わせにより、getとput両方の操作がO(1)となるため、LRUキャッシュは面接で非常に頻繁に問われます。