1
00:00:00,810 --> 00:00:06,510
Hi everyone, I hope you have given it a thought about how you could implement the solution, which

2
00:00:06,510 --> 00:00:12,840
we discussed in the previous video, to write a function which will remove a node when the node is given

3
00:00:12,840 --> 00:00:16,680
as an input right and that node is part of a doubly linked list.

4
00:00:16,710 --> 00:00:19,800
Now before we go ahead and write the instance method.

5
00:00:19,800 --> 00:00:25,560
So I have just written some code over here so that once we are done writing the instance method, we

6
00:00:25,560 --> 00:00:26,970
will be able to test our code.

7
00:00:26,970 --> 00:00:30,180
So let me just quickly walk you through what I've written over here.

8
00:00:30,750 --> 00:00:32,910
Now we have a class node okay.

9
00:00:32,910 --> 00:00:39,870
And when we call this class node we will be passing a value so that we can create a node.

10
00:00:39,870 --> 00:00:40,080
Right.

11
00:00:40,080 --> 00:00:43,650
So using this class node I have created these nodes over here.

12
00:00:43,650 --> 00:00:46,170
So node 1234 and five.

13
00:00:46,170 --> 00:00:49,410
They have the values 12345 respectively.

14
00:00:49,410 --> 00:00:50,040
All right.

15
00:00:50,040 --> 00:00:53,520
So and then I have a function over here.

16
00:00:53,520 --> 00:00:58,680
Now when I pass two nodes to this function I will connect them together.

17
00:00:58,680 --> 00:00:58,890
Right.

18
00:00:58,890 --> 00:01:01,740
So node one dot next is set to node two.

19
00:01:01,740 --> 00:01:04,680
And node two dot previous is set to node one.

20
00:01:04,680 --> 00:01:06,510
So that's what's done over here.

21
00:01:06,510 --> 00:01:09,060
So that's just to reduce the number of lines of code.

22
00:01:09,060 --> 00:01:10,500
We could do it manually also.

23
00:01:10,500 --> 00:01:10,920
Right.

24
00:01:10,920 --> 00:01:15,030
We could do it with multiple lines of code also to connect these nodes together.

25
00:01:15,030 --> 00:01:18,840
And I have a class doubly linked list over here.

26
00:01:18,840 --> 00:01:21,900
Now over here I don't have any input.

27
00:01:21,900 --> 00:01:23,880
And this dot head is set to null.

28
00:01:23,880 --> 00:01:25,650
And this dot tail is set to null.

29
00:01:25,650 --> 00:01:31,920
And using this class doubly linked list I have created linked list doubly over here.

30
00:01:31,920 --> 00:01:32,460
Right.

31
00:01:32,460 --> 00:01:38,970
And initially the head is null and the tail is null of linked list doubly right.

32
00:01:38,970 --> 00:01:40,260
This is a doubly linked list.

33
00:01:40,260 --> 00:01:48,150
And then we connect the nodes 1234, five using the function that we have written over here.

34
00:01:48,150 --> 00:01:54,690
And finally we set the head of linked list W21 and the tail of linked list W25.

35
00:01:54,720 --> 00:01:56,310
Now before we write anything.

36
00:01:56,310 --> 00:01:59,190
So just we have we have not written a function yet.

37
00:01:59,190 --> 00:02:01,230
Let's see how this looks.

38
00:02:01,230 --> 00:02:03,450
So let me just run this code.

39
00:02:04,430 --> 00:02:05,990
All right, so I'm just running it.

40
00:02:06,610 --> 00:02:10,300
And let's take a look at linked list doubly.

41
00:02:15,740 --> 00:02:16,070
All right.

42
00:02:16,070 --> 00:02:17,660
So over here you can see that.

43
00:02:17,660 --> 00:02:19,010
Let me just make this bigger.

44
00:02:19,010 --> 00:02:23,090
You can see that the head is having is a node with value one.

45
00:02:23,090 --> 00:02:25,460
And the tail is a node with value five.

