Hi everyone, I hope you have given it a try to code the solution which we discussed in the previous
video.
Now let's code it together in this video.
Now for this we will create a function.
Now we will continue with this same code which we have written right.
We have already created the remove instance over here right instance method.
Now similarly let's write a method insert b okay.
So insert before.
Now the question says that we will be given a node to indicate the position before which the given node
is to be inserted.
So let's call this node position.
So that's the node which will be given to indicate the position.
And then we'll be given a node which is a node we have to insert.
So let's call it call it node insert.
All right.
Now we are going to code the solution.
Now before we go ahead and do the cases which we discussed in the video, there is one edge case which
we need to take care.
What if the given doubly linked list consists of only one node.
And so let's say it's just a linked list like this.
It just has one node one, and to the left of it you have null and to the right of it also you have
null.
Now let's say the position is given as the node with value one, and the node to be inserted is also
the node with value one.
In that case, we don't need to do anything and we just need to return and come out of the function.
Right.
So let's just code that and take that out of the way.
So if this dot head.
Is the given node, which is the node.
Uh, insert right.
We call it node insert.
And if this dot tail.
Is equal to the node insert.
Now in this case, we just have one node in the doubly linked list and the position and the node to
insert is that particular node right.
So in this case we just need to return and we can come out of the function.
All right.
So that's an edge case.
Now if this is not the case we have seen that there are two possibilities.
One if the node to insert is part of the given doubly linked list.
And the second case is where the node to insert is not part of the given doubly linked list.
Right?
So in the previous video we have seen that if we just call the remove function and we remove the node
insert.
Right.
So in this case after this both the cases become the same thing.
Right.
So what happens over here is if the node is part of the doubly linked list we remove it.
Right.
So it's now no longer part of the doubly linked list.
And we have to insert it before the node position which is given.
Now if it was not part of the given doubly linked list, this function will just do nothing, right?
It will just, uh, over here we can see that at the end of remove we have the node which was passed
to the remove function, and its next and previous is pointing to null.
So if the given node was not part of the doubly linked list.
So both of the sides of it are pointing to null.
And we just have that node over here.
So now after calling the remove function we have we have reached a position where there is just one
case.
So the node now is no longer part of the doubly linked list.
And we need to insert that particular node before the node position which is again a node.
So we have to insert the node now before this node position node.
So let's go ahead and do that.
Now remember what we discussed in the previous video.
What we now go what we are going to do now is that we have this node.
So let's write that over here.
And we will set its previous and its next.
So that's the next step that we're going to do.
So let me just write that over here.
We are going to set its previous and its next.
What about its previous.
We're going to set its previous to the.
Node position.
Now again, remember the important thing is that you have to visualize this.
Let's say we are trying to insert three before two.
All right.
So now we have removed three.
So this is no longer over here.
Now we want to insert three over here.
Now what should be its next.
Its next has to be two right.
And what about its previous.
Its previous has to be one.
Right.
So we can say that node to insert dot previous.
And this is the position node.
Right.
So node to insert dot previous is the previous value of the position node.
So we can say that node insert dot prev is equal to node position dot prev.
Again remember the important thing is that you visualize this.
If you can correctly visualize this the code will come naturally.
So we are trying to insert three ahead of two.
So it will become in between 1 and 2 right.
So whatever is previous to three is this node over here.
And at this point this node is the node which is previous to this node.
And this node is the node position.
So that's what we have done over here.
Node insert dot prev is equal to node position dot prev.
Now when three is in between 1 and 2 the next uh node after three should be two right.
Which is the node position itself.
So node insert dot next is equal to node position.
All right.
So we have done this step.
So we have changed the pointers of uh three.
The node with value three.
Right.
Its previous and next pointers are now in the correct position.
Now what we are going to now check is we will check whether the node before which we want to insert
this actually.
Is the head itself or not, right?
Why is that?
So if you are inserting it before the head, then we have to make that node the new head.
Right.
So let's take care of that case.
So let's check that if the position node or that's the node position right.
If node position is the head.
So equal to equal to this dot head.
And we are inserting it before the head right.
So in that case we have to say that this dot head is the node that we are inserting which is node insert.
All right.
Now, if that is not the case, what do we do?
Try to visualize this.
So let's say if we had to insert this node ahead of this node, right.
So we are setting this node to the new head because it's over here.
But so that's what we have taken care over here.
Now what if that is not the case.
So that means we don't need to change the head right.
So let's say again we are taking the case.
Let me just make some space over here.
Let's say we are taking the case where we are changing the position of three.
Remember at every point the important thing is that we visualize this.
So we initially we removed three right?
We removed three.
Now we are trying to insert it over here which is in between 1 and 2.
So it's it's the else part over here.
So we are not trying to insert it at ahead of the head.
All right.
So that's clear.
And we have set its next and previous value already.
Now we have something over here right.
We have something over here.
So what we can do is node dot prev this.
This one over here is one right.
You can see that this is the node position.
This is the node position.
So node dot position dot prev will give us this node over here.
And the next node of this node has to be set to this one over here.
Right three.
So we are trying to make this connection over here at this point okay.
So we can say that node position.
Dot pref dot next is equal to node insert.
All right.
So we have made this connection from 1 to 3 at this point.
All right.
The final step is that we have to change the pointer of node position dot pref.
Right.
So we have inserted three right in between.
So node position is two.
And we need to change this direction also.
So so so far we have done this this direction.
This is done.
Where have we done over here in these two lines.
We have done this direction and this direction.
So this is done.
Now in this case we have checked whether it's the head.
If it's the head, we have set node insert as the head.
And in this case it's not the case.
So we have done node position dot prev which is one dot next to node insert.
So we have done this connection.
Also.
The last thing to do is we have to set node position dot prev is equal to node insert.
That is this connection over here.
This has to be set.
So let's do that now.
So we have node position.
Dot prev.
Is equal to node insert.
All right, so we are done.
And, um.
Okay, I've missed this over here.
Let me add that over here.
It should be this dot remove.
Now let's go ahead and test our, uh, code.
So over here we have our linked list doubly.
Now let's say we want to insert node three ahead of node two.
So let's try that linked list.
Doubly dot insert.
Be.
And let's say the node position is two and the node to insert or in this case node insert is three.
All right.
Now, what's the expectation?
Let's take a quick look.
We have one, two three, four five.
That's the current scenario right at the at the end of this we have created linked list doubly doubly
linked list with 12345.
So after we do this it should take three and it should put it ahead of two.
So that's the expectation right.
So it should be like this where each of these connections are two sided.
Now let's run our code and test whether that's working.
All right, so I'm running the code.
And let's take a look at our doubly linked list.
So we can see over here we have this is the expectation.
We have the head one which is pointing to three.
That's correct.
And that's pointing to two which is also correct.
And that's pointing to four.
And that is pointing to five which is pointing to null.
Right.
So this is correct.
Again, uh, let's take a look whether the pointers are correct in all the directions for node three.
So we have again we have the head which is one.
And that's pointing to three.
What about the next value.
That's two that that's something that we have confirmed.
What about the previous value three is pointing to one.
That is also correct.
So this solution is correct.
Now let's take another example.
Let me clear my console.
And let's say we want to insert a new node.
So over here we have these five nodes.
Let's create a new one which is not part of our part of our current uh doubly linked list.
Let's call it seven.
And that's equal to new node.
And let it have the value seven.
Now let's try to insert this again.
Maybe we can try to insert it ahead of three.
I'm commenting this out so that it's easy for us to test.
So what's the expectation initially, this is the scenario, right?
Of our doubly linked list.
And we want to insert seven ahead of three.
So seven will come over here and it should connect to three.
So this is the expectation.
So let's run it.
And let's see how our doubly linked list looks like now.
We have the head which is has a value one.
So that's pointing to the node with value two, which is pointing to the node with value seven.
And the next value is the node with.
Value three, which is correct.
So this is correct.
And the previous value we can see the previous value also over here.
So two is pointing to seven.
And the previous value of two is one.
Okay.
So we didn't make any changes over here seven as the next value three and seven as the previous value
two.
So this connection is also correct.
So yes our code is working.
Now let's take a sample case and again walk through the code.
Because in any coding interview you will be asked to do that once you have written the code.
So we will do that now.