1 00:00:01,070 --> 00:00:01,820 Hi everyone. 2 00:00:01,820 --> 00:00:07,970 So we have completed the first part of this question where we wrote a function where the input is a 3 00:00:07,970 --> 00:00:12,650 node to be removed, and we removed that particular node from the doubly linked list. 4 00:00:12,650 --> 00:00:13,070 All right. 5 00:00:13,100 --> 00:00:15,350 Now let's go ahead and do the second part. 6 00:00:15,350 --> 00:00:16,220 Let's read it. 7 00:00:16,220 --> 00:00:22,010 Insert a node before a particular node, both the node to be inserted and the node before which the 8 00:00:22,010 --> 00:00:24,770 insertion is to happen will be given as input. 9 00:00:24,770 --> 00:00:30,230 If the node to be inserted is part of the linked list, then shift its place to the desired location 10 00:00:30,230 --> 00:00:35,960 and if the node to be inserted is a new node, then insert the new node at the place desired. 11 00:00:35,960 --> 00:00:37,640 So what does this mean? 12 00:00:37,640 --> 00:00:42,470 Let's say we have a sample doubly linked list over here 123. 13 00:00:42,560 --> 00:00:48,470 And let's say we are asked to insert node three ahead of node two. 14 00:00:48,500 --> 00:00:49,850 So this points to null. 15 00:00:49,850 --> 00:00:51,320 This also points to null. 16 00:00:51,320 --> 00:00:51,770 All right. 17 00:00:51,770 --> 00:00:53,750 Now there are two possibilities over here. 18 00:00:53,750 --> 00:00:56,450 It says if the node to be inserted is part of the linked list. 19 00:00:56,450 --> 00:00:59,240 So in this case let's say three is part of the linked list. 20 00:00:59,240 --> 00:01:02,600 And three we are asking to insert three ahead of node two. 21 00:01:02,630 --> 00:01:04,190 So that's one possibility. 22 00:01:04,190 --> 00:01:07,160 So in this case we need to shift its place. 23 00:01:07,160 --> 00:01:09,080 So it should be placed ahead of two. 24 00:01:09,110 --> 00:01:10,310 It should be placed over here. 25 00:01:10,310 --> 00:01:14,750 And there is also a possibility where the node to be inserted is a new node. 26 00:01:14,750 --> 00:01:17,060 Let's say it's a node with value eight. 27 00:01:17,860 --> 00:01:18,250 All right. 28 00:01:18,250 --> 00:01:21,190 And let's say it's to be inserted ahead of node two. 29 00:01:21,220 --> 00:01:23,440 So in this case we have to place it over here. 30 00:01:23,440 --> 00:01:25,360 So there are these two possibilities. 31 00:01:25,360 --> 00:01:26,710 So this is the question. 32 00:01:26,710 --> 00:01:32,470 Now remember in the interview if you are getting this question always ensure that you ask sufficient 33 00:01:32,470 --> 00:01:37,120 clarifying questions so that you are thoroughly you thoroughly understand the question, and you are 34 00:01:37,120 --> 00:01:40,090 sure that you and the interviewer are on the same page. 35 00:01:40,090 --> 00:01:41,500 Now it's over here. 36 00:01:41,500 --> 00:01:46,780 It's pretty much straightforward, but possibly you could ask a question that you could ask is will 37 00:01:46,780 --> 00:01:51,520 it be mentioned if the node to insert is part of the doubly linked list or not? 38 00:01:51,520 --> 00:01:57,010 Like for example, over here we said that three was part of the doubly linked list, and in this case, 39 00:01:57,010 --> 00:01:59,500 eight was not part of the doubly linked list. 40 00:01:59,500 --> 00:02:01,300 Let's say it's pointing to null on both sides. 41 00:02:01,300 --> 00:02:02,680 So it's just a node. 42 00:02:02,680 --> 00:02:04,300 Now do I know this? 43 00:02:04,300 --> 00:02:05,440 Will this be an input. 44 00:02:05,440 --> 00:02:10,810 Now let's say to this question the interviewer says no, your code has to take care of it. 45 00:02:10,810 --> 00:02:16,840 So it will not be given whether the node which is mentioned is part or not part of the doubly linked 46 00:02:16,840 --> 00:02:17,230 list. 47 00:02:17,230 --> 00:02:17,950 All right. 48 00:02:18,310 --> 00:02:21,100 Now we've got a good idea of the question. 49 00:02:21,100 --> 00:02:26,110 Now let's look at a few test cases to understand what is to be done. 50 00:02:26,110 --> 00:02:26,440 Again. 51 00:02:26,440 --> 00:02:29,020 Remember test cases are just different inputs. 52 00:02:29,020 --> 00:02:33,040 And we write out the expected output for those inputs. 53 00:02:33,040 --> 00:02:36,040 And it's helpful to identify edge cases. 54 00:02:36,040 --> 00:02:40,720 And in the interview you can always ask the interviewer thank you for the clarifications. 55 00:02:40,720 --> 00:02:46,240 Is it okay if we come up with the test cases together and you can work with the interviewer so that 56 00:02:46,240 --> 00:02:48,550 you're very clear with the expectation? 57 00:02:48,550 --> 00:02:50,920 Now let's go ahead and write a few test cases. 58 00:02:50,920 --> 00:02:55,540 Now, let's say the doubly linked list which is given to us is this one over here. 59 00:02:55,540 --> 00:02:58,900 And we are asked to insert before node two. 60 00:02:58,900 --> 00:03:04,420 So before this node over here and let's say the node to be inserted is node three. 61 00:03:04,420 --> 00:03:07,090 This one this node over here the node with value three. 62 00:03:07,090 --> 00:03:11,500 So in this case the given node is part of the doubly linked list. 63 00:03:11,500 --> 00:03:13,870 And what's the output that would be expected. 64 00:03:13,870 --> 00:03:15,460 We need to shift the position right. 65 00:03:15,460 --> 00:03:20,560 So the expected output would be this over here where you can see that the position of three has been 66 00:03:20,560 --> 00:03:22,630 changed and it's placed over here. 67 00:03:22,630 --> 00:03:23,980 So we get this over here. 68 00:03:23,980 --> 00:03:27,760 Now another possibility is let's say again we have our doubly linked list. 69 00:03:27,760 --> 00:03:31,870 And we are asked to insert before node two, node five. 70 00:03:31,870 --> 00:03:37,630 So this node over here, the node with value five is not part of the given doubly linked list. 71 00:03:37,630 --> 00:03:41,920 So if we insert it before node two it would be inserted over here. 72 00:03:41,920 --> 00:03:44,170 And the output would be this. 73 00:03:44,170 --> 00:03:44,680 Right. 74 00:03:44,680 --> 00:03:50,080 We'll have this doubly linked list where you can see that five is placed between 1 and 2. 75 00:03:50,110 --> 00:03:53,320 So these are generally the two possibilities. 76 00:03:53,320 --> 00:03:57,190 Now we could also be given node one which is the head. 77 00:03:57,190 --> 00:04:00,550 And we may be asked to insert something ahead of node one. 78 00:04:00,550 --> 00:04:00,850 Right. 79 00:04:00,850 --> 00:04:02,860 So let's say that's another possibility. 80 00:04:02,860 --> 00:04:04,930 So let's say we are given before node one. 81 00:04:04,930 --> 00:04:06,100 So this is the position. 82 00:04:06,100 --> 00:04:08,230 And let's say again there are two possibilities. 83 00:04:08,230 --> 00:04:09,520 We could be given node three. 84 00:04:09,520 --> 00:04:13,390 So then we need to shift the position of node three to the head. 85 00:04:13,390 --> 00:04:19,150 Or we could be given node five or let's say node eight or a different node which is not part of the 86 00:04:19,150 --> 00:04:19,900 doubly linked list. 87 00:04:19,900 --> 00:04:22,510 So in that case we have to make it the new head. 88 00:04:22,510 --> 00:04:22,810 Right. 89 00:04:22,810 --> 00:04:27,460 So in these two cases we can see when we are inserting ahead of the head right. 90 00:04:27,460 --> 00:04:28,330 This is the current head. 91 00:04:28,330 --> 00:04:34,060 So if we are inserting before the current head then whatever we are inserting has to become the new 92 00:04:34,090 --> 00:04:34,300 head. 93 00:04:34,300 --> 00:04:36,340 So that is another thing to be kept in mind. 94 00:04:36,340 --> 00:04:38,320 So that's another important test case. 95 00:04:38,320 --> 00:04:41,440 Now if you are inserting just to check, what about the tail? 96 00:04:41,440 --> 00:04:44,170 If you're inserting before the tail, nothing happens, right? 97 00:04:44,170 --> 00:04:47,590 It's just one similar to the two cases that we have discussed over here. 98 00:04:47,590 --> 00:04:52,240 We will be just placing it over here and making the respective connections. 99 00:04:52,810 --> 00:04:55,870 All right, so we have got a good idea about the question. 100 00:04:55,870 --> 00:04:59,500 And we have written out the different possibilities in terms of test cases. 101 00:04:59,500 --> 00:05:03,130 And at this point you and the interviewer are on the same page. 102 00:05:03,130 --> 00:05:08,650 Now it's time to brainstorm how to solve this question, and let's do that in the next video.