Представление данных

Ключевой элемент нашей архитектуры — это тип RefCell. А сердцем RefCell являются пара методов:

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, мы можем сделать из Rust... невероятно многословный, полностью изменяемый язык со сборкой мусора, который не умеет собирать циклические ссылки! О-фи-геть!

Ладно-ладно, мы всего лишь хотим реализовать двусвязный список. Это значит, что в каждом узле хранится указатель на следующий и предыдущий узел. Кроме того, у самого списка есть указатели на первый и последний узел. Это позволяет нам быстро вставлять и удалять узлы на обоих концах списка.

Так что, кажется, нам нужно что-то такое:

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>,
   |     ^^^^^^^^^^^^^

Ого, код собрался! Много предупреждений о неиспользуемых переменных, но код собрался! Давайте попробуем его использовать.