1
00:00:00,680 --> 00:00:06,020
Hi everyone, I hope you have given it a try to code the solution which we discussed in the previous

2
00:00:06,020 --> 00:00:06,590
video.

3
00:00:06,620 --> 00:00:09,500
Now let's code it together in this video.

4
00:00:09,500 --> 00:00:11,780
Now for this we will create a function.

5
00:00:11,780 --> 00:00:15,860
Now we will continue with this same code which we have written right.

6
00:00:15,860 --> 00:00:20,750
We have already created the remove instance over here right instance method.

7
00:00:20,750 --> 00:00:26,030
Now similarly let's write a method insert b okay.

8
00:00:26,180 --> 00:00:27,590
So insert before.

9
00:00:27,590 --> 00:00:33,380
Now the question says that we will be given a node to indicate the position before which the given node

10
00:00:33,380 --> 00:00:34,490
is to be inserted.

11
00:00:34,490 --> 00:00:37,160
So let's call this node position.

12
00:00:37,160 --> 00:00:40,910
So that's the node which will be given to indicate the position.

13
00:00:40,910 --> 00:00:44,330
And then we'll be given a node which is a node we have to insert.

14
00:00:44,330 --> 00:00:46,580
So let's call it call it node insert.

15
00:00:47,180 --> 00:00:47,810
All right.

16
00:00:47,810 --> 00:00:50,780
Now we are going to code the solution.

17
00:00:50,780 --> 00:00:57,260
Now before we go ahead and do the cases which we discussed in the video, there is one edge case which

18
00:00:57,260 --> 00:00:58,250
we need to take care.

19
00:00:58,250 --> 00:01:03,830
What if the given doubly linked list consists of only one node.

20
00:01:03,830 --> 00:01:08,300
And so let's say it's just a linked list like this.

21
00:01:08,330 --> 00:01:12,920
It just has one node one, and to the left of it you have null and to the right of it also you have

22
00:01:12,920 --> 00:01:13,280
null.

23
00:01:13,280 --> 00:01:19,040
Now let's say the position is given as the node with value one, and the node to be inserted is also

24
00:01:19,040 --> 00:01:20,030
the node with value one.

25
00:01:20,030 --> 00:01:24,920
In that case, we don't need to do anything and we just need to return and come out of the function.

26
00:01:24,920 --> 00:01:25,220
Right.

27
00:01:25,220 --> 00:01:28,340
So let's just code that and take that out of the way.

28
00:01:28,340 --> 00:01:31,280
So if this dot head.

29
00:01:32,320 --> 00:01:35,770
Is the given node, which is the node.

30
00:01:36,010 --> 00:01:37,000
Uh, insert right.

31
00:01:37,000 --> 00:01:38,410
We call it node insert.

32
00:01:38,410 --> 00:01:41,740
And if this dot tail.

33
00:01:42,950 --> 00:01:44,810
Is equal to the node insert.

34
00:01:45,020 --> 00:01:51,470
Now in this case, we just have one node in the doubly linked list and the position and the node to

35
00:01:51,470 --> 00:01:53,060
insert is that particular node right.

36
00:01:53,060 --> 00:01:57,830
So in this case we just need to return and we can come out of the function.

37
00:01:57,830 --> 00:01:58,370
All right.

38
00:01:58,370 --> 00:01:59,750
So that's an edge case.

39
00:01:59,750 --> 00:02:03,860
Now if this is not the case we have seen that there are two possibilities.

40
00:02:03,860 --> 00:02:09,440
One if the node to insert is part of the given doubly linked list.

41
00:02:09,440 --> 00:02:15,050
And the second case is where the node to insert is not part of the given doubly linked list.

42
00:02:15,050 --> 00:02:15,380
Right?

43
00:02:15,380 --> 00:02:21,950
So in the previous video we have seen that if we just call the remove function and we remove the node

44
00:02:21,950 --> 00:02:22,640
insert.

45
00:02:23,150 --> 00:02:23,540
Right.

46
00:02:23,540 --> 00:02:28,040
So in this case after this both the cases become the same thing.

47
00:02:28,040 --> 00:02:28,280
Right.

48
00:02:28,280 --> 00:02:33,260
So what happens over here is if the node is part of the doubly linked list we remove it.

49
00:02:33,260 --> 00:02:33,650
Right.

