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

Давайте начнём с изучения структуры нашего врага. Двусвязный список концептуально прост, но именно так он обманывает вас и манипулирует вами. Это тот же связный список, с которым мы неоднократно сталкивались, но ссылки в нём идут в обе стороны. Двойные ссылки — двойное зло.

Так что вместо этого (для большей ясности прячу Some/None):

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

Мы получаем:

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

Благодаря двойным ссылкам, обходить список можно в любом направлении, а также, с помощью курсора можно искать и вперёд, и назад.

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

Вы должно быть заметили, что я умышленно не писала о концах списка. Это потому, что концы — одно из тех мест, где есть действительно обоснованные способы реализации. Нам определённо нужно, чтобы у нас было указателя: один на начало списка, и один — на конец.

Есть два известных способа реализации: «традиционный» и «фиктивный узел».

Традиционный подход — простое расширение способа, который мы использовали для стека — просто хранить указатели на голову и хвост:

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

Он работает, но у его есть обратная сторона — граничные случаи. А теперь в нашем списке два конца, что означает в два раза больше граничных случаев. Легко забыть об одном из них и получить серьёзную ошибку.

Подход с фиктивным узлом пытается сгладить граничные случаи путём добавления в наш список внешнего узла, в котором нет данных, а есть только ссылки на оба конца, что превращает структуру в кольцо:

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

В такой реализации у каждого узла всегда есть действительные указатели на предыдущий и следующий узлы в списке. Даже когда вы удаляете последний элементы из списка, вы просто замыкаете фиктивный узел сам на себя:

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

Есть часть меня, которая находит это решение вполне удовлетворительным и элегантным. К сожалению, у него есть пара практических проблем:

Проблема 1: Дополнительные уровень косвенности и выделение памяти, особенно для пустого списка, который должен включать фиктивный узел. Потенциальные решения включают:

• Не создавать фиктивный узел до тех пор, пока в список не будет вставлен первый элемент: просто и эффективно, но это возвращает некоторые из граничных случаев, от которых мы пытались избавиться, используя фиктивные указатели!
• Использовать статический одиночный фиктивный узел с копированием при записи и с каким-нибудь хитроумным методом, позволяющим совместить проверки Copy-On-Write с обычными проверками. Этот подход мне очень нравится, но мы не станем заниматься в этой книге тёмной магией. Читайте исходный код ThinVec, если хотите познакомиться с подобной странной реализацией.
• Хранить фиктивный узел на стеке — не практично в языке, где не поддерживаются конструкторы перемещения (move constructors) из C++. Я уверена, что можно было бы придумать странное решение с закреплением (pin), но и этого мы делать не будем.

Проблема 2: Какое значение хранить в фиктивном узле? Ладно бы, речь шла о целом числе, но что если в нашем списке хранятся сплошь экземпляры Box? Мы бы не смогли инициализировать такое значение! Потенциальные решения включают:

• Хранить в каждом узле Option<T>: просто и эффективно, в то же время неэкономно и «по ощущениям» неправильно.
• Хранить в каждом узле MaybeUninit<T>. Не только неправильно, но и ужасно.
• По настоящему осторожно и хитроумно, в стиле наследования, сделать так, чтобы фиктивный узел не хранил данных. Тоже заманчиво, но крайне опасно и неправильно. Читайте исходный код BTreeMap если хотите познакомиться с подобной странной реализацией.

Для такого языка, как Rust, проблемы действительно перевешивают удобство, так что мы будем придерживаться традиционного представления. Используем тот же базовый дизайн, что и в случае с небезопасной очередью из предыдущей главы:

#![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, 
}
}

(Теперь, когда мы добрались до двусвязного дека, мы, наконец, заслужили право назвать структуру LinkedList, поскольку речь идёт об истинном связном списке.)

Это ещё не совсем представление настоящего продуктового уровня. Оно неплохое, но есть волшебные приёмы, которые помогают лучше объяснить Rust, что мы хотим сделать. Для этого нам придётся двигаться... глубже.