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

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>(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代码，但我不知道在这里是否值得。

Answer 2

我不确定你能循环做。 借用检查器可能不够聪明。 不过，您可以使用递归来做到这一点。

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 => (),
        }
    }
}

操场