Hello all and welcome back.
So in this video let us continue our discussion on linked list.
And now let us try to add a node at a given index.
So let's get started.
Now when along with the node I am also given an index, I will be writing a function which takes in
two things.
Right?
So along with it of course, it's going to take the data as well as the index at which I have to add
my node.
So let us now first write what all we know.
So we have a linked list in front of us.
This is the head right.
And I am saying that these are my indexes.
So I am still doing zero indexing only.
Okay.
So I say that ten is at zeroth index, 20 at first, index 30 at second and 40 finally at third.
Okay.
So now if I have to add a node right.
If I have to add a particular node, then what I will be doing is let's say this node gets created here.
And say the node I have to add is 35.
Okay.
And everyone again I'm just taking this as sorted.
There is no any such condition.
I'm just taking it so that it is easier to visualize and understand.
Once I take this at 35 and say I want to add it at third position, then exactly what should happen
is something like this.
So this connection should be like this.
So I am saying that at third position, right?
I should have this node in my final linked list.
So this will be added somewhere in the middle of here.
Right.
So this is where my node will be added because then its index will be three in the resultant linked
list.
Right.
So let us do one thing everyone.
Let us try to just magnify on this particular area.
So what we are going to do is let us just see that exactly what's going to happen if we magnify this,
right?
So yeah, we will have our node here.
We will have our one linked list here.
Sorry one node here.
And we will have another node here.
Okay.
So again the understanding is very important.
The very first thing which I have to do, the very first thing is that we should take a head variable
or sorry take a temporary variable.
And somehow I have to reach I have to reach where my this particular node is.
Second node is just one before the index where I have to add okay.
The reason for that pay attention.
See if I reach on third node.
If I reach on third node then there is no way I can say that hey, add in the back.
We don't have that functionality in linked list, right?
But if I'm able to reach to the second node, then I can say that.
Hey, can you please add this to, uh, let's say next to me, right.
Then again, if this is clear.
So I will repeat what exactly I said.
We have to make sure that somehow, after making a jump, we are able to bring our temp here.
Okay, so let me write this as step as well.
So based on our understanding, we will just make the steps and then just code them.
So first is make a temp.
Make a temp.
Second move temp.
Till index minus one.
Right.
So we are moving temp till index minus one.
Okay so I hope this is clear as well everyone.
Now we are going to take a count variable for that.
So let's say using count variable.
So an extra variable will be took.
Then comes the third part which I'm going to explain to you a lot nicely, which is update.
The connections.
Right.
So I want to now update the connection.
To.
Insert new node.
Right.
To insert the new node I have to make sure that I update the connections.
Right everyone.
So this is where the little bit trick lies.
So pay attention once your temporary is at this particular point.
Once our temporary has reached this point.
Now I have to change some connections.
As of now this is how the pointing is happening.
And after that we don't care what exactly is after 40, we are not going to change that, right?
So this actually is the connection which we should now break, right?
This is the connection which we should now break.
And instead of that, I have to make two more connections.
So let us draw the new connection with green.
This is going to be my first connection.
Let me draw it in only.
So this is going to be my first connection.
And this is going to be my second connection okay.
But again just like we saw when we were inserting okay.
Just like we saw when we were inserting at tail at null, what we have to make sure is that this is
done first.
This thing is done first.
So let me write should be done first.
Using node 30.
Because pay attention everyone if I update this connection first.
If let's say I say that hey delete this connection and update this connection.
Then there is no way I can retrieve this connection back, right?
Then there is no way I can retrieve this connection back.
So let me just remove this connection for the time being so that we don't get confused.
Okay.
So great.
Now pay attention again if I have to add in the middle, if I have to add in the middle first I have
to do this connection.
This I will get.
How can I get this.
So if I just write new node.
Dot next equals to temp dot next right.
So this information is actually present in my temp.
Next.
Great.
So we have to make sure either we save it before updating it or we are updating this first.
Then we will make the second connection.
So then we will make the second connection.
And I'm going to write this at fourth step as well.
Okay.
Order Is very important to everyone.
So it is in green so that you always see and remember this.
Now once this is done, we can make the second connection.
This is going to be easy.
Just temp dot next is equal to new node right.
Just that if we do this first if we do this connection first then we will last this overall information.
And these are the reason like this is the reason I always ask you to make your make diagrams on your
linked list.
Okay everyone.
So I hope with this magnification, the way I have magnified this view, you are able to see how we
have to add that now this will become the in the updated list.
This will be the second node okay.
And this will be the fourth node.
And we have the inserted node at index three okay.
So yeah great everyone I hope with this diagram you are able to understand the same.
Now let's try to code it.
Let's try to code the same I'm inserting it here only so that in the insert linked list file we have
all the functions.
So let me just close this one second.
Yeah.
So I'm writing a function def insert once again insert at index.
Right.
You will be giving me the head the data and the index okay great.
So with this in line the input in line I hope you are able to understand exactly.
Now let us think about what all can happen with respect to index.
So we have taken a common case okay.
We have taken a case where we are adding in the middle.
But with index we don't have any such uh limitation.
Right.
So someone can tomorrow give me the index as zero as well.
So let us write these cases as 11.
Let me just help you visualize this.
So let me write this as edge cases.
First one is if index is zero, this implies we have to.
Add at head right.
If index is zero then we just have to add at head right.
Because this zero this ten.
It will not be my uh if I'm inserting at this head, my new head will be the new node.
So I think this is pretty straightforward.
So let us handle this and write the code for this.
Everyone.
What we can do here is if index is zero then being smart I can just actually call my inserted head function
right.
I can just call this function.
So I'm passing the head and the data.
It's going to take care of that.
Again it's a very easy function.
You can just copy and write the same as well.
Just these lines are there.
Okay.
Great.
So this is handled now let's see and move forward again.
Just this special case we have handled.
Let me just make sure that we are doing it right.
Great.
Okay.
So easy function.
We have this new node and everything is here.
Okay great.
Now moving ahead everyone insert an index.
Now let us see what exactly is going to happen.
Let me just for the time being, keep it down as well.
Cool.
Now the next thing, let me make this new node.
If I'm going to insert it, let me make this new node.
It's going to be node of data right.
And I'm creating a new tab which is head because I don't want to lose out my head.
I don't want to lose out on my head.
And I'm making a count which is zero.
Great.
So once we have done this, what effectively we have done, I have defined my temp.
I have defined my temp, which is currently at my head.
Right?
And the count is zero.
So now let us see what we have to do.
We have to increase our temp.
We have to just keep on increasing our temp till we are able to reach one step before the index we want
to add.
Okay, so let us see this as well.
Everyone.
While the very first condition is that temp should not be null.
Temp is not null.
Now again you can write this like it is.
Well like temp is not null.
Okay so not equals to and this is not both works.
So this is the first condition.
Like what if we have none.
We cannot then move the next temp right.
So that is the very first condition.
And I think if I say count is less than index minus one okay.
Because you have to stop one step before I can just keep on increasing my temp.
So temp is equals to temp dot.
Next.
And I can say that count also can be increased.
So here count plus equals one okay.
So again till in this step I have just defined my temp to be at head and count.
I have taken zero.
Now, based on our discussion, I am now just trying to move my temp.
But the first thing I have to make sure is that temp should not become none because else then where
it will move, right?
Same condition we used to have in the in take input function when we used to go to tail, right.
If it becomes none then how will you move it.
And the second is that count should be less than index minus one because I have to reach to this particular
node, not this node.
Okay.
Great.
So if this is clear then let us see if I have done this.
If I have done this then there are I have reached to this particular position.
Okay.
These are the two steps which I have to do.
Now we have already written the steps right.
So if you will see, these are just the steps I need to perform now based on our understanding we already
understood them.
And if I can just do them, do like write these codes, it should be fine, right?
So if sorry, no, if my new node dot.
Next I have to add temp dot next.
So now I have made sure that whatever was there in my linked list, I have just saved all of that.
Okay, and temp dot next equals new node.
I have made the connections.
These are the exact two things which we talked about.
New node.
Next is equals to temp dot next.
So that this overall connection which was there it doesn't get lost.
First I am connecting to this.
Now we can delete that connection.
The one which was above this particular one connection.
We should be good to break okay.
And let us join this again.
The order is very important.
That's why I have written one and two here.
And in the fourth step also you will see that order is very important.
Okay great.
And I should just go to return my hit.
Return hit.
Okay.
Great.
So now let us call this everyone.
Oh yeah.
Head is equals to insert at index.
Sorry insert at index.
Okay.
And let us use.
Head.
And let us just try to copy this example only.
So 1020 3040 I will try to add 35 at third index okay.
And then yeah I should be just print after inserting at index.
And I can just then call print underscore L mailing list okay everyone.
So we have just written the code based on our discussion.
This is the whole code.
We will see if it works or not okay.
If there is any problem or not.
And we are just printing it.
Let me I think we have another line here.
Let me remove this should be fine.
Okay.
Great.
So yeah let us run this.
Cool.
So it is asking me for the value.
So ten 20, 30 and 40.
After that, it's minus one and it seems to work.
It seems to work fabulously well.
Okay, we are seeing this is added into middle.
Okay, so just because this is a very important part like this particular function, I would like to
explain this visually to you as well again.
Okay so let us go to Python Tutorial one.
And here I am just going to yeah I think we can just do it.
Great.
So I think all these functions are here.
So we should be good to all.
Just one change I have made here everyone.
So instead of just giving this input every time I have just asked that hey, take the values from this
list.
Okay, so we are creating the same thing.
We are just creating the same thing.
Okay, but this time I won't have to give so many inputs.
Okay, so how we have done this instead of asking user from the value, I am passing this values in
a for loop and giving this particular list.
Great.
So yeah, I think this is fine.
Just let me have this head which we can use.
So take input better is going to get called.
Here we have the linked list which we will get.
And then we are calling inserted index.
Great.
So let us quickly visualize this everyone.
Yeah.
Cool.
So it seems to work for the time being.
Let me just run this quickly.
Okay.
So it's going to take this input better.
Again we don't have to input anything.
That's the good part.
And we have seen this.
So we know how this is going to get created.
So let me jump and go till we come out with our linked list.
Okay.
So let us go forward.
Great.
So I think yeah.
See everyone we have got our linked list.
This is how the linked list looks right.
So as of now yes, this is all good.
Now let me move forward.
Now I'm saying insert at index and I'm calling this particular function.
I've defined this function.
And now I'm calling this in my insert at index.
Let me try to zoom out if it works.
Yeah.
So I think that this should be a workable it should be visible.
If I zoom it out I'm calling insert at index okay.
This particular code.
Pay attention everyone.
This is the code which you have written with data is equal to 35 and index at three.
So now a good way.
We should also mention the index just like we discussed.
Zeroth index first index.
Second index.
Third index fourth index.
Right after this I should have it where 40 is.
That is what we have seen.
So pay attention everyone.
Now let us move forward.
First it's going to check if index is zero.
Don't think index is zero right.
So we can move forward.
Great I'm going to create a new node.
A new node is going to get created.
You already know how that's done.
So yeah a new node is going to get created in the memory which is like this okay.
I'll see what I have to do.
What I have to do is we just have to make sure that somehow we are able to add this here, and this
is the connection which you want to make.
Okay.
So we are going to see how it's going to get made.
No worries.
This is the code again if you pay attention temp head we are creating a new temp which is head and I'm
making a count which is zero.
Okay cool.
Now I'm running my loop while temp is not none and count less than index.
Okay, so let us move this everyone temp initially is head, let us move forward.
Temp moves to this thing and I'm going to increase my count.
It's going to become one okay cool.
Again let us move this temp.
Move to this end count will become two.
Pay attention.
How index minus one I have used.
Okay.
Once we come here.
Once we come here we are on the third index count is going to get two.
And since count is less than index minus one okay.
This condition gets false because two is not less than two, right?
It is equal.
So that is what is happening here.
Count less than index minus two.
This condition is very important to understand.
This is something which you are also going to write in.
Lots of questions going forward.
So index minus one will become two.
And this count when it become two right.
When it is two then we have reached here.
So we have to make sure that see this is less than this condition is false okay.
That's why we come out of this loop.
And if you will see, my temp is actually pointing where I need it to point.
Okay, everyone.
So I hope this is clear.
Now after that, we just have this particular temp with us and we are going to go forward.
So now I'm saying new node dot next.
So new node dot next.
Connect this connection right.
Make this connection.
So before breaking this connection because this overall connection I just have in temp right now.
I'm going to change the connection.
See how it's going to happen.
Now comes the point where I'm going to make this connection instead and delete this.
Okay, cool.
So let us do this.
See how it got deleted.
And we are able to see how it got added in the middle.
Again this index and everything is very important.
That's why I'm making sure that you understand this visually.
Yeah I think now it's all good.
So if I just move forward we have our head here and you can see how your linked list is.
Right.
It actually have added this node in the middle.
Okay great everyone.
So yeah I think this is fine.
If we just move forward we can print it right towards the end.
We will be able to print everything.
Okay great.
All so yeah we can see that it is working.
Now let's go back to our code.
Few things we have to do here.
Uh, just for one thing, which I want to show you.
Let's say if I'm adding ten, 20, 30, 3040.
Minus one.
Okay.
It is able to add.
Now what if I give this index as let's say 100?
What's going to happen then?
Let's try to run this right.
This is some case we which we have not discussed.
So I will repeat the case for you.
What if the index which you are giving me this index, it is greater than the length of my linked list.
So this index will run from zero to n minus one.
Right.
But if you give me the index which is greater.
Then what is going to happen.
Let's see if.
See that everyone minus one and I'm getting some error.
Non-type object has no attribute.
Next.
Okay, so what happened here?
Let us understand that if actually we can go to the code and understand this.
See, when this code was running we had two condition through which it can stop.
The first one was till ten becomes one second was of count less than index.
Now when you write this 100, of course we will not traverse till hundredth index, right.
We don't have that okay.
so if in this list you ask me that, hey, take this temp and move to the 10th index.
I will just use none.
First I will reach none first, right?
So to handle this condition, we have to actually add another if condition to make sure that this particular
code works every time.
So if temp is none I can just print index out of bounds.
Please check index and I can just return my head as it is.
Okay, so I hope this is clear to everyone why this is going to happen.
It's just same as if you have ten students and new student I am asking you to insert at 15th position.
Of course that is not possible, right?
That is not possible.
Now you should be aware of these kind of edge cases.
And I'm going to write this as well here.
These are the things which are tested in an interview.
Right.
So when you are giving your interview these are the things which gets tested if index is greater than
length, right?
We have already seen how to calculate length.
This implies out of bounds error right?
So cool everyone let us just now run this again ten 2030 and minus one.
We can see that it is saying index out of bounds.
Please check the index.
And we are able to see the list as it is just one more test case.
End case which I would like to edge.
Case sorry, which I like to check is if it is 1020, 30, 40 okay.
And I want to now insert at tail.
So at tail the index is going to be four I guess.
Right.
So index is going to be four here.
So let us see that if that case is also handled let me just add four here.
Right.
Let us just clear this and run it again 1020 3040 minus one.
And we can see that this case is handled in our code.
The reason is same.
We just reached to 40 till now and we are just doing the same thing.
Okay, so it is getting added.
In the end.
The code which we have written it is safe from all the errors.
These are the major edge cases.
So I will write this as well.
Okay pay attention everyone.
Third, if index equals to length that is add at end okay.
So all these I have done because you will have to run this very nicely.
This overall understanding of entering in the index that is going to help you a lot when you do questions
going forward.
So that's why we have spent so much time on it.
Please make sure that you understand it.
Draw your linked list a lot of times and this will be a lot clearer.
Okay, cool.
Then everyone let's meet in the next video then.
Thank you.