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

考虑此实现：这两个链表实现有什么区别？

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*)

这两个内存布局非常相似，我真的不知道第二个实现比第一个更好，如claimed by Learning Rust With Entirely Too Many Linked Lists。

来源

2017-10-04 Jal

第二布局实际上是要么

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

或

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

有对于空元素没有堆分配。

来源

2017-10-04 08:18:31 red75prime

由于这个例子是从“Learning Rust With Entirely Too Many Linked Lists” book取，我就引用the explanations from there：

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*) 
有两个关键问题：

我们分配，只是说一个节点“我实际上不是节点”

我们的一个节点根本没有分配。

从表面上看，这两个似乎相互抵消。我们分配一个额外的节点，但我们的一个节点根本不需要分配。但是，请考虑以下潜在布局：我们的列表如下：
[ptr] -> (Elem A, ptr) -> (Elem B, *null*) 
在此布局中，我们现在无条件地分配节点。关键的区别是我们的第一个布局中缺少垃圾。

[...]

大外卖这里要说的是，即使Empty是一位信息，这必然消耗的指针和元素足够的空间，因为它必须准备好成为一个Elem在任何时候。因此，第一个布局堆分配一个额外的元素，只是充满垃圾，比第二个布局占用更多的空间。

我们的一个节点根本没有被分配，也许令人惊讶的是，比总是分配它要糟糕。这是因为它给了我们一个非统一的节点布局。这对推送和弹出节点没有太大的影响，但它对分割和合并列表有影响。

[...]

一个关于链表的一些不错的事情之一就是你可以构建在节点本身的元素，然后随意将它洗各地的列表，而无需移动它。你只是摆弄指针而东西变得“移动”。布局1会破坏这个属性。

这只是从那里的一些关键点。我实际上认为，这本书的作者给出的解释实际上是极好的提供适当的推理和思考过程，从第一次迭代到下一次迭代。

我建议你重读整章，并确保你了解那里的观点。如果你对个别陈述有明确的问题，你可以具体询问他们。

来源

2017-10-04 08:37:51 poke

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

回答

相关问题