这两个链表实现有什么区别？

Question

考虑这个实现:

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}

2元素节点的内存布局是这样的:

[] = Stack
() = Heap

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)

考虑另一个链表实现:

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

2元素节点的内存布局是这样的:

[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Empty, *junk*)

两个内存布局非常相似,我并没有真正看到第二个实现如何比第一个更好,正如学习Rust与完全太多链接列表所声称的那样.

Answer 1

由于这个例子来自于"学习Rust with Eachly Too Many链接列表"一书,我只想引用那里的解释:

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)

有两个关键问题:

• 我们正在分配一个只是说"我实际上不是节点"的节点
• 我们的一个节点根本没有分配.

从表面上看,这两个似乎相互抵消了.我们分配了一个额外的节点,但我们的一个节点根本不需要分配.但是,请考虑以下列表的潜在布局:

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)

在这种布局中,我们现在无条件地堆分配节点.关键的区别在于我们的第一个布局没有垃圾.

[...]

这里最重要的一点是,即使Empty只是一点信息,它也必然会为指针和元素消耗足够的空间,因为它必须随时准备好变成一个Elem.因此,第一个布局堆分配了一个充满垃圾的额外元素,比第二个布局消耗更多的空间.

我们的一个节点根本没有被分配也许令人惊讶地比总是分配它更糟糕.这是因为它为我们提供了非均匀的节点布局.这对推送和弹出节点没有太大的影响,但它确实对分割和合并列表有影响.

[...]

链接列表中为数不多的好处之一就是你可以在节点本身中构造元素,然后在列表中自由地移动它而不用移动它.你只是摆弄指针,东西被"移动".布局1会破坏此属性.

这只是其中的一些关键点.我实际上认为该书作者给出的解释在提供适当的推理和从第一次迭代到下一次迭代所涉及的思考过程方面非常出色.

我建议你重读整章,确保你理解那里的要点.如果您对个别陈述有明确的疑问,可以专门询问.