Если вы изучали Rust, возможно, вы по неизвестной причине пытались реализовать связанный список с ним. Вы думали, это будет хорошая идея? Я, конечно, сделал. И, как и многие другие храбрые души, у вас еще больше шансов, что вы проиграете. Не волнуйтесь.
В этом коротком посте мы попытаемся создать разумный связанный список в Rust, но без использования каких-либо небезопасных вещей, и мы постараемся реализовать несколько функций и протестировать их. Так что вперед.
Давайте создадим новый проект с
$cargo new linky_lists
Перейдите к нашему linky_lists и создайте новую папку src / lists.
Создайте новый mod.rs файл в src / lists и в нашей main.rs над функцией main() напишите mod lists;. Внутри папки lists мы также создадим node.rs, где мы создадим структуру с одним узлом.
Мы используем ключевое слово type для объявления псевдонимов для других типов, в основном мы ленивы писать Rc<RefCell<Node>> все время, поэтому мы создаем из него новые типы, в нашем случае это NodeRef & NodeOption.
Но что такое Rc<RefCell<Node>>? Итак, свойство next нашего узла должно быть другим узлом, но в Rust мы не можем просто написать next: Node, потому что тогда исходный узел будет иметь размер всего списка, потому что он будет указывать на другой узел, а другой узел укажет на другой узел ...
Чтобы предотвратить это, мы используем интеллектуальные указатели Rust, такие как Box или Rc, и оборачиваем следующий узел внутри него, поэтому каждый узел будет иметь фиксированный размер, содержащий, в нашем случае, строковые данные и указатель на другой узел, таким образом компилятор будем счастливы, а значит и мы счастливы :)
Поэтому мы решили использовать Rc, потому что он предоставляет нам суперсилу совместного владения, он обозначает подсчитанные ссылки, поэтому он делает именно это, он подсчитывает, сколько ссылок указывает на определенное значение в куче.
И до тех пор, пока поскольку этот count не равен 0, это значение останется в живых, как только count станет 0, это значение исчезнет навсегда, если это звучит знакомо, да, это наш собственный мини-сборщик мусора. Мы создаем новые указатели, просто клонируя существующую ссылку на значение, поэтому создается только новый указатель, а само значение не копируется, мы делаем это с помощью clone(), который вы вскоре увидите в действии.
Хорошо, тогда что это за RefCell, ну, Rc сам по себе ничего не может сделать, кроме создания новых указателей, RefCell позволяет использовать внутреннюю изменчивость.
Обычно в ржавчине у нас может быть только одна изменяемая ссылка на объект,
, и это принудительно выполняется компилятором, но с помощью RefCell мы говорим компилятору
отступить немного и пусть среда выполнения выполнит эти проверки. Это используется, когда у нас есть несколько ссылок на объект и мы хотим его изменить, идеальным примером является связанный список!
Просто представьте, что Rc и RefCell работают вместе как одно целое, чтобы предоставить нам возможность заимствовать значение из Node, изменять его и иметь несколько указателей на одну и ту же структуру Node.
Я реализовал несколько черт PartialEq и Debug только для удобства сравнения и регистрации нашего узла с помощью макроса derive. Также я реализовал ведение журнала, когда наш узел удаляется, реализовав трейт Drop, это просто для того, чтобы мы видели в нашей консоли, когда определенный узел удаляется из наших связанных списков.
Напишите mod node; в lists/mod.rsrun $ cargo test, и наш единственный тест должен пройти, теперь мы напишем большую часть нашего кода в src/lists/mod.rs, где мы будем реализовывать наш связанный список.
Здесь все должно быть довольно просто, давайте теперь реализуем append_end и append_start.. А затем давайте добавим несколько итераторов, чтобы мы могли перебирать наши узлы и печатать строковые значения.
Мы используем метод take() Options, чтобы извлечь значение из self.head и заменить его на None. Если head уже существует, мы меняем свойство new_head next, чтобы оно указывало на предыдущий заголовок. Мы делаем это, используя borrow_mut RefCell, чтобы заимствовать Node, заключенный в new_head, и обновлять его свойство next. Мы также используем Rc::clone(&old_head)) для создания нового указателя на old_head, чтобы мы могли указывать на него. Мы могли бы просто написать old_head.clone(), но это может сбивать с толку, потому что может показаться, что мы клонируем сам узел, а это не так, а только ссылку, указывающую на него.
Я также предоставил несколько тестов, которые вы можете проверить в репо, которые будут связаны в конце.
Теперь напишем итератор.
Я написал ListNodeIterator внутри node.rs файла, рядом с нашей структурой Node. В основном мы собираемся использовать этот ListNodeIterator для итерации по списку, функция next () выполняет всю логику, она возвращает единственный NodeOption один за другим, поэтому каждый раз, когда мы вызываем next (), мы будем получать следующий элемент NodeOption, для получения дополнительной информации о том, как реализовать итераторы, проверьте документацию Rust, сам код нет ничего, что вы еще не видели.
Затем мы добавляем одну частную и одну общедоступную функцию в наш LinkedList.
iter_node () - это функция, которая будет создавать и возвращать итератор по нашему списку, а print_items () будет перебирать итератор и печатать свойство .data наших узлов.
В конце давайте реализуем pop_end и pop_head, чтобы мы могли получать данные из списка и удалять узлы как в начале, так и в конце.
Здесь мы используем другую полезную функцию Option, которая отображает результат take () на другой Option, в данном случае Option ‹String›, поскольку мы берем значение из head / tail и clone () как возвращаемое значение. Конечно, здесь реализован метод pop_end () медленнее, потому что он должен перебирать всю строку, поэтому я рекомендую всегда выталкивать голову.
Вот и все, полный код можно найти в этом репо.
Спасибо за прочтение!
