定義

双方向連結リストは、各ノードがデータに加えて、前のノードを指すprevと次のノードを指すnextの2つのポインタを持つデータ構造です。 単方向（nextのみ）に進む単方向連結リストと異なり、双方向に走査できます。

主な特性

• ✓双方向ポインタ: 各ノードは[prev | データ | next]で構成され、前後に移動できます。
• ✓逆方向走査: tailからprevをたどって逆順に探索できます。単方向では不可能です。
• ✓O(1)削除: 削除するノードの参照があれば、そのノードのprev/nextで両隣を直接つなぎO(1)で削除できます。
• ✓追加メモリ: ノードごとにprevポインタが余分に必要で、単方向よりやや多くメモリを使います。

時間計算量