data-structures - 使用 Box 和 &'a T 实现的链表之间有区别吗？

Question

我正在努力理解链表的这两种实现之间的区别。第一个版本是 Rust 书中使用 Box<T> 给出的版本。 :

enum List {
    Cons(i32, Box<List>),
    Nil,
}

这是我想到的另一个实现:

enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}

两者之间有什么重要的区别，或者在这种情况下它们是等价的吗？

Answer 1

这些实现中的任何一个都技术上可行，但有一些重大的权衡。

Box 在堆上进行分配，然后拥有 数据。与管理引用相比，这非常方便和灵活。

为了使用 & 引用构建第二种类型的列表，您需要在某处拥有数据。因此，您需要管理任意数量的节点并确保它们不会超出范围。这可能非常严格。例如，创建一个构造列表然后返回它的函数并不是很容易:

fn make_list<'a>() -> List<'a> {
    let node1 = List::Nil;
    let node2 = List::Cons(1, &node1);
    let node3 = List::Cons(2, &node2);
    node3
    // node1 and node2 go out of scope here...
}

这是行不通的，因为它引用的是函数局部变量，当函数返回时，这些变量会超出范围。使用 Box 的版本将起作用，因为 Box 取得了数据的所有权。