50
00:02:33,650 --> 00:02:36,350
So it's now no longer part of the doubly linked list.

51
00:02:36,350 --> 00:02:40,100
And we have to insert it before the node position which is given.

52
00:02:40,100 --> 00:02:45,740
Now if it was not part of the given doubly linked list, this function will just do nothing, right?

53
00:02:45,740 --> 00:02:51,140
It will just, uh, over here we can see that at the end of remove we have the node which was passed

54
00:02:51,140 --> 00:02:54,920
to the remove function, and its next and previous is pointing to null.

55
00:02:54,920 --> 00:02:59,420
So if the given node was not part of the doubly linked list.

56
00:02:59,420 --> 00:03:02,690
So both of the sides of it are pointing to null.

57
00:03:02,690 --> 00:03:04,610
And we just have that node over here.

58
00:03:04,610 --> 00:03:10,220
So now after calling the remove function we have we have reached a position where there is just one

59
00:03:10,220 --> 00:03:10,700
case.

60
00:03:10,700 --> 00:03:14,060
So the node now is no longer part of the doubly linked list.

61
00:03:14,060 --> 00:03:19,490
And we need to insert that particular node before the node position which is again a node.

62
00:03:19,490 --> 00:03:24,020
So we have to insert the node now before this node position node.

63
00:03:24,020 --> 00:03:25,910
So let's go ahead and do that.

64
00:03:25,910 --> 00:03:29,690
Now remember what we discussed in the previous video.

65
00:03:29,690 --> 00:03:34,310
What we now go what we are going to do now is that we have this node.

66
00:03:34,310 --> 00:03:35,870
So let's write that over here.

67
00:03:35,870 --> 00:03:38,990
And we will set its previous and its next.

68
00:03:38,990 --> 00:03:40,910
So that's the next step that we're going to do.

69
00:03:40,910 --> 00:03:43,370
So let me just write that over here.

70
00:03:43,370 --> 00:03:46,250
We are going to set its previous and its next.

71
00:03:46,250 --> 00:03:47,870
What about its previous.

72
00:03:48,350 --> 00:03:51,650
We're going to set its previous to the.

73
00:03:52,360 --> 00:03:53,380
Node position.

74
00:03:53,380 --> 00:03:56,650
Now again, remember the important thing is that you have to visualize this.

75
00:03:56,650 --> 00:04:00,040
Let's say we are trying to insert three before two.

76
00:04:00,040 --> 00:04:00,430
All right.

77
00:04:00,430 --> 00:04:02,050
So now we have removed three.

78
00:04:02,050 --> 00:04:03,730
So this is no longer over here.

79
00:04:03,730 --> 00:04:06,010
Now we want to insert three over here.

80
00:04:06,010 --> 00:04:08,260
Now what should be its next.

81
00:04:08,260 --> 00:04:10,180
Its next has to be two right.

82
00:04:10,180 --> 00:04:11,650
And what about its previous.

83
00:04:11,650 --> 00:04:13,000
Its previous has to be one.

84
00:04:13,000 --> 00:04:13,420
Right.

85
00:04:13,420 --> 00:04:16,630
So we can say that node to insert dot previous.

86
00:04:16,630 --> 00:04:18,250
And this is the position node.

87
00:04:18,250 --> 00:04:18,550
Right.

88
00:04:18,550 --> 00:04:23,470
So node to insert dot previous is the previous value of the position node.

89
00:04:23,470 --> 00:04:30,160
So we can say that node insert dot prev is equal to node position dot prev.

90
00:04:30,520 --> 00:04:33,430
Again remember the important thing is that you visualize this.

91
00:04:33,430 --> 00:04:36,760
If you can correctly visualize this the code will come naturally.

92
00:04:36,760 --> 00:04:38,980
So we are trying to insert three ahead of two.

93
00:04:39,010 --> 00:04:41,320
So it will become in between 1 and 2 right.

94
00:04:41,320 --> 00:04:44,980
So whatever is previous to three is this node over here.

95
00:04:44,980 --> 00:04:49,240
And at this point this node is the node which is previous to this node.

96
00:04:49,240 --> 00:04:51,490
And this node is the node position.

97
00:04:51,490 --> 00:04:52,810
So that's what we have done over here.

98
00:04:52,810 --> 00:04:56,530
Node insert dot prev is equal to node position dot prev.

