レイアウト

この設計の鍵となるのは RefCell 型です。RefCell の中核は、 次の 2 つのメソッドです。

fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;

borrow と borrow_mut のルールは、& と &mut のルールとまったく同じです。 borrow は何度でも呼び出せますが、borrow_mut には 排他性が必要です。

これを静的に強制するのではなく、RefCell は実行時に強制します。 ルールを破ると、RefCell は単に panic してプログラムをクラッシュさせます。 では、なぜこれらの Ref や RefMut というものを返すのでしょうか？ それらは基本的に、 借用版の Rc のように振る舞います。また、スコープから外れるまで RefCell を 借用されたままにします。これについては後で扱います。

これで Rc と RefCell を使って、私たちは……循環参照を回収できない、 信じられないほど冗長で、至るところで可変なガベージコレクション付き言語に なれるわけです！ や、やったぁぁぁ……

さて、私たちは 双方向リンク にしたいと考えています。これは、各ノードが 前のノードと次のノードへのポインタを持つことを意味します。また、リスト自体も 最初のノードと最後のノードへのポインタを持ちます。これにより、リストの 両端 で高速な挿入と削除が可能になります。

つまり、おそらく次のようなものが欲しいはずです。

use std::rc::Rc;
use std::cell::RefCell;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
    prev: Link<T>,
}

> cargo build

warning: field is never used: `head`
 --> src/fourth.rs:5:5
  |
5 |     head: Link<T>,
  |     ^^^^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: field is never used: `tail`
 --> src/fourth.rs:6:5
  |
6 |     tail: Link<T>,
  |     ^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/fourth.rs:12:5
   |
12 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `next`
  --> src/fourth.rs:13:5
   |
13 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

warning: field is never used: `prev`
  --> src/fourth.rs:14:5
   |
14 |     prev: Link<T>,
   |     ^^^^^^^^^^^^^

おお、ビルドできました！ dead code の警告がたくさん出ていますが、ビルドできました！ 使ってみましょう。