Another way to store data is by using a linked list.
There are a couple of different linked lists.
We can have a singly linked list and a doubly linked list.
But in this lecture and in this section, we are going to talk about a singly linked list.
Now, unlike an array which requires a fixed size, we can use a singly linked list which can easily
expand the concept around a singly linked list is pretty simple.
But with Russ's ownership and memory system, sometimes it can be a bit more complicated to create a
linked list in Russ than in other languages.
So let's take a minute to try and understand what a linked list is.
So we'll say we have a node and we'll say it is Node one and we'll just give it a circle.
That way we know it's a node and we'll label it as a node.
So inside of a node, we're going to have two pieces of data at least so we can represent this as a
struct and we will say the name of the struct is Node.
And then inside of here we're going to have our piece of data.
So in this case, our data is going to be one.
And then we're also going to have something that is called next.
So what next is is next is going to store the information.
So the memory address to another node.
So we'll say we have Node two.
And we'll say Node one's memory address.
Memory adder is 100 to keep it simple.
This link right here is represented by the next value and our node struct.
And then we will say our memory address.
For Node two is 200.
So next is going to point to this memory address of 200.
And we know at that memory address is going to be this node that stores the value, too.
So now we can point this node.
It's next value to Node three.
And then we can point this node's value to another node for.
And then we have one more piece that we can point for, too.
So let's just go ahead and fill this out.
So we'll say this is our next link and we'll say this is memory address 300 and this is memory address
400.
So currently what we have for Node one, if we looked inside of it, struck its data is equal to one.
Next is equal to.
200, which this points to Node two whose data is equal to two next.
Next equals 300.
And this is Node three, whose data is equal to three.
Next equals 400, who now we point to Node four.
Who's data equals four.
And who's next?
Equals.
So if Node four isn't pointing to another node, which it's currently not, what would its next be?
Well, in other languages you would typically point this to something like NULL to denote that, hey,
this is the head of the list.
So in rust we don't have null, but what we can do is we can point it to none because we can create
an option inside and it can either be some or none.
So we can have it denote it as none.
But now you heard me say that Node four is the head.
So we want to know where the head is in the link list because this is going to be the top of the linked
list, which is going to be important for us when we want to add elements or or remove elements.
So Node four is also going to have another struc or excuse me, there's going to be another struct.
And what we're going to have in this struct and we'll just call this link is going to be the head,
which then will point to.
A link.
And we'll see this and this will be much clearer when we look at the code.
But what this head is going to do is it's going to point to the top element in our leaked list.
So now that we have a general idea of how linked lists works, let's begin setting up our own linked
list.
That way we can begin to see how the code starts to form, and we begin doing that in the next lecture.