99
00:04:56,560 --> 00:05:02,980
Now when three is in between 1 and 2 the next uh node after three should be two right.

100
00:05:02,980 --> 00:05:04,990
Which is the node position itself.

101
00:05:04,990 --> 00:05:09,010
So node insert dot next is equal to node position.

102
00:05:10,680 --> 00:05:10,950
All right.

103
00:05:10,950 --> 00:05:12,150
So we have done this step.

104
00:05:12,150 --> 00:05:15,540
So we have changed the pointers of uh three.

105
00:05:15,540 --> 00:05:16,680
The node with value three.

106
00:05:16,680 --> 00:05:17,190
Right.

107
00:05:17,190 --> 00:05:20,610
Its previous and next pointers are now in the correct position.

108
00:05:20,610 --> 00:05:27,450
Now what we are going to now check is we will check whether the node before which we want to insert

109
00:05:27,450 --> 00:05:28,680
this actually.

110
00:05:29,580 --> 00:05:31,980
Is the head itself or not, right?

111
00:05:31,980 --> 00:05:32,610
Why is that?

112
00:05:32,610 --> 00:05:38,070
So if you are inserting it before the head, then we have to make that node the new head.

113
00:05:38,070 --> 00:05:38,370
Right.

114
00:05:38,370 --> 00:05:40,260
So let's take care of that case.

115
00:05:40,260 --> 00:05:46,350
So let's check that if the position node or that's the node position right.

116
00:05:46,350 --> 00:05:48,750
If node position is the head.

117
00:05:48,750 --> 00:05:50,790
So equal to equal to this dot head.

118
00:05:50,790 --> 00:05:53,190
And we are inserting it before the head right.

119
00:05:53,190 --> 00:06:00,660
So in that case we have to say that this dot head is the node that we are inserting which is node insert.

120
00:06:02,590 --> 00:06:03,070
All right.

121
00:06:03,070 --> 00:06:06,250
Now, if that is not the case, what do we do?

122
00:06:07,250 --> 00:06:08,330
Try to visualize this.

123
00:06:08,330 --> 00:06:13,280
So let's say if we had to insert this node ahead of this node, right.

124
00:06:13,280 --> 00:06:16,400
So we are setting this node to the new head because it's over here.

125
00:06:16,400 --> 00:06:18,920
But so that's what we have taken care over here.

126
00:06:18,920 --> 00:06:20,870
Now what if that is not the case.

127
00:06:20,870 --> 00:06:23,330
So that means we don't need to change the head right.

128
00:06:23,330 --> 00:06:25,700
So let's say again we are taking the case.

129
00:06:25,700 --> 00:06:27,830
Let me just make some space over here.

130
00:06:27,830 --> 00:06:31,730
Let's say we are taking the case where we are changing the position of three.

131
00:06:31,730 --> 00:06:35,180
Remember at every point the important thing is that we visualize this.

132
00:06:35,180 --> 00:06:38,060
So we initially we removed three right?

133
00:06:38,060 --> 00:06:39,080
We removed three.

134
00:06:39,080 --> 00:06:43,580
Now we are trying to insert it over here which is in between 1 and 2.

135
00:06:43,610 --> 00:06:45,410
So it's it's the else part over here.

136
00:06:45,410 --> 00:06:49,580
So we are not trying to insert it at ahead of the head.

137
00:06:50,210 --> 00:06:50,570
All right.

138
00:06:50,570 --> 00:06:51,890
So that's clear.

139
00:06:51,890 --> 00:06:55,550
And we have set its next and previous value already.

140
00:06:55,550 --> 00:06:57,500
Now we have something over here right.

141
00:06:57,500 --> 00:06:59,090
We have something over here.

142
00:06:59,090 --> 00:07:02,840
So what we can do is node dot prev this.

143
00:07:02,840 --> 00:07:04,400
This one over here is one right.

144
00:07:04,400 --> 00:07:06,470
You can see that this is the node position.

145
00:07:06,470 --> 00:07:08,030
This is the node position.

146
00:07:08,030 --> 00:07:11,750
So node dot position dot prev will give us this node over here.

147
00:07:11,750 --> 00:07:17,330
And the next node of this node has to be set to this one over here.

148
00:07:17,330 --> 00:07:18,170
Right three.

149
00:07:18,170 --> 00:07:21,860
So we are trying to make this connection over here at this point okay.

