使用 Box<T> 和 &'a T 实现的链表有区别吗？

Question

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

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

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

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

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

Answer 1

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

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

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

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...
}

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

使用 Box<T> 和 &'a T 实现的链表有区别吗？

Is there a difference between a linked list implemented using Box<T> and &'a T?

reference

heap-memory

rust

data-structures

recursive-type