46
00:02:25,460 --> 00:02:28,040
So one is pointing to a node with value two.

47
00:02:28,040 --> 00:02:30,470
And the previous node of one is null.

48
00:02:30,470 --> 00:02:32,420
So this is a valid doubly linked list.

49
00:02:32,420 --> 00:02:39,230
Now the node with value two is pointing to the node with value three, and the previous node of the

50
00:02:39,230 --> 00:02:41,300
node with value two is the node with value one.

51
00:02:41,300 --> 00:02:46,400
So in this way you can just open over here and see that we have already created a doubly linked list.

52
00:02:46,400 --> 00:02:48,800
So it's called linked list doubly over here.

53
00:02:48,830 --> 00:02:49,640
All right.

54
00:02:50,030 --> 00:02:51,800
Now let me minimize this.

55
00:02:53,520 --> 00:02:56,970
And let's go ahead and solve the question which we discussed.

56
00:02:58,530 --> 00:02:59,130
All right.

57
00:02:59,130 --> 00:03:02,190
Now we are going to write an instance method.

58
00:03:02,190 --> 00:03:06,240
So let's call it remove and it will be written over here right.

59
00:03:07,330 --> 00:03:11,560
And we will be passing a particular node to this function, right.

60
00:03:11,560 --> 00:03:13,900
The node which we want to remove.

61
00:03:13,930 --> 00:03:16,600
Now how do we go ahead with this code.

62
00:03:16,630 --> 00:03:20,290
Remember we have discussed that there are three cases.

63
00:03:20,290 --> 00:03:24,160
The first case is that if the node to be removed is the head.

64
00:03:24,160 --> 00:03:28,840
The second case, as per the previous video where we discussed the method, is the case where the node

65
00:03:28,840 --> 00:03:30,160
to be removed is the tail.

66
00:03:30,160 --> 00:03:35,470
And then we check whether the node to be removed has a previous value and we do something.

67
00:03:35,470 --> 00:03:39,100
We check if the node the given node has a next value.

68
00:03:39,100 --> 00:03:45,970
We do something, and finally we set the previous and next pointers of the given node to null.

69
00:03:45,970 --> 00:03:48,220
So this is the process that we are going to follow right?

70
00:03:48,220 --> 00:03:52,540
So try to visualize it based on the previous video that we discussed.

71
00:03:52,540 --> 00:03:52,810
Right.

72
00:03:52,810 --> 00:03:58,390
So if you can picturize this then it's very easy to code because you are very clear on what you want

73
00:03:58,390 --> 00:03:59,350
to actually achieve.

74
00:03:59,350 --> 00:03:59,860
All right.

75
00:03:59,860 --> 00:04:04,150
So first let's check whether the node to be removed is the head or not.

76
00:04:04,150 --> 00:04:05,950
So let's check that over here.

77
00:04:05,950 --> 00:04:10,540
If this dot head is equal to the given node.

78
00:04:10,540 --> 00:04:15,430
If this is true then we need to set the head as the next node right.

79
00:04:15,430 --> 00:04:20,140
So this dot head has to be set to node dot next.

80
00:04:23,900 --> 00:04:24,470
All right.

81
00:04:24,470 --> 00:04:28,040
Now, what if the node to be removed is the tail?

82
00:04:28,070 --> 00:04:29,720
Let's check that if.

83
00:04:30,470 --> 00:04:35,540
This dot tail is equal to the node to be removed.

84
00:04:35,540 --> 00:04:42,110
In this case, we have to set the new tail to the node which is previous to the given node, right.

85
00:04:42,110 --> 00:04:43,910
So node dot prev.

86
00:04:44,540 --> 00:04:48,380
So again remember these are this next and prev is defined over here.

87
00:04:48,380 --> 00:04:48,560
Right.

88
00:04:48,560 --> 00:04:49,760
So you have to use the same.

89
00:04:49,760 --> 00:04:53,210
So let's say you're writing dot val over here and somewhere else.

90
00:04:53,210 --> 00:04:54,620
You are writing this dot value.