150
00:07:21,860 --> 00:07:24,260
So we can say that node position.

151
00:07:24,990 --> 00:07:30,810
Dot pref dot next is equal to node insert.

152
00:07:32,560 --> 00:07:32,980
All right.

153
00:07:32,980 --> 00:07:36,850
So we have made this connection from 1 to 3 at this point.

154
00:07:36,850 --> 00:07:37,360
All right.

155
00:07:37,360 --> 00:07:43,810
The final step is that we have to change the pointer of node position dot pref.

156
00:07:43,810 --> 00:07:44,170
Right.

157
00:07:44,170 --> 00:07:47,320
So we have inserted three right in between.

158
00:07:47,320 --> 00:07:49,930
So node position is two.

159
00:07:49,930 --> 00:07:52,540
And we need to change this direction also.

160
00:07:52,540 --> 00:07:56,050
So so so far we have done this this direction.

161
00:07:56,050 --> 00:07:56,740
This is done.

162
00:07:56,740 --> 00:07:59,320
Where have we done over here in these two lines.

163
00:07:59,320 --> 00:08:01,960
We have done this direction and this direction.

164
00:08:01,960 --> 00:08:02,950
So this is done.

165
00:08:02,950 --> 00:08:05,560
Now in this case we have checked whether it's the head.

166
00:08:05,560 --> 00:08:08,530
If it's the head, we have set node insert as the head.

167
00:08:08,530 --> 00:08:10,570
And in this case it's not the case.

168
00:08:10,570 --> 00:08:16,720
So we have done node position dot prev which is one dot next to node insert.

169
00:08:16,720 --> 00:08:17,890
So we have done this connection.

170
00:08:17,890 --> 00:08:18,430
Also.

171
00:08:18,580 --> 00:08:24,460
The last thing to do is we have to set node position dot prev is equal to node insert.

172
00:08:24,460 --> 00:08:26,260
That is this connection over here.

173
00:08:26,260 --> 00:08:27,490
This has to be set.

174
00:08:27,490 --> 00:08:29,230
So let's do that now.

175
00:08:29,830 --> 00:08:32,050
So we have node position.

176
00:08:35,420 --> 00:08:36,560
Dot prev.

177
00:08:37,950 --> 00:08:40,410
Is equal to node insert.

178
00:08:42,730 --> 00:08:44,290
All right, so we are done.

179
00:08:44,290 --> 00:08:45,430
And, um.

180
00:08:45,430 --> 00:08:47,200
Okay, I've missed this over here.

181
00:08:47,200 --> 00:08:48,460
Let me add that over here.

182
00:08:48,460 --> 00:08:50,140
It should be this dot remove.

183
00:08:51,110 --> 00:08:55,640
Now let's go ahead and test our, uh, code.

184
00:08:55,640 --> 00:08:59,090
So over here we have our linked list doubly.

185
00:08:59,090 --> 00:09:04,610
Now let's say we want to insert node three ahead of node two.

186
00:09:04,640 --> 00:09:06,680
So let's try that linked list.

187
00:09:06,680 --> 00:09:08,930
Doubly dot insert.

188
00:09:09,510 --> 00:09:10,200
Be.

189
00:09:10,710 --> 00:09:19,050
And let's say the node position is two and the node to insert or in this case node insert is three.

190
00:09:20,960 --> 00:09:21,500
All right.

191
00:09:21,530 --> 00:09:22,970
Now, what's the expectation?

192
00:09:22,970 --> 00:09:24,290
Let's take a quick look.

193
00:09:24,290 --> 00:09:26,090
We have one, two three, four five.

194
00:09:26,090 --> 00:09:32,240
That's the current scenario right at the at the end of this we have created linked list doubly doubly

195
00:09:32,240 --> 00:09:34,370
linked list with 12345.

196
00:09:34,370 --> 00:09:40,490
So after we do this it should take three and it should put it ahead of two.

197
00:09:40,490 --> 00:09:42,080
So that's the expectation right.

198
00:09:42,080 --> 00:09:45,950
So it should be like this where each of these connections are two sided.

199
00:09:45,980 --> 00:09:49,130
Now let's run our code and test whether that's working.

200
00:09:51,030 --> 00:09:52,920
All right, so I'm running the code.

201
00:09:54,090 --> 00:09:57,450
And let's take a look at our doubly linked list.

