這兩個鏈表實現有什麼區別？

考慮此實現：這兩個鏈表實現有什麼區別？

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

這兩個鏈表實現有什麼區別？

回答

相關問題