91
00:04:54,650 --> 00:04:55,520
You will get an error.

92
00:04:55,520 --> 00:04:56,840
So you have to use the same thing.

93
00:04:56,840 --> 00:05:00,650
So over here we are writing this dot a list node dot pref.

94
00:05:00,650 --> 00:05:01,370
All right.

95
00:05:01,370 --> 00:05:04,010
So we have taken care of these two scenarios.

96
00:05:04,010 --> 00:05:06,260
Now what's the generic scenario.

97
00:05:06,260 --> 00:05:11,180
We are going to check if the node which is given has a previous value.

98
00:05:11,180 --> 00:05:16,520
Let's check that if the node given has a previous value then what do we do.

99
00:05:16,520 --> 00:05:17,990
The previous value.

100
00:05:18,290 --> 00:05:21,770
Next value has to be set to the node's next value, right?

101
00:05:21,770 --> 00:05:23,120
Just try to picturise it.

102
00:05:23,120 --> 00:05:26,210
And again remember we have discussed this in the previous video.

103
00:05:26,210 --> 00:05:28,430
Let me just quickly show that to you over here.

104
00:05:28,430 --> 00:05:31,940
So let's say we have one pointing to two.

105
00:05:31,970 --> 00:05:33,500
Again it's doubly linked list.

106
00:05:33,500 --> 00:05:38,990
I'm just drawing a line indicating that it's, uh, pointing in both the directions because I don't

107
00:05:38,990 --> 00:05:42,470
want to increase, uh, much what I'm writing over here.

108
00:05:42,470 --> 00:05:47,300
So one then we have two, then we have three, then we have four, then we have five.

109
00:05:47,720 --> 00:05:48,170
All right.

110
00:05:48,170 --> 00:05:51,200
Now let's say we want to remove node three.

111
00:05:51,230 --> 00:05:56,360
Now we are checking whether there is something at the position node dot pref.

112
00:05:56,360 --> 00:05:57,830
So that's this node over here.

113
00:05:57,830 --> 00:05:58,160
Right.

114
00:05:58,160 --> 00:06:04,130
So if it is there this one has to be connected to the value of to the node over here.

115
00:06:04,130 --> 00:06:05,720
Right which is node dot next.

116
00:06:05,720 --> 00:06:07,490
So that's what we are trying to do over here.

117
00:06:07,490 --> 00:06:15,110
If node.prev is there if it's truthy that means if it's not null or if it's there then node dot pref.

118
00:06:15,990 --> 00:06:17,130
Dot next.

119
00:06:17,280 --> 00:06:17,790
Right.

120
00:06:17,790 --> 00:06:20,520
So by doing no dot prev we get to here.

121
00:06:20,520 --> 00:06:23,850
Remember we are taking the example of removing node with value three.

122
00:06:23,850 --> 00:06:26,670
So no dot prev gives us this node over here.

123
00:06:26,670 --> 00:06:29,520
Dot next gives us this one over here.

124
00:06:29,520 --> 00:06:29,760
Right.

125
00:06:29,760 --> 00:06:31,590
So again we want to remove this.

126
00:06:31,590 --> 00:06:33,390
So we have to connect it to this one.

127
00:06:33,390 --> 00:06:36,540
So that is equal to node dot next.

128
00:06:37,800 --> 00:06:38,160
All right.

129
00:06:38,160 --> 00:06:42,360
So no dot next is four and no dot prev is two.

130
00:06:42,390 --> 00:06:43,890
So what we are doing is two.

131
00:06:43,890 --> 00:06:47,010
And then we are using the dot next operator.

132
00:06:47,010 --> 00:06:47,220
Right.

133
00:06:47,220 --> 00:06:49,980
So two next has to be the node with value four.

134
00:06:49,980 --> 00:06:52,110
So that's what we are trying to do over here.

135
00:06:52,770 --> 00:06:53,250
All right.

136
00:06:53,250 --> 00:06:58,050
And after this we are going to check if the input node has a next value.

