Связный однонаправленный список в Rust. Как вернуть последний элемент?
Я, например, не смог.
Даже с умным указателем, который считает ссылки.
use std::rc::Rc;
use std::cell::RefCell;
use std::fmt::Debug;
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
type Value<T> = Option<Box<T>>;
#[derive(Debug)]
struct Node<T> {
value: Value<T>,
next: Link<T>
}
#[derive(Debug)]
struct LinkedList<T: Debug> {
head: Link<T>,
}
impl<T: Debug> LinkedList<T> {
fn new() -> Self {
LinkedList {
head: None
}
}
// Добавление элемента в начало списка
fn push_front(&mut self, value: T) {
let new_node = Rc::new(RefCell::new(Node {
value: Some(Box::new(value)), // Упаковываем значение в Box
next: self.head.take(),
}));
self.head = Some(new_node);
}
// Добавление элемента в конец списка
fn pop_front(&mut self) -> Option<T> {
match self.head.take() { // Берём голову списка
Some(head) => {
let mut head_borrowed = head.borrow_mut(); // Получаем изменяемую ссылку на голову
self.head = head_borrowed.next.take(); // Устанавливаем новую голову как следующий узел
// Возвращаем значение, разыменовывая Box<T>
head_borrowed.value.take().map(|boxed_value| *boxed_value)
}
None => None, // Если список пуст, возвращаем None
}
}
fn push_back(&mut self, value: T) {
let new_node = Rc::new(RefCell::new(Node {
value: Some(Box::new(value)), // Упаковываем значение в Box
next: None,
}));
match &self.head {
Some(head) => {
// Копируем ссылку на голову списка
let mut current = Rc::clone(head);
loop {
// Получ;аем следующую ссылку без заимствования на долгое время
let next = current.borrow().next.clone();
match next {
Some(next_node) => {
// Переходим к следующему узлу
current = next_node;
}
// Если это последний элемент, устанавливаем новый узел как следующий
None => {
current.borrow_mut().next = Some(new_node);
break;
}
}
}
}
None => {
// Если список пуст, новый узел становится головой
self.head = Some(new_node);
}
}
}
fn pop_back(&mut self) -> Option<T> {
// Если список пуст
if self.head.is_none() {
return None; // Возвращаем None
}
// Если в списке только один элемент
if self.head.as_ref()?.borrow().next.is_none() {
return self.pop_front(); // Удаляем голову и возвращаем её значение
}
let mut current = self.head.clone().unwrap(); // Ссылка на голову
let mut prev: Option<Rc<RefCell<Node<T>>>> = None; // Предыдущий узел
// Проходим по списку до последнего узла
while let Some(next) = current.borrow().next.clone() {
prev = Some(current.clone()); // Сохраняем текущий узел как предыдущий
current = next; // Переходим к следующему узлу
}
// Удаляем последний узел, обновляя ссылку предыдущего узла
if let Some(prev_node) = prev {
prev_node.borrow_mut().next = None; // Устанавливаем следующий узел как None
}
// Возвращаем значение последнего узла, разыменовывая Box
current.borrow_mut().value.take().map(|boxed_value| *boxed_value)
}
// Вывод значений всех элементов списка (для демонстрации)
fn print(&self)
where
T: Debug,
{
let mut current = self.head.clone();
while let Some(node) = current {
let node_ref = node.borrow();
println!("{:?}", node_ref.value);
current = node_ref.next.clone();
}
}
}
fn main() {
let mut list = LinkedList::new();
// Добавление элементов в список
list.push_front(1);
list.push_front(2);
list.push_front(3);
println!("Список после добавления в начало:");
list.print();
// Добавление в конец списка
list.push_back(4);
list.push_back(5);
println!("Список после добавления в конец:");
list.print();
//list.insert(12, 2); // Значение и позиция в списке
// Удаление элемента из начала списка
if let Some(value) = list.pop_front() {
println!("Удалено из начала: {}", value);
}
println!("Список после удаления из начала:");
list.print();
// Удаление элемента с конца списка
if let Some(value) = list.pop_back() {
println!("Удалено с конца: {}", value);
}
println!("Список после удаления с конца:");
list.print();
}