Welcome back.
Let's now go ahead and discuss how we can solve this question.
Now there are two possibilities.
The node which is given to us could be either a new node which is not part of the existing doubly linked
list, or it can be an existing node in the doubly linked list, and in which case we have to shift
its position.
So these are two possibilities.
Now these two possibilities will be handled by the existing method that we have written which is insert
before write.
So how was it handled.
It was handled because if it's an existing node we're just removing it first.
Right.
So we are removing it for removing it from the doubly linked list.
And then these two cases will become the same case.
All right now let's take a sample doubly linked list.
So we have 123 and four.
Now this is already handled with our existing function insert before a given node.
So we are going to make use of that same node.
And then we are just trying to have an extra function which will make use of the previous instance method
that we have used.
And we will try to solve the different possibilities.
Now what are the possibilities?
As we have seen in the case of the test cases, one possibility is that the position may be zero or
the head right.
In this case the position is zero.
Another possibility is that over here in this doubly linked list over here, the positions one, 2 or
3 could be given.
And another possibility is that a position is mentioned which is greater than three, something like
100.
And we have clarified from the interviewer that in that case we will just insert the node at the tail.
All right.
Now let's go ahead and explore these three possibilities.
Let's say the node is five.
And let's say the first case.
Let's look at the first case where we want to insert this particular node at position zero.
Now if we want to do this then over here we have our doubly linked list.
All we are going to do is we are going to call our function insert B right insert before.
So we are going to call the same function which we have previously written.
And then we will just identify that at index zero we have node one.
So we are going to pass node one and then node five which is the node that we want to insert at position
zero.
So in this way we will solve the first case.
And we are just trying to reuse maximum of the code that we have already written.
Now let's proceed.
What if we want to insert at positions one, 2 or 3?
In these cases we will just have to identify the node at that particular position.
Right.
So we need to find the node at position.
For this we will use a counter and we will traverse the given doubly linked list.
So initially the counter will be zero.
And then we will keep moving the counter and a particular current node.
We will keep moving the current node along with the counter till the counter is equal to position.
So in that way we will find the node at the given position.
And then again we will call the insert function.
And we will pass the node at that particular position and the node which we want to insert which is
this node over here.
And then finally again that's the only way.
Right.
So there is just one way of doing that.
We have to traverse the array for this.
And then finally we have this third case over here.
If you want to insert at a position which is greater than three for example 100.
In that case we will just make the given node to be the tail.
So for this we will keep traversing the array.
And if we reach null if the current node becomes null before we reach a case where the counter is equal
to the given position, then we can understand that the position which is given to us is greater than
the last index of the doubly linked list, and in that case we will insert the node at the tail.
So we'll have five over here.
Now its previous and its next connections have to be made.
All right.
So we'll need to identify the previous node.
So we have to connect the previous of the node which is to be inserted to the previous tail.
And then its next has to be connected to null.
And then this connection over here has to be severe.
And it has to be connected to the new node that we have just now inserted.
And then the new node has to be made the tail.
So that is how we will solve this question.
Now you can see that it's pretty much easy because we have already written this function.
And we are going to make use of this function in as many cases as possible.
Now let's take a look at the time and space complexity of this solution.
The time complexity is going to be O of N in the worst case, where we are going to insert the particular
node which is given to us at a position which is greater than the size.
Now we have to identify this.
So that's why we have to traverse the doubly linked list once to identify that yes, we have reached
null and we have not yet reached a situation where the counter is equal to the position.
So that means that the position is greater than the size.
So we don't know initially, if we are not tracking the size, then we won't know initially itself that
the position is greater than or equal to size.
So that's why the in the worst case the time complexity is going to be O of n.
And if we are inserting at the head, that is, if the position is zero, then we can just insert at
constant time.
So that's an O of one operation.
Now the space complexity is going to be O of one because we are not using any extra space.