137
00:06:58,050 --> 00:07:02,400
So if node dot next that is if node dot next is truthy.

138
00:07:02,400 --> 00:07:04,290
Or if there is something after that.

139
00:07:04,290 --> 00:07:06,060
So let's again take this example.

140
00:07:06,060 --> 00:07:08,340
So over here we want to remove three.

141
00:07:08,340 --> 00:07:11,040
So there is something in the next position right.

142
00:07:11,040 --> 00:07:12,030
There is a node over here.

143
00:07:12,030 --> 00:07:13,410
So what do we need to do.

144
00:07:13,440 --> 00:07:17,880
We need to set the previous of this node to two over here.

145
00:07:17,880 --> 00:07:18,270
Right.

146
00:07:18,270 --> 00:07:19,740
So let's do that over here.

147
00:07:19,740 --> 00:07:22,560
So node dot next.

148
00:07:23,200 --> 00:07:28,930
Dot pref has to be set to node dot pref.

149
00:07:30,400 --> 00:07:32,560
Again try to visualize this right.

150
00:07:32,560 --> 00:07:36,970
So if you are clear visually what you're doing then the code comes naturally.

151
00:07:36,970 --> 00:07:41,320
So over here node dot next is for dot prev.

152
00:07:41,320 --> 00:07:45,730
So we are thinking about the pointer which is going from four to the left.

153
00:07:45,730 --> 00:07:48,850
And that has to be set to no dot prev no dot prev.

154
00:07:48,850 --> 00:07:50,140
Is this one over here.

155
00:07:50,140 --> 00:07:50,770
All right.

156
00:07:51,040 --> 00:07:57,790
So what we are trying to avoid over here is we don't want to have a situation where let's say node.prev

157
00:07:57,790 --> 00:08:00,100
is null and then we say null dot next.

158
00:08:00,100 --> 00:08:01,150
So we don't want that right.

159
00:08:01,150 --> 00:08:04,240
So that's why we are checking whether node.prev is there.

160
00:08:04,240 --> 00:08:06,880
If it is there then we are doing node dot prev dot.

161
00:08:06,880 --> 00:08:08,770
Next is equal to node dot next.

162
00:08:08,770 --> 00:08:10,990
Again remember the key is to visualize this.

163
00:08:10,990 --> 00:08:12,520
So the code comes naturally.

164
00:08:12,520 --> 00:08:16,750
And once we are done with this then just one more step remains.

165
00:08:16,750 --> 00:08:20,620
So we have the node and now it's pointing somewhere right.

166
00:08:20,620 --> 00:08:21,580
So we want to remove it.

167
00:08:21,580 --> 00:08:24,280
So no dot next should be set to null.

168
00:08:25,200 --> 00:08:30,150
And node.prev should be set to null and we are done with the code.

169
00:08:30,150 --> 00:08:30,720
All right.

170
00:08:30,720 --> 00:08:36,540
Now let's go ahead and run our code and see whether it's working or not.

171
00:08:36,540 --> 00:08:38,400
So let's do that now.

172
00:08:38,580 --> 00:08:46,350
Now over here we have linked list doubly and we have seen that it's uh, we have it in this structure

173
00:08:46,350 --> 00:08:47,460
like we have null.

174
00:08:47,490 --> 00:08:50,430
Then we have one, two, three, four, five and then we have null.

175
00:08:50,430 --> 00:08:52,500
So this is the current way it looks.

176
00:08:52,500 --> 00:08:56,760
Now let's say for example let's start by removing this two over here.

177
00:08:57,240 --> 00:08:57,540
All right.

178
00:08:57,540 --> 00:08:58,800
So let's do that.

179
00:08:58,800 --> 00:09:03,600
So I'm calling linked list doubly and dot remove.

180
00:09:03,600 --> 00:09:05,370
And I'm going to pass a node.

181
00:09:05,370 --> 00:09:05,760
Right.

182
00:09:05,760 --> 00:09:07,530
So that's what we are done over here.

