Hi everyone.
So we have got a good understanding of the question and in this video let's try to think through how
to solve this question.
Now we have seen that there are two possibilities.
One is that the given node is part of the doubly linked list.
And there is another possibility where the given node is not part of the doubly linked list.
Now there is an interesting thing that we can notice over here.
Let's say that this is the case where the given node is part of the doubly linked list, and previously
we have written a function where if we input a node, that function removes that node from the doubly
linked list.
Let's say we are passing this particular node to that function which we have written.
Write the remove function.
So what would be the case after we run that we call that function.
This would be taken out of the doubly linked list.
Right.
So we would have this scenario over here where we have one two and four and three is removed out.
Right.
And then we have three separately.
We have three taken out now when you compare this scenario and this scenario these were the two scenarios.
One is the scenario where the given node is part of the doubly linked list.
This is the scenario where the given node is not part of the doubly linked list.
But in the first case, after we have called the remove function, we can see that these two scenarios
are now one and the same.
Right over here we can see we have a doubly linked list and we have node five which is not part of it.
Similarly over here also we have a doubly linked list and we have node three because we have removed
it.
It is no longer part of the doubly linked list.
Now it's just one and the same.
Right.
So we have converted both the cases into the same case by calling the remove function, which we have
already written.
All right.
So this is step one.
We will call the remove function.
And if the node which is given to us is part of of the doubly linked list, we will take it out of the
doubly linked list.
Now again remember if the node which is given is not part of the doubly linked list, and if we call
the remove function, it does not do anything right.
It will just make sure that the node in this case node five, is pointing to null in both the directions,
so it will not do anything, and it will ensure that in case this node was pointing somewhere else,
we will make it point to null in both the cases, both the directions.
So that's it.
So step one is to call the remove function irrespective.
So we don't know whether the given node is part of the doubly linked list or not.
So that's the clarification that we've got from the interviewer.
So irrespective of that like it doesn't matter whether it's part of the doubly linked list or whether
it's not part of the doubly linked list, we will call the remove function and we will pass the given
node to us.
And we will ensure that if it is part of the doubly linked list, it is removed.
So it will become like this.
Now we are dealing with the same scenario right now.
Let's proceed.
So we are now at this point where we have a doubly linked list, and we are given a node which is not
part of the doubly linked list.
Why is that?
So in case it's part of the doubly linked list, we have called the remove function.
And we have removed it outside.
So let me just write five over here.
And it's given that we need to insert this node ahead of two.
Right.
So it should be inserted over here.
Now there are two possibilities.
Again I'm just taking a generic scenario.
And we will look at the case where we are.
We have to insert ahead of the head before the head.
So those are the two cases.
Now let's say it's not the head.
So we have one over here and we have no two over here.
Now this is the given node and this will be the previous node.
So this is node dot previous.
Right now you can see that this node over here at at the current moment is pointing to null right in
both directions left and right or previous and next right.
So previous and next is pointing to null.
So what we can now do is let's make this point to these two nodes over here.
Again.
Remember don't think of it in terms of code like Node.prev or node.
So I'm just I've just written it so that it becomes familiar to you to you.
But the important thing is that you visualize this.
Right?
So once you're very clear with what you want your code to accomplish, it's very easy to go ahead and
write out that code.
So we are now going to change these two directions which were pointing to null.
We are going to change these two and make them to point to this node and this node.
Right.
So we have node.
So we make this node.
This is the let's call node insert.
Let me call this node insert.
So node insert dot.
Next will be node and node insert dot prev will be node dot prev.
So I'm connecting these two connections right.
So that can be done without any danger of losing anything or doing anything wrong.
So there is nothing to be checked whether it's the head or not.
Like let me again draw that conditionals over here.
Now again let's say we did not have this node one over here.
And again we want to insert node five ahead of node two.
Right.
So we have five again over here.
In this case also you can see that the same.
Thing can be done right.
We can connect these two.
That is again we have node over here.
This is node and this is node dot pref.
Right.
So whether it's the head, whether we are inserting before the head or not, it does not matter in both
the cases we can.
So let me call this node insert.
Let me just write it again so it's easier to speak about it.
But as I speak keep visualizing it.
That's the important thing.
So node insert dot.
Next is node in both the cases and node insert dot prev is node dot prev over here.
And node.prev in this case is null right.
So in both the cases we make these two connections.
So that can be done straight forward.
Now we need to see whether we are dealing with this scenario or this scenario.
In this scenario over here we are trying to insert before the head.
Right.
So in that case we need to make this node over here the new head.
All right.
Now, if we are not inserting before the head, like for example, over here.
So we don't need to make it the new head and we have something over here, right?
In this case, the previous node, the node.prev gives us null.
Right.
But in this case node dot prev is a node.
Because this node over here is not the head, this is not the head, right.
So in this case, when it is not the head, when we are not inserting before the head, we can do no
dot prev dot.
Next that is this connection over here.
Right?
We can disconnect this connection and make it connect to node insert.
So that's the next step.
So again this the first step was to do these two connections.
That was irrespective of whether we are inserting before the head or not.
So this red this these red arrows.
That was the first step.
Right.
So these two red arrows.
Now the second case is the blue arrows.
So we check whether it's the head.
If it's the head we make this the head.
If it's not the head we disconnect this connection and we make this connection right.
So how do we do this.
No dot dot.
Next is node insert.
So we change this connection to this one over here.
Now what's remaining.
You can see that over here we have a connection right.
This connection should no longer point to null but it should point to this node over here.
Right.
And the same thing is also over here this this connection, which is the same connection which we have
over here.
So this connection or this connection should no longer point to here or here, but rather it should
point to node insert.
So let's do that.
We disconnect this connection and make this connection.
How do we do that.
No dot prev is equal to node insert.
The same thing is applicable over here.
Also node dot prev is equal to node insert.
All right.
And we are done with our solution.
You can see that we have null.
Then one then five two and three four and null right.
Which is correct.
And in this case where we were inserting before the head we have null.
Then we have five, two, three, four and null.
So yes we have our solution.
All right.
So now let's quickly look at the complexity analysis of this solution.
Now the time and space complexity of this solution is O of one or this solution.
This method runs in constant time and space.
Why is that.
So you can see that we are not traversing the doubly linked list, right?
The node is given to us as input and the position node is also given to us.
So there is no need to traverse the doubly linked list, and hence this solution runs in constant time
and space.