Hi everyone.
Let's go ahead and write the next function, which is a function which asks us to insert a given node
at a given position.
So let's call this function insert position.
And a position will be given to us.
And the node which is to be inserted will be given to us.
Now for this we will make use of the insert before or insert b function that we have already written.
Now this function helps us to insert before any given node.
Now the difference over here is we will be given a position right instead of a particular node.
So what we will do is we will traverse the given doubly linked list, and we will identify the node
at the given position.
If that node can be identified then we will pass that node and this node over here to the function that
we have already written, so that the given node over here will be inserted before that particular node,
which we find out at the given position.
So that is one thing.
Now if the position given is greater than like for example over here the possible positions are zero,
one, two, three and four.
Now let's say the given node position is five or 20 or 100.
In that case we will insert the node at the tail and we will make it the new tail.
Now there is also an edge case.
What if the doubly linked list is just empty.
And we are asked to insert the node at a particular position?
In that case, we will just make the given node as the head and the tail, and the empty doubly linked
list will now be turned into a doubly linked list with one node.
So that's a brief outline of what we are going to do.
Now.
First let's create a variable.
Let's call it cur and let that be equal to this dot head.
Now we will go.
Also, we will need a counter, right?
Let's have a counter.
Let counter is equal to zero because we will need to identify the node at the position which is given
to us.
So that's why we will have a counter.
And we will check whether the position is equal to the counter.
And if it's not equal, we will keep incrementing cur to the next node so that when counter becomes
equal to the position, we can identify the node at that particular position.
So for this let's use a while loop.
So while cur not equal to null.
And.
Counter not equal to position.
Why do we have this over here?
Car not equal to null.
Because let's say in this case we have only 012, three, four for valid positions at which we can insert.
Now let's say the position given is 100, right.
So at this stage we will reach over here.
All these will not match.
Then when we reach over here we can identify that we have already come to null.
So we can come out of the while loop.
So that's why we are putting car not equal to null.
All right.
Now if the counter is not equal to the position, what we will do is we will make car equal to car dot
next.
And we will increment the counter.
So counter plus plus.
All right.
So when we come out of this while loop there are two possibilities.
One is let's say counter became equal to position right.
So car is still not equal to null in that case.
Right.
If we are able to identify a valid position.
So let's say if car.
Not equal to null.
So that means counter is equal to position, right?
That means we have identified the node before which we need to insert this given node over here.
Therefore we can just call the function which we have already written insert b and then we can pass
cur as the position node.
And then we pass the given node over here which is the node to be inserted.
So this node will be inserted before cur.
And now cur is the node at the given position.
So yes, we will get the correct answer in this case.
For example, let's say the given position was three.
So 0123.
So cur.
At this point when counter is equal to position, cur will be over here and then we will pass four and
the node, let's say whichever node we want to insert before four.
And then that would be inserted over here.
Let's say it's given five.
So five will be inserted over here.
And then we'll have four.
And then that will point to null.
And that will be taken care by the insert B function which we have already written.
Now let's also now look at the else case.
If this is not true, that means cur is now equal to null.
Now there are two possibilities.
One is that if the position given is like 100 or 20 or something else in this case, right, we have
only four valid positions zero, one, two, three, four.
So if the position given is five or 100 or 10, we will insert it at the tail.
So that is one possibility.
And the other possibility is if the doubly linked list itself is null.
Right.
If if if if it does not have any nodes in this case.
Also, when we set Curry's equal to this dot head at this point itself, cur will be equal to null.
So this will fail and this also will fail right.
So we will come over here.
Now we will check inside this else whether this dot head is equal to null.
This is to see whether the doubly linked list itself is empty, or it does not have any node.
In this case, we just have to set the head and the tail to null to the node which is given to us.
Right.
Because we're inserting that node into the doubly linked list.
All right.
Now what if.
Let's say this is also not true.
So head is also not null and car is equal to null.
So that means the position at which we have to insert the given node is the tail.
Right.
So we just need to go ahead and write the code to insert the given node at the tail.
So it's very much similar to the code that we have already written over here.
So let's go ahead and discuss this.
So the first step will be let's remove the given node from the doubly linked list.
Right.
Why is that so?
Why do we need to do this?
This is to just to ensure that in case the node which we have to insert this node over here, right.
If it's part of the given doubly linked list, then we need to remove it out.
We did the same thing over here also right this dot remove.
And this was the node which we had to insert.
So if the node is part of the doubly linked list first we remove it from where it is.
And then we put it back to the position where we need it to be.
In this case that position is the tail.
All right.
So now we have taken the node out of the doubly linked list.
Now let's place it into the position that is the tail or the end of the doubly linked list.
For this what do we need to do.
We need to make that.
We we need to make a few connections.
Right.
So if this node becomes the tail then its next should be equal to null right.
Because the tail will tails.
Next will be pointing to null and its previous node dot prev should be equal to the current tail, right?
Because we are inserting at the tail.
So these are two changes.
And then the current tail.
The current tail should point to the node.
The tails next should point to the node because we are inserting it after the node.
So this dot tail dot next should be equal to node.
And finally we should change the tail and update it to the node.
Because now this has to be made the node right.
So this has been inserted as the tail.
So this is the tail at this point.
And we are done.
We have successfully inserted the node at the given position.
So we have written the code for that.
Now let's go ahead and test our code.
To test this, let's call it.
And at at the current moment, we have linked the doubly linked list where one is pointing to two,
pointing to three.
That's pointing to four, that's pointing to five.
So this is the current situation.
Let me just quickly write the positions also.
So this is position zero.
This is position one.
This is position two.
Oops.
And this is three.
This is four.
Now let's say we want to shift.
Node four to position one, right.
So what would that look like.
We'll have this is position zero.
We want it at position one.
So over here this is position one will have node four there.
And then we have two three and five.
So this is the expected output.
Let me comment this out.
We want to move for to position one.
So let's call it we have, uh.
Link list doubly dot insert position, and at position one we want node four.
Now let's run it and see what's happening.
All right.
Now let's look at our doubly linked list.
And this is the expectation.
We want it to be 14235.
So let's try.
Let's take a look at it.
We have the head with value one.
It's pointing to four which is what we expected.
And that is pointing to two which is pointing to three.
And that is pointing to five which is again pointing to null.
And it's in two directions.
There is next and previous in all of these cases.
So yes, our code is working.
We were able to successfully insert at position one.
Now what if I wanted to insert at position zero.
Let's again try that.
And let's take a look at our doubly linked list.
So in this case, the new head has to be for.
Yes.
And then that has to point to one which will point to two, that will point to three and that will point
to five and that will point to null.
So yes, that's also working.
Now what if we want to insert at position let's say 20.
All right.
So we have 12345.
And then we are inserting at position 20.
So four should become the new tail right.
So it should be 1235 and four.
So let's run it.
And let's take a look at our linked list.
Doubly so over here we have one which is pointing to two which is pointing to three which is pointing
to five.
And four is inserted at the tail which is working.
And that's what we wanted.
So yes, our code is working.
Now let's take a sample input and quickly walk through the code, because in any interview question
you will have to do this.
Once you have written the code, the interviewer will ask you to walk you to to walk through the code
that you have written and explain what the variables are at each stage.
So let's quickly do that now.