在我的 Rust 单链表中实现 .pop() 的更好方法是什么？

Question

我已经在 Rust 中实现了我自己的单向链表版本，作为我学习它的挑战之一，我对除了 .pop() 方法之外的所有东西都很满意。使用 2 个 while 循环非常丑陋且效率低下，但我没有找到其他方法来解决将索引 len() - 2 处的节点设置为 None（弹出列表）并使用来自Some(data) return 值的索引 len() - 1 处的节点（returns 被弹出的元素）。

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

您可以通过跟踪您看到的最后一个元素（然后在最后更新它）来避免重新遍历列表。

如果你对自己的做法太天真了，你会运行惹上麻烦；您的 "previous" 指针保留列表其余部分的所有权，借用检查器不允许这样做。诀窍是在你进行时打破 link - 为此你可以使用 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);
}

顺便说一句，如果你愿意稍微改变一下界面，那么所有这些指针改组都会简化很多，这样我们每次都会 return 一个 "new" 列表（在 pop 函数），或者使用持久数据结构，就像他们在 Learning Rust with entirely too many linked lists 中所做的那样（已在评论中提到）：

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

你会使用哪个：

let elem, list = list.pop();

Answer 2

fn pop(&mut self) -> Option<T> {
        let mut current: &mut Option<Box<Node<T>>> = &mut self.head;
        loop {
            // println!("curr: {:?}", current);
            match current {
                None => {
                    return None;
                }
                Some(node) if node.next.is_none() => {
                    let val = node.data;
                    *current = node.next.take();
                    return Some(val);
                }
                Some(ref mut node) => {
                    current = &mut node.next;
                }
            }
        }
    }

在我的 Rust 单链表中实现 .pop() 的更好方法是什么？

What would be a better way to implement .pop() in my single linked list in Rust?

linked-list

rust

singly-linked-list