CODEWITHSUNDEEP
rust
Jal
Jal

Reputation: 2312

What is the difference between these two linked list implementations?

Consider this implementation:

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

The memory layout of a 2 element node is this:

[] = Stack
() = Heap

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

Consider another linked list implementation:

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

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

The memory layout of a 2 element node is this:

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

The two memory layouts are very similar, and I don't really see how the second implementation is better than the first one, as claimed by Learning Rust With Entirely Too Many Linked Lists.

Upvotes: 1

Views: 179

Answers (2)

red75prime
red75prime

Reputation: 3861

The second layout is actually either

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

or

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

There are no heap allocations for empty elements.

Upvotes: 3

poke
poke

Reputation: 387983

Since this example is taken from that “Learning Rust With Entirely Too Many Linked Lists” book, I’ll just quote the explanations from there:

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

There are two key issues:

  • We're allocating a node that just says "I'm not actually a Node"
  • One of our nodes isn't allocated at all.

On the surface, these two seem to cancel each-other out. We allocate an extra node, but one of our nodes doesn't need to be allocated at all. However, consider the following potential layout for our list:

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

In this layout we now unconditionally heap allocate our nodes. The key difference is the absence of the junk from our first layout.

[…]

The big takeaway here is that even though Empty is a single bit of information, it necessarily consumes enough space for a pointer and an element, because it has to be ready to become an Elem at any time. Therefore the first layout heap allocates an extra element that's just full of junk, consuming a bit more space than the second layout.

One of our nodes not being allocated at all is also, perhaps surprisingly, worse than always allocating it. This is because it gives us a non-uniform node layout. This doesn't have much of an appreciable effect on pushing and popping nodes, but it does have an effect on splitting and merging lists.

[…]

One of the few nice things about a linked list is that you can construct the element in the node itself, and then freely shuffle it around lists without ever moving it. You just fiddle with pointers and stuff gets "moved". Layout 1 trashes this property.

This is just some of the key points from there. I actually think the explanations given by the author of that book are really excellent in providing proper reasoning and the thinking process involved to move from the first iteration to the next.

I’d suggest you to reread the whole chapter and make sure you understand the points there. If you have explicit questions about individual statements, you can ask about them specifically.

Upvotes: 5

Related Questions