如何在Rust中正确实现LinkedList的push_back()方法？

问题背景 #

刚学习Rust几天，尝试实现最简单的LinkedList，定义了Node和LinkedList结构体，但在实现push_back()方法时不符合预期：添加两个节点后，预期head的next指向tail节点，实际head的next为空。

Node结构体定义 #

#[derive(Debug, Clone)]
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

Node的Display实现及new方法 #

impl fmt::Display for Node {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

impl Node {
    fn new(value: i32) -> Node {
        Node {
            value,
            next: None,
        }
    }
}

LinkedList结构体及有问题的push_back实现 #

struct LinkedList {
    head: Option<Box<Node>>,
    tail: Option<Box<Node>>,
}

impl LinkedList {
    pub fn push_back(&mut self, value: i32) {
        let new_node = Box::new(Node::new(value));

        match self.tail {
            Some(ref mut tail) => {
                tail.next = Some(new_node.clone());
                swap(&mut Some(new_node.clone()), &mut self.tail);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node.clone());
            }
        }
    }
}

扫描函数及测试代码 #

扫描链表的工具函数：

fn scan_list(list: &LinkedList) -> impl Iterator<Item=Node> {
    let mut current_node = list.head.clone();

    std::iter::from_fn(move || {
        match current_node.clone() {
            None => {
                None
            }
            Some(node) => {
                current_node = node.clone().next;
                Some(node.as_ref().clone())
            }
        }
    })
}

tests.rs测试代码：

#[cfg(test)]
mod tests {
    use super::*;
    use expect_test::{expect, Expect};
    use crate::{scan_list, LinkedList, Node};

    fn test_list(src: &LinkedList, expect: Expect) {
        let actual: String = scan_list(src).map(|node| format!("{:?}\n", node)).collect();
        expect.assert_eq(&actual)
    }

    #[test]
    fn test_empty_list() {
        let list = LinkedList { head: None, tail: None };
        test_list(
            &list,
            expect![r#""#],
        )
    }

    #[test]
    fn test_list_with_single_node() {
        let list = LinkedList { head: Some(Box::new(Node::new(5))), tail: None };
        test_list(
            &list,
            expect![r#"
                 Node { value: 5, next: None }
            "#],
        )
    }

    #[test]
    fn test_list_with_two_nodes() {
        let mut list = LinkedList { head: None, tail: None };
        list.push_back(5);
        list.push_back(3);
        test_list(
            &list,
            expect![r#"
                 Node { value: 5, next: Node { value: 3, next: None } }
                 Node { value: 3, next: None }
            "#],
        )
    }

}

核心误解 #

你对Box<T>的Clone实现理解错误：Box<T>的Clone不是复制指针，而是深克隆——它会克隆Box指向的堆上整个T实例，生成新的Box指向新的堆内存地址。每次调用new_node.clone()，都会创建完全独立的Node副本，而非让多个Box指向同一个节点。

这导致：

1. 第一次push_back时，head和tail各自持有独立的Node(5)副本，两者无关联
2. 第二次push_back时，tail副本的next指向新的Node(3)副本，随后tail被替换为另一个Node(3)副本，而head的Node(5)副本的next仍为None

修正方案 #

要实现正确的push_back，需利用Rust的共享所有权智能指针Rc和内部可变性RefCell，让head和tail指向同一个节点实例：

修正后的Node结构体 #

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(value: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node {
            value,
            next: None,
        }))
    }
}

修正后的LinkedList及push_back方法 #

struct LinkedList {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}

impl LinkedList {
    pub fn new() -> Self {
        LinkedList { head: None, tail: None }
    }

    pub fn push_back(&mut self, value: i32) {
        let new_node = Node::new(value);
        match &self.tail {
            Some(tail) => {
                // 获取tail节点的可变引用，修改next指向新节点
                tail.borrow_mut().next = Some(new_node.clone());
            }
            None => {
                // 空链表时，head指向新节点
                self.head = Some(new_node.clone());
            }
        }
        // 更新tail为新节点
        self.tail = Some(new_node);
    }
}

修正后的scan_list函数 #

fn scan_list(list: &LinkedList) -> impl Iterator<Item=i32> {
    let mut current_node = list.head.clone();

    std::iter::from_fn(move || {
        current_node.take().map(|node| {
            let node_ref = node.borrow();
            current_node = node_ref.next.clone();
            node_ref.value
        })
    })
}

额外说明 #

• Rc用于共享所有权，允许多个指针指向同一堆内存实例，通过引用计数管理生命周期
• RefCell提供内部可变性，允许在不可变引用下修改内部数据，适合链表这类需要修改节点关系的场景
• 入门阶段实现链表遇到所有权问题是Rust内存安全机制的正常体现，理解所有权、引用、智能指针是关键

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