Ссылки в реализации связного списка

Question

Я пытаюсь решить задачу Simple Linked List Exercism, но я застрял при реализации метода pop().Ошибки, которые я получаю, мне не очень понятны;Думаю, я не совсем привык к образу мышления Руста.

Кроме того, из-за предложений компилятора я добавил группу as_ref(), которую я на самом деле не понимаю.

Мне интересно знать, почему мой способ ведения дел не помогаетработать больше, чем решение.

pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
}

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self {
        unimplemented!()
    }

    pub fn len(&self) -> usize {
        unimplemented!()
    }

    pub fn push(&mut self, _element: T) {
        unimplemented!()
    }

    pub fn pop(&mut self) -> Option<T> {
        // Recursive function to return the before last element of the list
        fn get_before_last<'a, T>(
            prev: &'a Box<Node<T>>,
            current: &'a Box<Node<T>>,
        ) -> &'a Box<Node<T>> {
            match &current.next {
                Some(next_node) => get_before_last(&current, &next_node),
                None => &prev,
            }
        }

        // Check if the head is None
        match &self.head {
            None => return None,
            _ => (),
        };

        let before_last = &mut match &self.head {
            // Beginning of the recursion
            Some(node) => get_before_last(&node, node.next.as_ref().unwrap()),
            None => self.head.as_ref().unwrap(),
        };

        let to_pop = before_last.next.as_ref();
        before_last.next = None;

        Some(to_pop.unwrap().data)
    }
}

Я получаю следующие ошибки:

error[E0594]: cannot assign to `before_last.next` which is behind a `&` reference
  --> src/lib.rs:48:9
   |
48 |         before_last.next = None;
   |         ^^^^^^^^^^^^^^^^ cannot assign

error[E0507]: cannot move out of borrowed content
  --> src/lib.rs:50:14
   |
50 |         Some(to_pop.unwrap().data)
   |              ^^^^^^^^^^^^^^^^^^^^ cannot move out of borrowed content

Answer 1

В вашем коде before_last не является изменяемым.На самом деле это &mut &'a Box<Node>.По этой причине вы не можете ничего присвоить узлу, потому что это изменяемая ссылка на неизменяемую.

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

Таким образом, у вас есть список LIFO, и вам не нужно просматривать весь список, чтобы нажимать и выталкивать, так что это также более эффективно.Нажатие на переднюю часть также уменьшает количество требуемого кода.

Мое решение доступно на Exercism .