- Okay.
So, in my Main,
I'm going to uncomment this statement,
this is our statement for this example.
And let's have a look at the code, demo box three.
There's quite a lot of code in here.
I'm gonna explain most of it.
What I suggest you do is to have a look at all of it,
when you get a chance, to digest in the kind of calmness
of your everyday life.
So you can actually get a chance to absorb what's going on.
I've called it chain, but it's really like a link list.
Okay, but I called it chain
just to make it something different.
So first of all, just to confirm the fact,
the original approach that we tried,
where we didn't use box,
we just tried to kind of nest the item inside,
that won't work, because it's infinitely nested,
and therefore of infinite size.
So if I uncomment that code,
I will get an error from the compiler.
I'm gonna show you the error.
Recursive without indirection.
It's a recursive data structure.
A data structure that recurs to itself.
But without using pointers.
You can't just nest objects inside each other,
it's like a hall of mirrors.
There has to be some pointer to externalize it.
So I get an error, compiler error.
Cargo run.
Okay, so it's complaining here.
The node bad structure is a bad node,
because it has a recursive data structure.
Without using redirection.
Consider using some kind of smart pointer.
Okay, so we're talking about box at the moment.
Later on in this lesson, we'll have a look at RC,
which is a reference counted pointer.
So, okay, so that doesn't work.
So let's just comment that code back up again.
I'm gonna just get rid of my terminal window for now,
I'm not gonna run the application again for a few minutes.
I just want to step through the code
and explain what's going on.
So if I give myself a bit more space.
I want to bring up a whiteboard,
so I can draw some pictures to explain the code.
Okay, so I'm going to step through the code.
And I'm gonna draw some pictures
in my whiteboard on the right hand side,
to see what's going on.
Okay?
So, in terms of the data for a node,
a node, an individual node, will look like this.
It'll have an integer data.
Like 42.
And then it'll have a next field, on line nine,
and my code there on the left.
And that next field is going to be an option.
It's gonna get quite difficult to draw
if I keep on showing an option that contains a box.
So what I'll do,
is I'll just imagine that there is an option there.
But really it contains a box.
Okay, so, it's not the last node in the list,
in other words.
So next is kinda like a box, really.
Which contains a pointer to the next node.
Okay?
So that's the kind of data structure that we've got.
Let's imagine that we've constructed a link list, or chain,
with just two items, 43.
So the second item, or the second node,
it'll have an option.
But that option, instead of containing some box,
it contained none.
So I just draw it as none,
like that, it's like a null pointer.
I've always drawn it when I'm teaching in other languages,
I draw it as a null pointer, like that,
that's effectively what we are trying to achieve.
Okay, right, so, to when I wanna create a node,
maybe to insert a new node into the chain,
I've got a new function here.
I just pass in the data that I wanna store,
like maybe the value 44, I've got 42 and 43 already.
So I pass in a data value that I'd like my node to contain,
and I create a new node object which contains that data.
But then who's next is none, okay,
so the next value here is none.
So whenever I create a new node,
it'll contain the data that I pass in the parameter.
Like the value 44, like that.
And the next pointer, or the next box, will be none.
Okay, because, well, because of the way this is gonna work,
I'm gonna be appending at the end.
So, making the next pointer effectively null makes sense.
Alright, well, have us discuss that.
Have a look at the append function there
on the left hand side.
The append function is going to, it's a recursive function.
I'm going to arrange it so that you can only append
at the end of the list, okay?
So, it's kinda like a forward-only list,
like you'd have in C++.
It doesn't support insertion at random positions,
and it doesn't support like a push front function,
it only supports a push back mechanism.
Okay, so, let's imagine that by one way or another,
and I'll explain how this works in a moment.
But imagine that this node on the left is the head node,
and imagine that we kind of know
that that's the head node, okay?
What I'm gonna show you in a few minutes,
I've actually got another structure called chain,
which is really list in disguise.
And it's got a box, a pointer,
which points to the head node, like that, okay?
But we'll see the details for that in a few minutes,
let's ignore that part of it for now.
And let's just imagine that one way or another
we know that the box I've drawn here on the left hand side,
we know that it's the head one.
And what I do is I call the append function on here.
I do something like, let's say I've called it head.
Head.append.
And I want to append a node with a data value 44.
Alright, so that's how I'd call the append function.
Head.append, assuming that head is some magical pointer box
that points to this first node.
So what we've gotta do is we've gotta basically recurse,
we've gotta get to a point where we know we're at the end,
and at that point, we can put the new node at this position.
So the append function,
the node is a recursive data structure,
a node is a piece of data, and a pointer to the next node,
box is pointer, really, a smart pointer.
So when you have a recursive data structure,
like a list or binary tree,
the functions that you implement are typically recursive.
They call themselves to step to the next node.
And that's what I've done here.
Have a look at the append function.
So, wherever we're currently pointed to,
so self will initially be pointing here, okay?
It says, are you at the end of the chain?
Let's have a look at your next pointer.
I'm using the word pointer quite freely here,
it's a box, really.
But I'm using the word pointer,
because that's what it is, really, it's a smart pointer.
So, it's saying, look at the next pointer.
Is it null?
Option is effectively can be none,
which is like a null pointer.
And if it's none, we are currently at the end of the list.
It's okay to append at the end of us.
But, at the moment, our next reference isn't none,
it's some box.
Okay, so, this here is some.
So what we do, is we get,
there's some keywords here, ref mut,
it's just a handy way of saying,
give me back a mutable reference to.
Right, so self.next is this option here.
In the box, this option.
And when you say some,
it'll give you back the value inside the option.
So I'm gonna get back,
that will basically be a mutable reference
to the box object.
Like that.
It's like the pointer.
And then what I do is I say, that pointer basically points,
that box points to this node here.
So I say, dereference that box
and call the append function on the thingy 0.2.
So, I'm gonna draw this carefully now.
This is a box object.
And that box object has a pointer.
This variable I've got here, this variable here.
Basically is this box.
All right.
I wanna say object.append, remember,
I was showing you this in the previous demo.
When you have a box, and you call a function,
what it really does is it is as if you did that.
It will implicitly dereference the box,
to give you the node that it points to.
Okay?
So when I say boxed_next_node.append
really what I'm saying is, the pointer, inside here,
points to this node.
And it's upon this node that I call the append function.
I've stepped down the list.
And then it calls the append function recursively,
on that node.
Like that.
Okay?
So if you want to, you can dereference the box explicitly,
if you prefer, you can dereference the box implicitly.
That's weird, isn't it?
A C++ developer would find this tricky.
I did, coming from C++.
So basically, what it does,
it comes back up to the append function again,
but this time we've marched on to the next node.
We're trying to get to the last node,
so that we can then append the item after us.
So, let's have a look,
we're currently pointing here.
Let's have a look at the next field.
Now the next field here is an option, and it's none.
That's what I've been waiting for.
It says, oh, if it's none, there's nothing after you,
you've got a null next pointer, effectively.
So in that case, great, in that case, we can create,
now have a look at this code here,
we're basically gonna create a new node and stick it here.
Alright, that's what's gonna happen.
I'm gonna move this picture a little bit to the left,
to give myself a bit more space.
Okay.
And let's see what's going on in this piece of code here.
So the most nested piece of the code is this bit here.
So that will create a new node, containing the data,
alright, so that's gonna create a new node,
via the new function, the constructor,
effectively, effectively.
And it'll put the data, the value that we specify, just 44.
And remember that when you create a new node,
when you create a new node,
it basically sets the new node to have a null next pointer.
Or to put it in a Rust way, it has a box,
it has an option, that's set to none.
So, in a kind of a pointer-ish kind of dialect,
I could say it has a null next pointer, like that.
Okay, so it knows that it's at the end.
Okay, so that's created the node object.
And what I then do, is I put that pointer into a box,
it would be allocated all in a heap.
Okay, so that box object, we'll wrap it up.
And that box object goes inside an option.
And that option is what I store in my current next field.
So this next field here,
this is the next field that we currently at.
That becomes an option.
Okay, it is an option.
And it contains some value as opposed to none.
In particular, the option contains a box.
So what I've just drawn in red is a box, this here.
And I'll draw it again.
That there is the box.
And that box will contain a pointer
to the node that's just been allocated,
instead of being a null pointer,
it now points here like that.
Alright?
So, to be perfectly honest,
I mean I've been writing code like this in C++ for 30 years.
And when I learned Rust, I found this hard.
It really challenges your understanding,
in C++ I could have written this in five minutes.
With pointers, and I get that,
and I've been doing it for years.
With Rust, the idea of using this to represent the pointer,
and then having to wrap it in an option,
to represent the now pointer,
is a very different mental model.
So I had to really think this through
when I was learning this myself.
I'm gonna go through just a few orbits,
and then I'll leave you
have a look at full details yourself.
What happens if you display a node?
Okay, so if I just move my diagram
back to the right hand side.
And let's just see
if I can get rid of some of my writing here.
Having appended items into the list.
So the list contains the data that we want.
Let's say we want to display all the data.
So the way you do that, is you call the display function,
on the head node.
And it ensures that it is printed, and so is the next one,
and so is the next one in a recursive kinda way.
So I'm gonna display function here.
And what you would do is you would, again,
you'd have some kind of head pointer,
via the chain class.
Structure, excuse me.
And it would tell me where the head of my chain is.
So let's say I've said head.display.
So that would basically try to display the first node.
Okay, well that's fair enough.
In the display function,
it prints the data for the first node.
And that's going to be the value 42.
Beautiful.
Like that.
And then it says, okay,
but then I've gotta print the rest of the list.
So, it says, am I at the end?
Is the next pointer null?
No, it isn't, it's some value.
So, it'll basically get the box out of here.
That's the box that the option contains.
That box contains is here.
Okay?
And that box, again, I could have said here, tick the box.
The box is effectively a pointer.
Dereference the pointer.
To get the actual node that you're talking to.
So it would dereference this box,
and gimme back the node like that.
Or I can do that implicitly without the star.
And believe it or not, people actually write it that way.
Even C++ developers.
So what you're basically saying is,
you are moving to the next node.
And then you call in display on that.
Okay?
And that'll go through the same process,
it'll print the value,
the data for the cabinet node, which is 43.
And it'll then chain on to the next node,
and the next node is here.
Okay?
And that'll print the data at the current node.
So that'll be 44.
And then it says, and by the way, what's your next pointer?
Is it null?
Yes, it is.
None, really, in an option kinda way.
So that means we've reached the end.
So what I do is I just print end, just to confirm,
just to get confirmation of the fact
that it has actually reached the end, like that.
There we are.
So, it does take some getting used to,
but you will get used to it.
And it is a beautiful thing, really.
It's much safer than the corresponding code in C++.
I can't possibly dereference a null pointer here.
I can't forget to deallocate anything,
it's all managed for me, much safer.
So what I'll do is just to finish off,
I'll just delete my picture that I've got so far.
Because there's another structure
that I'll just introduced briefly, and that's chain.
Chain is really the list class, if you like,
in other programming languages.
And it just contains a head pointer, if you like.
I say pointer, I really mean box.
It contains a pointer to the head node, or possibly null.
Okay, so this, for a C++ developer,
would be a pointer to a node that might be a null pointer,
it's a nullable pointer to node.
A Rust developer would say it's a boxed node.
So the node will be allocated on the heap,
and the box will have a pointer.
Or it could be none.
So when I create a new chain, in my code down below,
in fact, let me just show you the code down below.
When I create a new chain here.
The constructor, effectively, it creates a chain,
and just sets the head to be none.
Head is an option.
It can be some value, or it can be none.
So, when you create a new chain,
and it has a head, a box.
Which is effectively a null pointer,
to say it's an empty collection, at the moment.
When you call the insert function,
I've called the insert function four times,
it's an append function, really,
perhaps I should have called it append, but there we go.
When you call the insert function,
the insert function, basically, it has to decide
whether to create a new structure, or basically,
it needs to decide what to do about the head point,
that's the key point.
In the special case, it's only the first time,
where the head pointer is effectively gonna be null.
So, first time through, when we call the insert function,
it'll say, is the head pointer null?
And if it is, and it is,
then it'll basically create a new node.
It'll create a node.
Put it into a box, put it into an option.
And that's what our head variable is.
So our head variable now, is an option that contains a box.
And that box contains a pointer,
to a new node that's being created like that.
Alright, if we call the insert function again,
it would say, is the head pointer null?
And no it isn't.
The head pointer points to a node.
In that case, what it'll do
is it'll basically tell that node to append.
Okay, that's the function
that I introduced about five minutes ago.
When you have a pointer to the head node,
and you call append, as we saw in the last five minutes,
the append function basically figures out,
there may be multiple nodes here.
The append function will kind of recursively figure out
where the last node is,
and then it'll basically stick the new data at the end.
And it's the same thing for display.
When I display a chain, if my chain is empty,
it just says empty chain.
If the head chain isn't empty, then all it does
is to say to the first node in my collection,
basically the head node.
It'll say basically display the head node.
It'll call the display function on the first node.
And again, from what we saw earlier,
when you call display on a node, it displays itself,
and then goes to the next one,
and it keeps on doing that recursively,
until it reaches the end.
So I guess all I need to do now,
is to actually run the application,
and I rather hope it works after all that effort.
So, create an empty chain, insert some items, append,
and then display the whole chain at the end.
I have all digits crossed.
Cargo run.
So I'm hoping it's going to, basically,
it'll insert 100, and then append 200, and append 300.
I want to display it.
It'll display 100, 200, 300, and then end.
(sighs)