69. (アイデアメモ) ランダムアクセスが O(1) で可能な双方向リスト

今日はアイデアのメモ書きです。

双方向リストは追加・削除が で可能なデータ構造です。しかし、ある要素が含まれているかを探そうとすると の計算量になります。

ただ、ちょっと工夫すればこれも に落とせそうな上、（若干扱えるデータの範囲は狭くなりますが）双方向リストの気持ち悪い部分である「Nodeがむき出し」問題を解決できそうだなぁ、と思いました。

C# で探してみたのですが標準で無さそうだったので、LinkedListDictionary という名前で実装しようと考えています。

名前の通り Key でアクセス可能な双方向リストで、つまりキーの重複するデータは保持できません。ここが通常の双方向リストに比べてデメリットとなる箇所です。

キーとNodeのマップをデータ構造内に保持することで、 でのランダムアクセスが可能になります。また、Nodeを完全に隠蔽できて利用者側から扱いやすくなります。