70. ランダムアクセスが O(1) で可能な双方向リスト

双方向リストは、片方向リストと比較して「前後両方のノードへのポインタを持つ」という点が特徴です。C# では LinkedList として実装されています。

f:id:ibako_piyo:20220219131815p:plain — 双方向リスト

双方向リストは、以下のような特徴を持ちます。

先頭・末尾への要素追加が $O(1)$ で可能
(そのノードが分かっていれば)ノードの前後への要素追加が $O(1)$ で可能
(そのノードが分かっていれば)ノードの削除が $O(1)$ で可能
要素の探索が $O(N)$ で可能

片方向リストと比較して、任意ノード前後への要素追加や、任意ノード削除が高速なのが特徴です。ただし、リスト自体は最初と最後へのポインタしか持っていないため、要素の探索自体は線形時間になります。つまり、定数時間で追加・削除を行うには、対象ノードを知っている必要があります。これは、API として本来隠蔽すべきノードというデータ構造がむき出しになるということです。

ただし、制約を設けることで要素の探索を $O(1)$ で行うことが可能になります。それは、「リスト内に同一（キーを持つ）データが存在しない」という制約です。

これによって、双方向リスト内に「データ値を Key、ノードへのポインタを Value とする Dictionary」を作成することで、全要素へのアクセスを $O(1)$ で行うことが可能になります。