- In the previous section, I introduced the box structure
and I described the fact that it's
like a pointer to an object on heap.
It's a smart pointer.
In this section,
we're going to look at the realistic use of boxes
to define a recursive data structure, like a link list,
I've called it chain here, but it's like a link list.
So imagine you wanted to define a structure
to represent a node in a link list, or a chain.
Each node would have a pointer to the next node.
Because it's like a link list.
The final node points to null
to indicate that's the end of the list.
Okay, so it's a very common kinda data structure.
I'm sure you've seen that kind of thing before.
Each node has a pointer to the next one,
and then eventually the last pointer
points to null, that kind of arrangement.
How would you do that in Rust?
Well, the answer is you have to use box
to achieve that effect.
So this would be our first approach, maybe.
This approach doesn't use box, it's not going to work.
I'll draw a picture
and then you can see what the problem is.
I'll ignore the bit about option for now, okay?
That's to do with whether it's a null pointer or not.
This is how you represent something
that may be a null pointer in Rust using Option.
Let me come back to that point a bit later.
The key point at the moment
is whenever you define a structure,
the compiler needs to know how big it is in bytes,
so we can know how much space to allocate on the stack.
But when the compiler sees this data structure,
it won't compile because NodeBad, as I've called it,
is infinitely nested.
You can imagine if the compiler
is trying to figure out how many bytes it is in size,
it would say, okay then so let's say
I've got one NodeBad instance.
It's got a piece of data which is an integer, like that.
Probably the value 42.
And then it's got another field called Next.
And that is another, let's ignore the option bit for now.
We will come back to that.
It's basically another instance of NodeBad, okay?
So that box there is another instance of NodeBad,
and inside that NodeBad, it's recursive, okay?
Kind of infinitely nested.
It will say, how big is this inner NodeBad?
Well, it's got some data, okay?
That might be the value 43, controversially.
Oh, and then it's got another field called Next,
which is another instance of NodeBad.
Okay, so this thing is going to be infinitely nested
like dolls inside dolls, inside dolls.
The compiler, it'll never end.
The compiler can't possibly figure out
how big it's gonna be in memory.
Basically, you can't nest objects together
like I've done here.
You need pointers to point to something external.
And that's basically where box comes in.
So Rust can't determine the size of this data structure here
and it won't compile.
So this is a better approach.
Again, ignore the option bit for now.
Okay, and I'll come back to that in a moment.
Focusing on the kind of box aspect of it,
a node would look like this.
A node object would have a piece of data,
an I32 like that.
So it knows how big that is. It's 32 bits.
And then it's got a field called Next, okay?
And ignoring the option bit for now,
it is effectively a box, which is like a pointer.
When you see box, think pointer or smart pointer.
So it is a pointer to something externally allocated.
It's a pointer to another node.
It is a pointer to another node.
That's the way to think about box.
All right?
And then, there's another node here,
but we've already solved the problem.
The compiler can ascertain how big this thing is.
It's 32 bits for the integer.
And a box is probably also four bytes
because it's just a pointer really.
So the compiler can work out the size
of this data structure.
Let's say it's eight bytes, problem solved, okay?
So by using a box, it effectively means it's a pointer
to something in external memory.
So we don't need to worry about that
when we're trying to figure out the size of this.
Okay, great. So box to the rescue.
When you go to recursive data structure,
you've got to basically use box
to give you a pointer to another instance.
What about option?
Rust doesn't really do null pointers,
it kind of does pointers to a fashion.
Box is like a smart pointer,
but it always contains a box,
always contains a real...
It always points to a real object.
A box object will never have a null pointer
because that would be dangerous,
and Rust doesn't like danger.
So a box object will always point to something.
So what I've done
is I've decided to put the box inside an option.
So if we think of this more carefully,
let's say we've got two nodes in our data structure, okay?
In the first node, it'll have some data and integer 42.
And then it has an option.
An option can either be some value, or none.
And that's basically where the null concept comes in.
So let's say that this object will have a next pointer.
So the option, if I kind of draw next to it.
The option will be in the sum state.
In other words, the option will contain a box
and that box will point to a node, like this.
It points to the next node.
The next node, let's say this next node
is actually the end of the list, like that.
So it'll have some data, 43, like that,
and it'll have a Next field.
And this Next field is an option.
It can either be some value or none,
and it would contain the value, none.
So instead of containing a box,
which is the value it could contain,
it'll either contain some box, or it'll contain none.
None, which you can think of as effectively being
the Rust equivalent of a safe null pointer.
This is the way you achieve null pointers in Rust.
You have an option which may contain a real object,
or may contain none, like that.
And that's basically how you do the concept of null pointers
in Rust, in a safe way.
Because whenever you access an option,
you've gotta use pattern marking to say,
"Do you contain some value, or do you contain none?"
You can't just directly de-reference it,
unless you call the Unwrap function, of course.
And then good luck with that.
So this is fine now.
The node contains a box, which is effectively a pointer.
So the memory for this thing is known in size
and the pointer points
to an externally allocated node living elsewhere, okay?
So Rust can determine the size of this data structure,
which is the first hurdle that it had to overcome.
Right, so that was a quick example of the theory
of how boxes would be used in a recursive data structure.
I've got quite a detailed example
which I'm gonna step you through now,
which shows how to actually implement this link list.
I've called it chain in the demo.
So we'll have a look at main
and then we'll have a look at demo_box3,
and then we'll run it.