レイアウト

まずは敵の構造を研究するところから始めましょう。Doubly-Linked List は概念的には単純ですが、まさにそこがあなたを欺き、操るところです。これは、これまで何度も見てきたのと同じ種類の連結リストですが、リンクが両方向に伸びています。リンクが 2 倍なら、邪悪さも 2 倍です。

つまり、これではなく（見やすくするために Some/None 周りは外します）:

... -> (A, ptr) -> (B, ptr) -> ...

こうなります:

... <-> (ptr, A, ptr) <-> (ptr, B, ptr) <-> ...

これにより、リストをどちらの方向からでも走査したり、カーソルで前後に移動したりできます。

この柔軟性と引き換えに、各ノードは 2 倍の数のポインタを格納しなければならず、各操作ははるかに多くのポインタを修正しなければなりません。これはかなり大きな複雑化であり、ミスを起こしやすくなるため、かなり多くのテストを行うことになります。

また、私が意図的にリストの端を描いていないことにも気づいたかもしれません。これは、ここが実装に関して本当に擁護可能な選択肢が存在する場所の 1 つだからです。私たちの実装には 2 つのポインタが絶対に必要です。1 つはリストの先頭へのポインタ、もう 1 つはリストの末尾へのポインタです。

私の考えでは、これを行う主な方法は 2 つあります。「従来型」と「ダミーノード」です。

従来型のアプローチは、Stack で行った方法の単純な拡張です — head ポインタと tail ポインタをスタック上に格納するだけです:

[ptr, ptr] <-> (ptr, A, ptr) <-> (ptr, B, ptr)
  ^                                        ^
  +----------------------------------------+

これは問題ありませんが、1 つ欠点があります。それはコーナーケースです。リストには端が 2 つあるため、コーナーケースも 2 倍になります。片方を忘れて深刻なバグを抱え込むのは簡単です。

ダミーノードのアプローチは、データを含まない余分なノードをリストに追加し、両端をリング状につなげることで、これらのコーナーケースをならそうとします:

[ptr] -> (ptr, ?DUMMY?, ptr) <-> (ptr, A, ptr) <-> (ptr, B, ptr)
           ^                                                 ^
           +-------------------------------------------------+ 

こうすることで、すべてのノードはリスト内の前後のノードへの実際のポインタを常に持つことになります。リストから最後の要素を削除した場合でさえ、最終的にはダミーノードが自分自身を指すようにつなぎ直すだけです:

[ptr] -> (ptr, ?DUMMY?, ptr) 
           ^             ^
           +-------------+

私の中には、これを非常に満足感がありエレガントだと感じる部分があります。残念ながら、これには実用上の問題がいくつかあります:

問題 1: 特に空のリストにおいて、余分な間接参照とアロケーションが発生します。空のリストにもダミーノードを含めなければならないためです。考えられる解決策には次のものがあります:

• 何かが挿入されるまでダミーノードをアロケートしない: 単純で効果的ですが、ダミーポインタを使うことで避けようとしていたコーナーケースの一部が戻ってきてしまいます！

• 静的な copy-on-write の空シングルトンなダミーノードを使い、Copy-On-Write のチェックを通常のチェックに便乗させる本当に巧妙な仕組みを用意する: 正直かなり惹かれますし、私は本当にそういうクソが大好きなのですが、この本ではその暗い道を進むわけにはいきません。そういう倒錯したものを見たいなら、ThinVec のソースコードを読んでください。

• ダミーノードをスタック上に格納する - C++ 風のムーブコンストラクタがない言語では実用的ではありません。pinning を使えば、ここで何か奇妙なことができるのは確かですが、やりません。

問題 2: ダミーノードにはどんな値を格納するのでしょうか？ 整数ならもちろん問題ありませんが、Box だらけのリストを格納している場合はどうでしょう？ その値を初期化することが不可能かもしれません！ 考えられる解決策には次のものがあります:

• すべてのノードに Option<T> を格納させる: 単純で効果的ですが、同時に肥大化して面倒です。

• すべてのノードに MaybeUninit<T> を格納させる。恐ろしく面倒です。

• ダミーノードがデータフィールドを含まないようにするための、本当に慎重で巧妙な継承風の型偽装。これも魅力的ですが、非常に危険で面倒です。そういう倒錯したものを見たいなら、BTreeMap のソースを読んでください。

Rust のような言語では、問題の方が利便性を大きく上回るため、従来型のレイアウトを使うことにします。前の章の unsafe queue で使ったのと同じ基本設計を使います:

#![allow(unused)]
fn main() {
pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

type Link<T> = *mut Node<T>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}
}

（doubly-linked-deque に到達した今、私たちはついに自分たちを LinkedList と呼ぶ権利を得ました。なぜなら、これこそが真の Linked List だからです。）

これはまだ真の本番品質のレイアウトとは言えません。悪くはありませんが、自分たちが何をしているのかを Rust にもう少しうまく伝えるために使える手品があります。そのためには、もっと……深く潜る必要があります。