202
00:10:01,930 --> 00:10:06,790
So we can see over here we have this is the expectation.

203
00:10:06,790 --> 00:10:10,360
We have the head one which is pointing to three.

204
00:10:10,360 --> 00:10:11,440
That's correct.

205
00:10:11,440 --> 00:10:14,440
And that's pointing to two which is also correct.

206
00:10:14,440 --> 00:10:15,940
And that's pointing to four.

207
00:10:15,940 --> 00:10:20,380
And that is pointing to five which is pointing to null.

208
00:10:20,380 --> 00:10:20,740
Right.

209
00:10:20,740 --> 00:10:21,850
So this is correct.

210
00:10:21,850 --> 00:10:28,630
Again, uh, let's take a look whether the pointers are correct in all the directions for node three.

211
00:10:28,630 --> 00:10:31,960
So we have again we have the head which is one.

212
00:10:31,960 --> 00:10:33,670
And that's pointing to three.

213
00:10:33,670 --> 00:10:35,260
What about the next value.

214
00:10:35,260 --> 00:10:37,360
That's two that that's something that we have confirmed.

215
00:10:37,360 --> 00:10:40,120
What about the previous value three is pointing to one.

216
00:10:40,120 --> 00:10:41,170
That is also correct.

217
00:10:41,170 --> 00:10:42,970
So this solution is correct.

218
00:10:42,970 --> 00:10:44,440
Now let's take another example.

219
00:10:44,440 --> 00:10:45,850
Let me clear my console.

220
00:10:45,850 --> 00:10:48,970
And let's say we want to insert a new node.

221
00:10:48,970 --> 00:10:51,970
So over here we have these five nodes.

222
00:10:51,970 --> 00:10:56,980
Let's create a new one which is not part of our part of our current uh doubly linked list.

223
00:10:56,980 --> 00:10:58,090
Let's call it seven.

224
00:10:58,090 --> 00:11:01,210
And that's equal to new node.

225
00:11:01,210 --> 00:11:03,220
And let it have the value seven.

226
00:11:04,650 --> 00:11:07,410
Now let's try to insert this again.

227
00:11:07,410 --> 00:11:11,040
Maybe we can try to insert it ahead of three.

228
00:11:14,110 --> 00:11:18,220
I'm commenting this out so that it's easy for us to test.

229
00:11:18,220 --> 00:11:22,570
So what's the expectation initially, this is the scenario, right?

230
00:11:23,200 --> 00:11:24,880
Of our doubly linked list.

231
00:11:24,880 --> 00:11:27,280
And we want to insert seven ahead of three.

232
00:11:27,280 --> 00:11:31,030
So seven will come over here and it should connect to three.

233
00:11:31,030 --> 00:11:32,500
So this is the expectation.

234
00:11:32,500 --> 00:11:34,090
So let's run it.

235
00:11:35,330 --> 00:11:38,870
And let's see how our doubly linked list looks like now.

236
00:11:40,700 --> 00:11:43,760
We have the head which is has a value one.

237
00:11:43,760 --> 00:11:49,010
So that's pointing to the node with value two, which is pointing to the node with value seven.

238
00:11:49,010 --> 00:11:52,820
And the next value is the node with.

239
00:11:53,590 --> 00:11:55,480
Value three, which is correct.

240
00:11:55,480 --> 00:11:56,500
So this is correct.

241
00:11:56,500 --> 00:12:00,610
And the previous value we can see the previous value also over here.

242
00:12:00,610 --> 00:12:03,100
So two is pointing to seven.

243
00:12:03,100 --> 00:12:05,050
And the previous value of two is one.

244
00:12:05,050 --> 00:12:05,320
Okay.

245
00:12:05,320 --> 00:12:09,910
So we didn't make any changes over here seven as the next value three and seven as the previous value

246
00:12:09,910 --> 00:12:10,030
two.

247
00:12:10,060 --> 00:12:11,710
So this connection is also correct.

248
00:12:11,710 --> 00:12:13,720
So yes our code is working.

249
00:12:13,870 --> 00:12:18,130
Now let's take a sample case and again walk through the code.

250
00:12:18,130 --> 00:12:22,480
Because in any coding interview you will be asked to do that once you have written the code.

251
00:12:22,480 --> 00:12:24,040
So we will do that now.