In this episode we will implement a linked list.
We'll start by writing the implementation of a simple linked list and then modify that implementation
to implement w linked list.
A link list is a data structures that represent a collection of elements.
Every element is gonna hold a value.
In this case a reference to the next element.
So this will in the end form some sort of chain.
The last element of this chain or list doesn't reference any other one which means that is the last
one.
So we need to define a list which points to the first element or no.
And every note points to the next one.
So let's write this into a code first thing way to go is to define a list.
Which is a structure which will have a field call head and this head will point to note which is the
type that we would need to define right now.
So let's define a node.
I would just so the node has a value let's just use integrals for the values and have a reference to
the next one.
So let's call the next which will point to a node okay.
So the first model we need to define is on the list we'll call the first which will give me the first
note.
So this will return.
Now it will be as simple as this return least of her right.
Also my list will need to implement a method called push in order to push values.
So every time I call Kush I add a new note to this list.
So I wonder value which I said is going to be an integer and it is not going to return anything.
We are gonna implement this later.
So now we have all the methods I need on my list.
I need to implement some methods on my note to the first method on my note will be next.
So next will return me the next note.
In this case when I call next on my first note it will return me the second one.
So this will probably return now.
The next which is very simple okay.
So I have all the methods I need.
I will probably need to implement push so let's start by creating a new list without any note.
What I want to do is when I call push one least push 2 and least push 3 1 I will be doing will be something
like this.
I will be the first element when I call push again it will call after the first one and when I call
it again I will call it after until later.
So let's do that so the first thing is when I push I need to make sure that my list is not empty which
means that hair is not new.
If it's nil I will assign the first note to my head.
So first I need to create my known let's create a note with value.
The value that I just pass here.
And if my lease is empty I will sign this note to the head which is the first element on the list.
And also I will assign these to the tail and what is still still nothing but I will define it right
here.
So tail will point to the last element on the left or to the last note.
So my list have two pointers or two reference to the first one to the last one.
Everytime I push something I will appended to the last one.
But if my list is empty I will also assigning to the head right.
So the first element is going to be appointed by head and tail.
Okay.
So for now this should be working.
Let's execute this.
Everything is fine right now.
If I want to call next on my note.
So let's say you lose the first.
I have my first note here.
Let's bring the value let's see what happened here.
This will work.
It brings 1.
If I change this to 2010 open print.
Now if I do and is gonna be equal to and the next which will return me the next element and I print
its value what happened is that I have a memory problem because next is not assigned yet and that should
be made in the push method.
So the fear is that if my list is not empty which means that I already have at least one known I will
say this my current last known dot next is going to be equal to the note.
So now this should work.
What I just did.
Let me show you on the picture.
So let's assume my list is empty.
When I assign the first note my head and my tail reference are gonna be pointing to this element.
The first one A.
Now when I assign a new one what I'm doing here is that I'm saying a my daily is point here which is
a element when the first one I wonder.
This part of the element which is the next points to the newly created element.
And then I move her to point to this one.
So if we go through the code here this is exactly what I'm doing.
I'm creating a note for every case.
If my list is empty I will create this I will assign this note to the head in every case.
I will assign it to the tail as well after the.
But if my list has already some element the tail the previous tail dot next is gonna be the note so
this is pretty much what we need for a linguist.
Now let's try to traverse this list.
We know that the last element dot next is gonna be Neil.
So let's do a four which we'll learn in previous section and let us start by saying an is gonna be the
first note.
This is my first note.
Let's print the value and then let's assign to the new one.
So And up next will be this.
Now what happened in this is not Neil.
I shouldn't continue the iteration I should start.
So if n it's equal to Neil which means there's no next.
I will just break the execution.
That's it.
I mean this should iterate until we find a Neil element.
OK so we bring 1 2 3 right.
So this pretty much is for the simple list.
Now I want to explain you are doubly linked list in Dublin list knows points not only to the next one
but to the previous one.
So why is this useful.
Because I can go back and forth depending on the operation that I want to do.
So let's modify the current code with half in order to implement this.
So the first thing we need is that as we want to traverse the list by words we need to define a method
to get to the last element.
Well let's define the last method which also will return a note.
The implementation is as you might guess return the tail.
Right.
Also as we saw in our picture note has a reference to the previous element.
So went into a new field called PRA which also gonna point where no and then a method which returns
that is pretty obvious.
Now how to traverse this is going to be like this last and then I'm going to copy this because pretty
much the same but instead of going to next we should call previous.
Now there's something missing here because they haven't implemented that yet.
So if they run this one going forward one two three and then it stops in three.
Why.
Because the previous element which is here it's always empty.
So that a for loop goes here and it's always needed because it's empty and it's done the execution how
to do that.
It's right here.
So every time we assign a new element to our list we need to link it back to the note.
So the new node previews is gonna be equal to the previous tale.
Okay.
So let's execute this and see what happened and how it works.
I have one two three and then three two one.
So let me go to the picture again to explain you what we just did here.
Every time I push an item to the list w link that so I link the new element let's say I'm outlining
B to the list as we did previously we assign B to the first element next reference but also that element
which is a it's been assigned to the previous one.
So again B is assigned to a and a is assigned to be.
So let's just review the code one more time to understand why we just did.
The list is empty.
Well we just started.
So these will be true had is empty.
So we assign the node to head and we also assigned to the tail which is the first no is gonna be pointed
by Helen pale because our lives just have one element.
But on further iterations that tail dot next is going to be assigned to the newly created node and also
that node that preview is gonna be assigned to the current last one item so that I can iterate over
them now for traverse the list from the beginning.
You call first and you do this for traversing the list backwards.
Would you just call last instead of column next.
No.
You call previous.
No no.
This is maybe not very useful in a language let go because as we saw in the previous section we have
slices which is pretty much the same and also go offers at least package which is pretty much what we
did first with what we just did but with other names they call element instead of note.
But they have next and previous they have a list and they have other methods which are like for finding
elements and getting the size of the element removing elements and so on.
So probably when we write production code we're not going to implement our own linked list but it's
pretty good to do these kind of exercises to bring practice what we've been learning so as an exercise
if you want to improve a little bit I will say try to implement and then you write it here and try to
implement the fine method which you should be.
I'm not gonna implement I'm just going to write a signature of the function that'll be fine and then
value integer and this should return a note.
So these functions should traverse the whole list and return the first note which matches that value
like no good value should be equal to this value.
So if you want to improve a little bit implement that and of course if you want to understand how this
is implemented in the standard library you can also go here and let's say I want to see how my element
is implemented.
I can just come here and go to the code which is super well documented.
This is going to be very useful if you want to improve your skills.
So this is for this episode.
I hope you enjoy it and see you on the next one.
But.