Rustで双方向連結リストが欲しいと思ったときは、意外と簡単に実装できる代替品が使えるかも？という記事です。
Rustでの連結リスト実装に関しては、何よりもまずIntroduction - Learning Rust With Entirely Too Many Linked Listsという有名な文献があります。この最初のページに、「Linked Listが本当に必要な場面は思ったよりかなり限られているので、まずはVecかVecDequeあたりの使用を検討しろ」ということが書いてあります。
ただそれでも連結リストが必要なときというのはあります。筆者はソフトウェアNAT（こちらの記事で詳しく解説しています）でIPアドレス・ポートのマッピングをタイムアウトの順に並べて管理するために連結リストが欲しくなったのですが、ここではもう少し単純な問題を考えてみましょう。
以下のような状況をプログラムで表現するとします。
- （uniqueな）名字を持った人間たちが、1列で順番待ちをしている。基本的には、最初に来た人が最初に通されるが、ときどき「高橋さんを先に通して」とか「田中さんを佐藤さんの一つ後ろに移動させて」のような命令が来る
先頭・末尾における要素の追加・削除はVecDequeでもO(1)でできますが、この例では途中での追加・削除があり、しかもその操作が名前で指定されます。名前で指定されるということは定数時間でのルックアップのためにHashMapを使いたくなりますが、HashMapの値として何を使うか？という問題が生じます。VecDequeのインデックスをそのまま使用すると、人の位置が時間により変動するのを捕捉できなくなります。計算量うんぬん以前に、要素へのポインタを保持しておくにはVecDequeは使えません。（多分。そこまで自信はないです）
そこで連結リストが欲しくなります。連結リストがあれば、ノードへのポインタをHashMapの値として持っておくことで、名前を指定されたときにその人がどの場所にいて前後に誰が並んでいるかまでわかるため、O(1)で削除・挿入を行うことができます。
しかし一方で、Rustには厳格な所有権システムがあるため、双方向連結リストのように循環するポインタを含むようなデータ構造を表現するのはかなり面倒です。
もちろんunsafeな生ポインタを使えばCと同じように実装でき、バグを埋め込みにくい自明なデータ構造であることとパフォーマンスも考えればこれも悪くない選択肢ではあるのですが、ここではsafeなやり方を考えてみます。その場合は、書き換え・共有が可能なスマートポインタであるRc<Refcell<T>>を使って実装することになると思います（Rustスマートポインタ比較表 #Rust - Qiitaが参考になります）。また、Debug表示の際などに循環参照が発生するのを防ぐため、双方向連結リストの場合はどちらか一方（典型的には一つ前のエントリを指すポインタ）をRc（強参照）ではなくWeak（弱参照）にする場合が多いです。具体的な実装についてはSimple doubly-linked list in safe Rust · GitHubや『みんなのデータ構造』を読んで Rust で実装した #Rust - Qiitaを参照してください。また、Rustの標準ライブラリにも連結リストは一応あります（LinkedList in std::collections - Rust）が、途中の要素へのポインタを保持するために使えそうなcursor系の関数がNightlyのみで利用可能となっており、このあたりを見る限り使い勝手もあまりよくないようです。
そして、いずれにしても、メモリが分散して使用効率が悪いというリンクリストのよく知られた欠点が解決できません。
ここで少し考えてみると、普通の配列（Vec）を使って双方向連結リストっぽいものを作ることもできそうな気がします。つまり、配列のインデックスをポインタのように使用することで前後の要素をたどることができるということです。しかし単純に新規挿入のたびにインデックスを1つずつ増やすという実装にすると、インデックスが際限なく増えていってしまい、かつ小さいインデックスのところはすでに削除された要素が大量にあり、メモリを無駄遣いしてしまいます。
これを防ぐために、未使用のできるだけ小さいインデックスを使用するというような実装にすることが考えられます。こちらでキーを事前に指定するのではなく、挿入時に勝手に適切な場所を選んでキーを決めてもらうということです。
これをやってくれるのがslotmapやslabといったcrateです。slotmapに関しては公式リポジトリに実装例があるのですが先頭・末尾の削除の実装が間違っています（報告済み）。自分のソフトウェアNATでの実装ではいくつかの関数を追加しているのでこちらもご覧ください。slabを使った実装例はGitHub - GallagherCommaJack/linked-slab: A doubly-linked list backed by a slabにあります。ほぼ同じ内容なのは見てわかると思います。
slotmapとslabの機能的な違いとしては、slotmapはキーのバージョン管理に対応しているというのがあります。すなわち、(index, version)という組がキーになっています。これによって、キーが指している要素が一旦削除されたあとそこに別の要素が追加されたとしても、古いキーが（indexの一致する）新しい要素を誤って指してしまうことなく、無効と判定されるということです。
これはゲームのように複数の場所から1つのオブジェクトが参照されたりオブジェクトがいつ勝手に消えるかわからなかったりする状況で特に有用なようで、実際にgenerational-arenaといった名前でslotmapと同等の機能を提供しているcrate（ただしこれは開発停止している？）もあります。この文脈での解説記事としては[Rust] ゲーム向け世代型Idアリーナによる最適化 #Rust - Qiitaが詳しく、こちらもおすすめです。
連結リストでは追加・削除を厳密に追跡できるのでslabで十分です。
他にもstable-vecなど様々なcrateがあるようで、ベンチマークがBenchmarking slotmap, slab, stable_vec etc.にあります。
注意点として、タイトルにもある通り、こうして実装できるのは厳密には双方向連結リストではありません。具体的に何ができないかというと、リストの分割あるいはリスト同士の結合をO(1)で普通に行うことができません。slotmapやslabはあくまで1つの配列がベースになっているからです。
しかし、先ほど述べた待ち行列の管理のように、連結リストそれ自体は1つあればよくて分割も結合もしないという場合や、同じ配列上に複数の連結リストが共存しても問題ないという場合は、slotmapやslabはシンプルな連結リストの代替品となり得ます。
正直Rustにもデータ構造にもそこまで詳しくないので間違っているかもしれませんが、以上になります。お役に立てば幸いです。
