如何在LinkedList上实现"push_back()"函数

Question

我几天前开始学习铁锈。我听说在rust中实现数据结构非常容易混淆，尽管我想尝试一下。这个选择属于最简单的LinkedList。

我实现了一个Node作为一个结构：

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

为了简单起见，没有通用值。

我实现了fmt::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结构。

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

目前，我只尝试实现push_back()函数，结果发现它很难让我失败。

这是它的当前状态：

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());
}
}
}
}

在我展示它的结果之前，让我解释一下我如何理解我的代码——这是最有可能发生错误的地方。

我创建了一个指向新创建的节点的不可变指针。指针Box存储在堆栈上，指向在堆上创建的节点。

然后我匹配self.tail以查看列表是否为空。在这种情况下，我执行以下代码块：

self.head = Some(new_node.clone());
self.tail = Some(new_node.clone());

因此，我自欺欺人地认为self.head和self.tail指向堆上的同一地址，因为我只克隆了指针。如果我正确地理解了我的调试器，不幸的是，情况并非如此。

如果我天真地在空列表上执行它，它会编译并为尾部分配一些Node。当我尝试添加另一个节点时，第一个arm执行：

tail.next = Some(new_node.clone());
swap(&mut Some(new_node.clone()), &mut self.tail);

在这里，我想对尾部进行操作，尾部应该与头部完全相同，并修改其next属性。之后，我尝试用新创建的节点交换当前的尾部。

因此，在这种状态下，我希望我的LinkedList看起来像这样：

Head: Node { value: 5, next: Node { value: 3, next: None } }
Tail: Node { value: 3, next: None }

不过，我的代码没有达到我的期望。

它输出：

Head: Node { value: 5, next: None }
Tail: Node { value: 3, next: None }

我误解了什么？如果有任何提示，我将不胜感激。

如果有人想重现代码，我也会分享我编写的负责测试的代码。

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

测试.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 }
"#],
)
}
}

它当然不能通过最后一个。

Answer 1

Box是一个智能指针。当您克隆Box时，它会创建一个深层副本，而不是浅层副本，并且节点在内存中会完全不同(如果您想了解一下，实现就在这里(。

此外，在Rust中，您想要做的是不可能的。您试图违反Rust的核心借用规则：不存在别名可变借用。当列表为空时，您可以尝试将head与tail别名，当列表不为空时将tail与tail_prev.next别名。我想你从一个没有所有克隆的简单代码开始，但编译器抱怨，所以你添加了它们。你只是隐瞒了问题，但什么也没解决。

有三种不同的方法来解决这个问题。第一个也是最建议你停止试图欺骗编译器。只是不要化名。创建一个只有head而没有tail的单链表。这是你应该能够自己解决的问题。

第二个和第三个更为复杂。第一种是使用CCD_ 19和CCD_。最后也是最危险的是使用不安全的代码(std::collections::LinkedList就是这样做的，但不建议初学者使用，尤其是在没有建议的情况下(。

如果你想创建链表来学习Rust，一个非常推荐的阅读方法是用太多链表学习Rust。它实现了所有三种变体以及更多变体。