我可以在没有所有者移动或不安全的情况下遍历单向链表吗？

Question

单向链表可以简单地从tail创建。但是不能从头开始，我试了很多次，代码在这里：https://gist.github.com/tioover/8d7585105c06e01678a8.

事实上，我想搜索然后删除链表中的一个节点。但我不能遍历带有可变借用指针的链表：https://gist.github.com/tioover/526715ed05342ef5b4f1。我也试过很多次了。

Answer 1

这是来自的一些代码。它显示了一种可以添加到开头和结尾以及中间的列表的方法。

#[derive(Debug)]
struct Node<T> {
    v: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(v: T) -> Node<T> { Node { v: v, next: None } }

    fn push_front(self, head: T) -> Node<T> {
        Node {
            v: head,
            next: Some(Box::new(self)),
        }
    }

    fn push_back(&mut self, tail: T) {
        match self.next {
            Some(ref mut next) => next.push_back(tail), 
            None => self.next = Some(Box::new(Node::new(tail))),
        }
    }

    fn push_after(&mut self, v: T) {
        let old_next = self.next.take();

        let new_next = Node {
            v: v,
            next: old_next,
        };

        self.next = Some(Box::new(new_next));
    }
}

fn main() {
    let mut n = Node::new(2u8);
    n.push_back(3u8);
    let mut n = n.push_front(0u8);
    n.push_after(1u8);

    println!("{:?}", n);
}

重要的是，当我们添加到头部时，我们将旧的头部作为self来消耗。这允许我们将它移动到 Box 中，它将成为新头的追随者。删除项目是此示例的直接扩展，但您需要稍微向前看并处理更多边缘情况（例如，如果没有第二个后继者该怎么办）。

我可以在没有所有者移动或不安全的情况下遍历单向链表吗？

Can I traverse a singly linked list without owner move or unsafe?

lifetime

rust

data-structures

singly-linked-list