Hi everyone.
So we have completed the first part of this question where we wrote a function where the input is a
node to be removed, and we removed that particular node from the doubly linked list.
All right.
Now let's go ahead and do the second part.
Let's read it.
Insert a node before a particular node, both the node to be inserted and the node before which the
insertion is to happen will be given as input.
If the node to be inserted is part of the linked list, then shift its place to the desired location
and if the node to be inserted is a new node, then insert the new node at the place desired.
So what does this mean?
Let's say we have a sample doubly linked list over here 123.
And let's say we are asked to insert node three ahead of node two.
So this points to null.
This also points to null.
All right.
Now there are two possibilities over here.
It says if the node to be inserted is part of the linked list.
So in this case let's say three is part of the linked list.
And three we are asking to insert three ahead of node two.
So that's one possibility.
So in this case we need to shift its place.
So it should be placed ahead of two.
It should be placed over here.
And there is also a possibility where the node to be inserted is a new node.
Let's say it's a node with value eight.
All right.
And let's say it's to be inserted ahead of node two.
So in this case we have to place it over here.
So there are these two possibilities.
So this is the question.
Now remember in the interview if you are getting this question always ensure that you ask sufficient
clarifying questions so that you are thoroughly you thoroughly understand the question, and you are
sure that you and the interviewer are on the same page.
Now it's over here.
It's pretty much straightforward, but possibly you could ask a question that you could ask is will
it be mentioned if the node to insert is part of the doubly linked list or not?
Like for example, over here we said that three was part of the doubly linked list, and in this case,
eight was not part of the doubly linked list.
Let's say it's pointing to null on both sides.
So it's just a node.
Now do I know this?
Will this be an input.
Now let's say to this question the interviewer says no, your code has to take care of it.
So it will not be given whether the node which is mentioned is part or not part of the doubly linked
list.
All right.
Now we've got a good idea of the question.
Now let's look at a few test cases to understand what is to be done.
Again.
Remember test cases are just different inputs.
And we write out the expected output for those inputs.
And it's helpful to identify edge cases.
And in the interview you can always ask the interviewer thank you for the clarifications.
Is it okay if we come up with the test cases together and you can work with the interviewer so that
you're very clear with the expectation?
Now let's go ahead and write a few test cases.
Now, let's say the doubly linked list which is given to us is this one over here.
And we are asked to insert before node two.
So before this node over here and let's say the node to be inserted is node three.
This one this node over here the node with value three.
So in this case the given node is part of the doubly linked list.
And what's the output that would be expected.
We need to shift the position right.
So the expected output would be this over here where you can see that the position of three has been
changed and it's placed over here.
So we get this over here.
Now another possibility is let's say again we have our doubly linked list.
And we are asked to insert before node two, node five.
So this node over here, the node with value five is not part of the given doubly linked list.
So if we insert it before node two it would be inserted over here.
And the output would be this.
Right.
We'll have this doubly linked list where you can see that five is placed between 1 and 2.
So these are generally the two possibilities.
Now we could also be given node one which is the head.
And we may be asked to insert something ahead of node one.
Right.
So let's say that's another possibility.
So let's say we are given before node one.
So this is the position.
And let's say again there are two possibilities.
We could be given node three.
So then we need to shift the position of node three to the head.
Or we could be given node five or let's say node eight or a different node which is not part of the
doubly linked list.
So in that case we have to make it the new head.
Right.
So in these two cases we can see when we are inserting ahead of the head right.
This is the current head.
So if we are inserting before the current head then whatever we are inserting has to become the new
head.
So that is another thing to be kept in mind.
So that's another important test case.
Now if you are inserting just to check, what about the tail?
If you're inserting before the tail, nothing happens, right?
It's just one similar to the two cases that we have discussed over here.
We will be just placing it over here and making the respective connections.
All right, so we have got a good idea about the question.
And we have written out the different possibilities in terms of test cases.
And at this point you and the interviewer are on the same page.
Now it's time to brainstorm how to solve this question, and let's do that in the next video.