在构建链表时如何保持对最后一个节点的可变引用？

Question

我正在尝试实现从 Iterator 构建单链表，保持元素的顺序。

结构定义为：

#[derive(Debug)]
struct List<T> {
    list: Node<T>,
}

type Node<T> = Option<Box<Link<T>>>;

#[derive(Debug)]
struct Link<T> {
    head: T,
    tail: Node<T>,
}

我正在考虑保留对列表末尾的可变引用并在迭代时扩展它。但是，我无法弄清楚如何做到这一点。（无效的）想法是：

impl<T> List<T> {
    pub fn from_iterator(i: &mut Iterator<Item = T>) -> Self {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;
            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);
                // --> I aim for something like the line below. Of course
                // 'singleton' can't be accessed at this point, but even if I
                // match on *last to retrieve it, still I couldn't figure out how
                // to properly reference the new tail.
                // last = &mut singleton.tail;
            }
        }
        list
    }
}

可以只反向构建列表，然后以相同的时间复杂度将其反向，但我很好奇上述方法在 Rust 中是否可行。

Answer 1

我不确定你是否可以循环执行。借用检查器可能不够聪明。不过你可以用递归来完成。

impl<T> List<T> {
    pub fn from_iterator(i: &mut Iterator<Item = T>) -> Self {
        let mut list = List { list: None };
        Self::append_from_iterator(&mut list.list, i);
        list
    }
    pub fn append_from_iterator(list: &mut Node<T>, i: &mut Iterator<Item = T>) {
        match i.next() {
            Some(x) => {
                let mut singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                Self::append_from_iterator(&mut singleton.tail, i);
                *list = Some(singleton);
            }, 
            None => (),
        }

    }
}

playground

Answer 2

如中所述，您可以使用 {}:

显式转移可变引用的所有权

impl<T> List<T> {
    pub fn from_iterator<I>(i: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;

            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);

                last = &mut {last}.as_mut().unwrap().tail;
            }
        }
        list
    }
}

我还删除了特征对象 (&mut Iterator) 以支持泛型。这允许更优化的代码（尽管使用链表可能不值得）。

不幸的是，unwrap 是必需的。即使 Link 被放置在堆上，使地址稳定，编译器也不会执行该级别的生命周期跟踪。可以使用基于这些外部知识的 unsafe 代码，但我不知道在这里这样做是否值得。

在构建链表时如何保持对最后一个节点的可变引用？

How do I keep a mutable reference to the last node while building a linked list?

linked-list

rust

singly-linked-list