Hello all and welcome back.
So in this video let's now move forward and do the first variation of insert that is inserting at the
head of our linked list.
So let's get started.
Now first let me quickly draw a linked list.
Now I'm making sure to draw this again and again in front of you, because I also want all of you to
have this habit drawing linked list is like is very important.
If you are solving any question or trying to do any operation in your linked list.
Okay, so let me just join this.
The way we have discussed as of now, I am assuming that there are three elements or three nodes in
my linked list ten 2030 this is pointing to none, right?
Great.
So if I think now what exactly is the ask is that I will be creating a new node.
So let's say this is my new node.
And let's say it is having some value say 100 okay.
As of now, this is none.
We are also aware of this.
My head as of now is this.
So I am pointing to the list linked list which is drawn in front of us.
Now I want my new head to be this node in orange.
The newly created node.
Right.
This node.
Effectively, I believe what we should do, what we should do is changing the head is very easy.
So I can just ask my head that, hey, forget this connection.
Please just go and remember that this is the new head.
But in doing so, what I can.
What I will make a mistake is that this whole linked list will get lost.
This whole linked list will get lost.
So I have to make sure that before doing this, before changing my head, I am also making this connection
where I am asking the new node to point to the last head, right?
So that this whole list is also kind of made.
Now you can just think of this intuitively as well.
Let's say if you have this children exam example only where they were playing in the field.
If you have a new student whom you want in the starting, you can remember that, yes, this is the
first student.
But then you will also have to tell that student that, hey, please remember that previously before
you, this was the first student so that you can take the full class along, right?
I hope you are able to visualize the same thing.
If you just remember that he is the new student.
If you just change your head and say this is the new node, then all this information will be lost because
as of now, this information is all because of the head pointer.
Okay great everyone.
So if that's the case, what we have to do is what we just have to do is we have to make sure that we
are able to make two connections.
The first is this one, right?
And the second is this one.
So if you are able to make these two connections and it should be in order as well.
So you cannot say or ask your head to first point here because then this information will get lost.
Right.
Great.
So I hope this is clear.
Now let us also compare this with our array or list.
So let us write this versus array or list.
Now to do the same thing to insert any element in the head or in the first position of my array or list,
we have to do two operations.
First is we have to make sure that we are able to shift everything, or rather first will be checking
capacity.
Capacity should be there, right?
Capacity should be checked.
And second is shifting.
So each and every of these elements right.
Each and every of these elements will have to shift to make space.
And again, if the size is n then I will have to make n shifts.
So the complexity of this whole operation will become o of n.
Okay, now this understanding is going to be a lot helpful to you.
Everyone.
Uh, in the interviews as well, these questions are asked that if you have this kind of an operation,
let's say then which is better linked list or an array?
Okay.
So yeah, let us now do this.
And we are going to find the complexity of uh inserting into linked list as well.
Let us first code this great.
So again from Commons import node and take input better okay.
So first let me create a linked list.
So head is equals to take input better.
In the last class we created this common where I'm keeping all these functions so that I can use them
directly.
Now once I have taken my input then I just want to define insert At head function, which is going to
take the current head right.
And let's say data.
Also, we are giving here only so that we can create our node.
Now once this is done okay.
So as of now I've just defined the function.
It is expecting the head of the linked list the previous head okay.
And the data.
So the input will be this head and data.
Let's say I'm entering 100.
Okay great.
First we have to create a new node.
For this new node have to be created.
So node data.
Okay.
This is going to create a new node.
Once this node is created then let us go back and see before asking our head to point here we should
do this right.
We should say that hey, can you please remember that this is the previous head?
So we have to make sure that the order is always taken care of.
Because if you just jingle the order, then the information will be lost.
So we cannot shuffle the order.
Okay everyone.
So now new node dot next.
Okay.
Equals to head right.
The next thing is I can now ask my head to point to new node.
Straightforward.
I'm just making this second connection now.
Okay.
If this is done then I can just return my head.
So yeah, we have just updated our head.
Uh, one more thing to note here.
Everyone in the functions which you are going to define for your linked list, it's going to happen
that either you are making the change in the linked list, or you have to return the new head.
Okay.
So what I want to explain you is that it can happen.
That function is.
Making the change right in the list.
Making the change.
So let me write it a little bit down so that you can refer it afterwards.
So yeah, let us write it here.
Function can
either just make the change so we are not returning anything.
Just make the change okay.
Or return.
The new return.
The updated head.
Let's say like this.
Return the updated head okay.
So for example, if we have to let's say insert in middle, then you can just give me the head.
And I don't need to give you back the head back.
Right.
Because the head is going to remain same in this function.
Specifically in this function we will have to return the head because it's change.
So anytime the head gets changed okay, we have to make sure that we return the head.
Right.
If no changes are there in the head, then we are still fine with not returning the head.
Okay, so I hope this is clear.
Everyone.
What effectively this means is that you have to see if you want to return with your function or not.
As a thumb rule, I will always suggest that you can return the head so that you don't make these kind
of mistakes.
Right.
But if in any contest or let's say in an interview, if the interview expects that, you will not be
returning anything if the function is written like that.
So you will have to change your approach in a similar manner.
Okay, great.
So here of course, of course you will have to return the head because it is change.
There is no way I can, uh, not return and still get it.
So now let's say head is equals to inserted head and say make it.
I'm passing the head as well.
And 100 is the data.
And what we can do is just to see it quickly.
We can just call print.
I think we have not imported it.
So print will print my linked list and let me give head.
And here again, I'm just calling it after that.
Cool.
So what effectively I have done is I have now defined a linked list.
So it is going to give me a head.
Then I'm printing my linked list.
After that I have inserted at the head position.
If all goes well after calling this function then I will see 100 in the starting.
Okay.
So let us run this everyone.
Let us run this.
Yeah.
Great.
Uh.
One second.
Let me just kill this terminal.
Cool.
So.
Okay.
So it is asking me the value.
Let me enter ten.
Then the next value can be 20, 30, 40 and 50 and minus one.
So this is how we have written our take input function.
Okay.
So see I'm getting the first print as this right and the second print as this.
To make it just a little bit more clear let us do one thing.
Let me just print After inserting okay at head.
Great.
So just let us run this again everyone.
Python.
Second, let me just quickly see what is the working directory CD fourth link list.
And now Python sixth inserted it.
So yeah let me create it.
First is ten 2030 minus one.
So initially it was ten 2030 as we expected.
After that it was changed to 110 2030.
So it seems to work fabulously well.
Right.
We are able to add, just like we discussed into the head and our new head is updated with this as well.
Okay, so great everyone.
I hope this is clear.
Now let's meet in the next video.
Where where we are gonna implement another way of inserting that is to the tail.
Thank you.