Rust中如何为递归类型定义的链表实现尾部追加元素方法

你给出的示例框架存在几处笔误，需要先修正才能正常编译：

• type 是 Rust 保留关键字，不能作为函数参数名，替换为bug_type即可
• BugColony初始化时字段名为first，正确写法是BugColony { first: None }
• 你贴的预期输出里结构体名WorkEnvironment、第二个节点的bug_type是笔误，和你定义的结构体对应后应为BugColony、第二个节点bug_type为Bedbug

符合Rust所有权规则、无unsafe、零额外开销的惯用实现如下，全程通过可变借用遍历链表，不发生节点所有权转移：

#[derive(Debug, Clone, Eq, PartialEq)]
struct BugColony {
    pub first: Link,
}

type Link = Option<Box<Bug>>;

#[derive(Debug, Clone, Eq, PartialEq)]
struct Bug {
    bug_type: String,
    next_bug: Link,
}

fn main() {
    let mut list = BugColony { first: None };
    list.add_bug(String::from("Bee"));
    list.add_bug(String::from("Bedbug"));

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

impl BugColony {
    fn add_bug(&mut self, bug_type: String) {
        let new_node = Box::new(Bug {
            bug_type,
            next_bug: None,
        });

        // 从链表头开始，用可变引用遍历到尾部空节点
        let mut cur = &mut self.first;
        while let Some(node) = cur {
            cur = &mut node.next_bug;
        }
        // 写入新节点
        *cur = Some(new_node);
    }
}

实现说明 #

• 不需要单独判断头节点是否为空：如果链表为空，while let循环不会执行，直接将新节点插入头节点位置即可
• 遍历过程中始终持有当前节点位置的可变引用，不会触发节点的移动或复制，完全通过借用检查
• 没有运行时额外开销，时间复杂度为O(n)，和单链表尾部追加的理论最优复杂度一致

运行后输出结构和你预期完全匹配：

BugColony { first: Some(Bug { bug_type: "Bee", next_bug: Some(Bug { bug_type: "Bedbug", next_bug: None }) }) }

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