183
00:09:07,530 --> 00:09:10,140
We are passing a node as input to the remove function.

184
00:09:10,140 --> 00:09:13,470
So let's say we wanted to remove the node with value two.

185
00:09:13,470 --> 00:09:15,510
So that's this node over here.

186
00:09:15,510 --> 00:09:17,880
So we are going to pass in the node two.

187
00:09:19,010 --> 00:09:22,130
Okay, now let's run it and let's see what's happening.

188
00:09:27,530 --> 00:09:29,360
Okay, so we have run it.

189
00:09:29,360 --> 00:09:32,990
Now let's see how linked list doubly looks like now.

190
00:09:32,990 --> 00:09:36,920
Now that we have run this and removed the node with value two.

191
00:09:36,950 --> 00:09:38,180
So that should not be there.

192
00:09:38,180 --> 00:09:39,890
So that's what we're going to check.

193
00:09:40,460 --> 00:09:44,840
Now we have the head as one and the head is pointing to three, right?

194
00:09:44,840 --> 00:09:48,860
Initially the head was one, was pointing to two, but now one is pointing to three.

195
00:09:48,860 --> 00:09:50,600
So we have successfully removed two.

196
00:09:50,630 --> 00:09:51,500
So it's working.

197
00:09:51,500 --> 00:09:55,100
Now let's take an example where we want to remove the head.

198
00:09:55,100 --> 00:09:56,960
Let's say we want to remove one.

199
00:09:56,960 --> 00:10:00,590
So I'll change this to one and I'll run the code again.

200
00:10:00,590 --> 00:10:03,200
Remember we are only removing one at this point right?

201
00:10:03,200 --> 00:10:05,870
Again because we are running the code from the beginning again.

202
00:10:05,870 --> 00:10:09,680
So we will again create this new doubly linked list, right?

203
00:10:09,680 --> 00:10:10,220
The linked list.

204
00:10:10,220 --> 00:10:14,570
We will be again created and we are going to remove only this node over here.

205
00:10:14,570 --> 00:10:14,870
All right.

206
00:10:14,870 --> 00:10:17,300
So the head should be two once we are done with this.

207
00:10:17,300 --> 00:10:19,040
So let's go ahead and do that.

208
00:10:20,490 --> 00:10:22,350
All right, so I've run the code.

209
00:10:22,350 --> 00:10:25,140
Now let's check how it looks.

210
00:10:27,550 --> 00:10:31,060
Okay so we have linked list W over here.

211
00:10:31,060 --> 00:10:35,320
And when we open it we can see that the head is two and two is pointing to three.

212
00:10:35,320 --> 00:10:36,250
And it goes on like that.

213
00:10:36,250 --> 00:10:37,390
And the tail is five.

214
00:10:37,390 --> 00:10:40,180
So yes we've successfully removed the head.

215
00:10:40,180 --> 00:10:43,540
And lastly let's check a case where we remove the tail.

216
00:10:43,540 --> 00:10:45,100
So the tail over here is five.

217
00:10:45,100 --> 00:10:47,170
So let's again run our code.

218
00:10:48,420 --> 00:10:50,850
And let's check how it looks.

219
00:10:56,720 --> 00:10:57,440
All right.

220
00:10:57,770 --> 00:10:59,210
So we have run the code.

221
00:10:59,210 --> 00:10:59,990
Let's check it.

222
00:10:59,990 --> 00:11:03,170
So over here you can see that the head is one and the tail is four right.

223
00:11:03,170 --> 00:11:06,110
Initially the tail was five but we have successfully removed it.

224
00:11:06,110 --> 00:11:08,330
And the tail over here is now four.

225
00:11:08,330 --> 00:11:11,060
Now we have successfully coded the solution.

226
00:11:11,060 --> 00:11:16,610
Now let's take a sample case and quickly walk through the code because you will be doing this in the

227
00:11:16,610 --> 00:11:17,510
interview also.

228
00:11:17,510 --> 00:11:18,980
So let's do that next.