如何在构建单链表时保留对尾节点的可变引用？

嘿，我懂你的需求啦——你已经定义好了单链表的结构体，现在想通过迭代器来构建它，还希望靠维护尾部的可变引用避免每次添加元素都从头遍历，对吧？这确实是个能提升效率的好思路，咱们一步步来实现它。

首先先确认下你的结构体定义（方便后续讨论）：

#[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>,
}

核心思路：死死盯住尾部的可变引用 #

要高效从迭代器构建链表，关键就是始终持有当前尾部节点tail字段的可变引用。这样每次加新元素时，直接修改这个tail字段就行，不用从头遍历找尾部，把单次添加的时间复杂度降到O(1)。

实现FromIterator trait #

Rust里从迭代器构建集合的标准方式是实现FromIterator trait，这样你就能直接用Iterator::collect()方法来构建链表了，非常顺手。下面是具体实现：

impl<T> List<T> {
    // 空链表构造函数
    fn new() -> Self {
        List { list: None }
    }
}

impl<T> FromIterator<T> for List<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = List::new();
        // 用可变引用跟踪当前尾部的`tail`字段
        let mut tail = &mut list.list;

        for item in iter {
            // 为当前元素创建新的Link节点
            let new_link = Link {
                head: item,
                tail: None,
            };
            // 把当前尾部的位置替换成新节点
            *tail = Some(Box::new(new_link));
            // 更新尾部引用，指向新节点的`tail`字段，为下一次添加做准备
            tail = &mut tail.as_mut().unwrap().tail;
        }

        list
    }
}

代码细节解释 #

1. 初始化空链表：先创建一个空的List，此时list.list是None。
2. 跟踪尾部引用：tail一开始指向list.list的可变引用，也就是链表的“入口”位置。
3. 遍历迭代器元素：
   • 为每个元素生成新的Link节点，它的tail初始化为None（因为刚添加的元素是当前最后一个）。
   • 把tail指向的位置（可能是空链表的入口，也可能是上一个节点的tail）设置为新节点，完成添加动作。
   • 更新tail引用：通过tail.as_mut().unwrap()拿到刚添加的节点的可变引用，再取它的tail字段作为新的尾部引用，这样下一次添加就能直接操作这个位置了。

测试验证功能 #

写个简单的测试看看效果：

fn main() {
    let list: List<i32> = vec![1, 2, 3, 4].into_iter().collect();
    println!("{:?}", list);
    // 输出应该是：List { list: Some(Link { head: 1, tail: Some(Link { head: 2, tail: Some(Link { head: 3, tail: Some(Link { head: 4, tail: None }) }) }) }) }
}

额外：手动逐个添加的push_back方法 #

如果你需要手动逐个添加元素，也可以基于类似思路实现push_back（不过这个是O(n)复杂度，因为每次都要找尾部，不如FromIterator高效）：

impl<T> List<T> {
    fn push_back(&mut self, item: T) {
        let mut tail = &mut self.list;
        while let Some(node) = tail {
            tail = &mut node.tail;
        }
        *tail = Some(Box::new(Link { head: item, tail: None }));
    }
}

内容的提问来源于stack exchange，提问作者Petr