Что может быть лучше для реализации .pop () в моем единственном связанном списке в Rust?

Question

Я реализовал свою собственную версию односвязного списка в Rust как одну из задач для меня, чтобы изучить его, и я удовлетворен всем, что у меня есть, кроме метода .pop (). Использование 2 циклов while очень уродливо и неэффективно, но я не нашел другого способа преодолеть проблему установки узла с индексом len () - 2 на None (вывод списка) и использование данных из узла с индексом len () - 1 для возвращаемого значения Some (data) (возвращает извлеченный элемент).

GitHub Link

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

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

impl<T> Default for SimpleLinkedList<T> {
    fn default() -> Self {
        SimpleLinkedList { head: None }
    }
}

impl<T: Copy> Clone for SimpleLinkedList<T> {
    fn clone(&self) -> SimpleLinkedList<T> {
        let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
        let mut cur = &self.head;
        while let Some(node) = cur {
            cur = &node.next;
            out.push(node.data)
        }
        out
    }
}

impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self {
        Default::default()
    }

    pub fn len(&self) -> usize {
        let mut c = 0;
        let mut cur = &self.head;
        while let Some(node) = cur {
            cur = &node.next;
            c += 1;
        }
        c
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn push(&mut self, _element: T) {
        let mut cur = &mut self.head;
        match cur {
            Some(_) => {
                while let Some(node) = cur {
                    cur = &mut node.next;
                }
            }
            None => (),
        }
        *cur = Some(Box::from(Node {
            data: _element,
            next: None,
        }));
    }

    pub fn pop(&mut self) -> Option<T>
    where
        T: Copy,
    {
        let length = &self.len();
        let mut cur = &mut self.head;
        let mut out = None;
        match cur {
            Some(_) if *length > 1usize => {
                let mut c = 0usize;
                while let Some(node) = cur {
                    cur = &mut node.next;
                    if c >= length - 1 {
                        out = Some(node.data);
                        break;
                    }
                    c += 1;
                }

                c = 0usize;
                cur = &mut self.head;
                while let Some(node) = cur {
                    cur = &mut node.next;
                    if c == length - 2 {
                        break;
                    }
                    c += 1;
                }
            }
            Some(node) => out = Some(node.data),
            None => (),
        }
        *cur = None;
        out
    }

    pub fn peek(&self) -> Option<&T> {
        let cur = &self.head;
        match cur {
            Some(node) => Some(&node.data),
            None => None,
        }
    }
}

impl<T: Copy> SimpleLinkedList<T> {
    pub fn rev(&self) -> SimpleLinkedList<T> {
        let mut clone = self.clone();
        let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
        while let Some(val) = clone.pop() {
            out.push(val)
        }
        out
    }
}

impl<'a, T: Copy> From<&'a [T]> for SimpleLinkedList<T> {
    fn from(_item: &[T]) -> Self {
        let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
        for &e in _item.iter() {
            out.push(e);
        }
        out
    }
}

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
    fn into(self) -> Vec<T> {
        let mut out: Vec<T> = Vec::new();
        let mut cur = self.head;
        while let Some(node) = cur {
            cur = node.next;
            out.push(node.data)
        }
        out
    }
}

Answer 1

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

Если вы наивны в том, как вы это делаете, у вас будут проблемы;ваш «предыдущий» указатель сохраняет за собой право владения остальной частью списка, а средство проверки заимствования не позволяет этого.Хитрость заключается в том, чтобы разорвать эту ссылку по ходу дела - и для этого вы можете использовать функцию mem::replace.Как только вы это сделаете, вы должны будете вернуть его обратно, прежде чем снова потерять след предыдущего узла.

Вот как это может выглядеть в полной мере (вам придется простить мое либеральное использование unwrap - Я думаю, это проясняет ситуацию):

pub fn pop(&mut self) -> Option<T>
    where T : Copy,
{
    use std::mem::replace;

    let curr = replace(&mut self.head, None);

    if curr.is_none() { // list started off empty; nothing to pop
        return None;
    }

    let mut curr = curr.unwrap(); // safe because of the check above

    if let None = curr.next { // popped the last element
        return Some(curr.data);
    }

    let mut prev_next = &mut self.head;

    while curr.next.is_some() {
        // Take ownership of the next element
        let nnext = replace(&mut curr.next, None).unwrap();

        // Update the previous element's "next" field
        *prev_next = Some(curr);

        // Progress to the next element
        curr = nnext;

        // Progress our pointer to the previous element's "next" field
        prev_next = &mut prev_next.as_mut().unwrap().next;

    }

    return Some(curr.data);
}

В качестве отступления вся эта перестановка указателей сильно упрощается, если вы хотите немного изменить интерфейс, чтобы мы возвращали "новый"составлять список каждый раз (вступая во владение функцией pop) или использовать постоянную структуру данных, как это делается в Learning Rust со слишком большим количеством связанных списков (уже упоминалось в комментарии):

pub fn pop_replace(self) -> (Option<T>, Self) {
    // freely mutate self and all the nodes
}

Что бы вы использовали как:

let elem, list = list.pop();