1
00:00:00,620 --> 00:00:01,610
Welcome back.

2
00:00:01,610 --> 00:00:05,450
Let's now go ahead and design the singly linked list.

3
00:00:05,450 --> 00:00:10,100
And let's also implement the instance methods as we discussed in the previous video.

4
00:00:10,100 --> 00:00:13,010
Now for this let's first write a class node.

5
00:00:13,010 --> 00:00:18,500
Now we will use this class to create each node which is going to be each element in the singly linked

6
00:00:18,500 --> 00:00:18,830
list.

7
00:00:18,860 --> 00:00:20,810
Now over here we'll need a constructor.

8
00:00:21,520 --> 00:00:25,000
And let's pass the value over here to the constructor.

9
00:00:25,000 --> 00:00:27,460
And then we will just say this dot value.

10
00:00:28,890 --> 00:00:31,530
Is equal to the value which is passed over here to it.

11
00:00:31,530 --> 00:00:33,540
And then let's say this dot next.

12
00:00:34,570 --> 00:00:36,100
Is equal to null.

13
00:00:36,280 --> 00:00:37,000
All right.

14
00:00:37,030 --> 00:00:40,090
Now we also need the singly linked list class.

15
00:00:40,090 --> 00:00:42,430
So let's say class singly linked list.

16
00:00:45,670 --> 00:00:48,220
And we have a constructor over here as well.

17
00:00:50,210 --> 00:00:51,770
And nothing is passed to it.

18
00:00:51,800 --> 00:00:55,340
Now let's just say over here this dot head is equal to null.

19
00:00:57,640 --> 00:01:00,640
And we can say this dot tail is equal to null.

20
00:01:00,910 --> 00:01:04,420
Now we can also track the size of the linked list over here.

21
00:01:04,450 --> 00:01:05,890
So let's do that.

22
00:01:05,890 --> 00:01:09,340
So we can say this dot size is equal to zero at this point.

23
00:01:09,490 --> 00:01:10,000
All right.

24
00:01:10,030 --> 00:01:13,960
Now over here we will go ahead and write the instance method.

25
00:01:13,960 --> 00:01:15,670
So we'll have a get function.

26
00:01:15,670 --> 00:01:17,170
So get index.

27
00:01:17,170 --> 00:01:20,860
That is one of the instance methods asked in the question.

28
00:01:20,860 --> 00:01:24,370
Then we have an instance method to add at the head.

29
00:01:24,370 --> 00:01:26,140
So we can write over here add at head.

30
00:01:26,140 --> 00:01:27,880
So these are just placeholders.

31
00:01:29,580 --> 00:01:31,980
And over here the value has to be passed to it.

32
00:01:34,850 --> 00:01:35,210
All right.

33
00:01:35,240 --> 00:01:38,390
Now let's go ahead and write the remaining instance methods.

34
00:01:38,390 --> 00:01:40,250
And let's just have placeholders for them.

35
00:01:40,250 --> 00:01:43,130
So we have another method to add at the tail.

36
00:01:44,850 --> 00:01:48,330
And the value is passed to this method as well.

37
00:01:49,350 --> 00:01:52,740
And then we have another function to add at a particular index.

38
00:01:52,740 --> 00:01:54,750
So add at index.

39
00:01:56,260 --> 00:01:59,860
And the value is passed to it, and the index also is passed.

40
00:01:59,860 --> 00:02:01,600
So let's say index comma value.

41
00:02:04,730 --> 00:02:05,210
All right.

42
00:02:05,210 --> 00:02:08,900
And then finally we have a method to delete at a particular index.

43
00:02:08,900 --> 00:02:10,340
So delete at index.

44
00:02:10,910 --> 00:02:14,660
And in this case only the index will be passed to this method.

45
00:02:15,350 --> 00:02:15,770
All right.

46
00:02:15,770 --> 00:02:18,140
So these are the instance methods that we will write.

47
00:02:18,140 --> 00:02:24,200
And then to initialize an object we can just say let's say let's just call that new object.

48
00:02:24,200 --> 00:02:25,730
Let's call it um SL.

49
00:02:25,730 --> 00:02:29,270
So we can say const SL is equal to new.

50
00:02:29,270 --> 00:02:31,400
And then we can just write singly linked list.

51
00:02:31,760 --> 00:02:35,930
So we are using the class to create a new object of singly linked list.

52
00:02:35,930 --> 00:02:37,730
So that's the first part of the question.

53
00:02:37,730 --> 00:02:38,870
So that is done over here.

54
00:02:38,870 --> 00:02:40,820
Now let's complete this part.

55
00:02:40,820 --> 00:02:42,230
And then we will just test our code.

56
00:02:42,230 --> 00:02:43,610
So we will go one by one.

57
00:02:43,610 --> 00:02:45,800
So let's get started with get index.

58
00:02:46,800 --> 00:02:52,440
So let's say we have a singly linked list and we are calling the Getindex instance method.

59
00:02:52,440 --> 00:02:54,180
And let's say the index is passed.

60
00:02:54,180 --> 00:02:56,610
Let's say the index is 1 or 2, etc..

61
00:02:56,610 --> 00:03:03,270
Now we have to keep traversing through the singly linked list till we reach the node where the index

62
00:03:03,300 --> 00:03:05,310
is equal to the index passed over here.

63
00:03:05,310 --> 00:03:08,340
And again we don't index a singly linked list like an array.

64
00:03:08,340 --> 00:03:11,460
So we cannot access the particular index in constant time.

65
00:03:11,460 --> 00:03:15,180
So let's go ahead and implement the function as we discussed in the previous video.

66
00:03:15,180 --> 00:03:18,210
Now to start with let's just check if the index is valid.

67
00:03:18,210 --> 00:03:24,930
So if the index which is passed over here is less than zero, or if the index is greater than the size

68
00:03:24,930 --> 00:03:26,340
and we are tracking the size over here.

69
00:03:26,340 --> 00:03:27,990
So that's coming handy for us.

70
00:03:27,990 --> 00:03:29,970
So if the index is greater than the size.

71
00:03:29,970 --> 00:03:33,690
So we can say if index greater than or equal to the size right.

72
00:03:33,690 --> 00:03:36,960
Because the last index is going to be the size minus one.

73
00:03:36,960 --> 00:03:41,130
Because in the question it's mentioned that the singly linked list is zero indexed.

74
00:03:41,130 --> 00:03:43,560
So the index of the first node is going to be zero.

75
00:03:43,560 --> 00:03:46,890
So if index is greater than equal to this dot size.

76
00:03:49,120 --> 00:03:49,420
Right?

77
00:03:49,420 --> 00:03:54,760
So if either of these is true, then we know that the index is invalid and we can just return minus

78
00:03:54,760 --> 00:03:55,090
one.

79
00:03:55,090 --> 00:03:56,470
So that's mentioned in the question.

80
00:03:56,470 --> 00:03:59,560
So if the index is invalid we return minus one.

81
00:03:59,560 --> 00:04:01,840
Now if this is not the case we proceed.

82
00:04:01,840 --> 00:04:03,070
So we'll have a counter.

83
00:04:03,070 --> 00:04:06,580
So let's say let counter or let's say counter is equal to zero.

84
00:04:07,180 --> 00:04:10,840
And then let's say we have another variable let's call it current.

85
00:04:10,870 --> 00:04:13,390
Now this is going to point at the head at the moment.

86
00:04:13,390 --> 00:04:16,030
So this dot head so current is equal to this dot head.

87
00:04:16,030 --> 00:04:17,770
And then we will have a while loop.

88
00:04:17,770 --> 00:04:21,640
So we will use this while loop key to keep traversing the singly linked list.

89
00:04:21,640 --> 00:04:27,010
As long as the counter is not equal to the index.

90
00:04:29,180 --> 00:04:29,450
All right.

91
00:04:29,450 --> 00:04:33,830
So if the counter is not equal to the index inside the while loop, what we will do is we will just

92
00:04:33,830 --> 00:04:34,310
move ahead.

93
00:04:34,310 --> 00:04:37,010
So current is equal to current dot next.

94
00:04:38,280 --> 00:04:42,210
And then we will just increment the counter so we can say counter plus plus.

95
00:04:42,780 --> 00:04:43,200
All right.

96
00:04:43,200 --> 00:04:49,380
So when we are out of the while loop, the current over here is going to point at the node where the

97
00:04:49,380 --> 00:04:51,060
index is equal to the counter.

98
00:04:51,060 --> 00:04:53,250
So we can just return that particular node.

99
00:04:53,250 --> 00:04:55,140
So we can say return current.

100
00:04:56,940 --> 00:04:57,690
And that's it.

101
00:04:57,690 --> 00:04:59,160
So this is our Get function.

102
00:04:59,160 --> 00:05:03,060
Now let's go ahead and complete the remaining functions also over here.

103
00:05:03,060 --> 00:05:05,220
So the next one is to add at the head.

104
00:05:05,220 --> 00:05:09,600
Now if we are calling the function add at the head and the value is passed.

105
00:05:09,600 --> 00:05:12,990
So what we need to do is we need to make a node with this value.

106
00:05:12,990 --> 00:05:14,640
So let's do that first.

107
00:05:14,640 --> 00:05:17,820
So for this we will make use of the node class over here.

108
00:05:17,820 --> 00:05:20,430
So we can say const node.

109
00:05:21,540 --> 00:05:25,350
Is equal to new node and then we pass the value to it.

110
00:05:25,860 --> 00:05:28,230
So this will call the constructor over here.

111
00:05:28,620 --> 00:05:30,210
And it will create a node.

112
00:05:30,210 --> 00:05:34,140
And the value of that particular node will be the value which we just passed to it.

113
00:05:34,140 --> 00:05:37,440
And this dot next is going to point to null at the moment.

114
00:05:37,470 --> 00:05:40,890
Now we just need to make this point to the head right now.

115
00:05:40,890 --> 00:05:45,840
Before that let's check whether the singly linked list at this point is null or not.

116
00:05:45,840 --> 00:05:52,590
So if not this dot head, that means if the head is null and the singly linked list is just an empty

117
00:05:52,590 --> 00:05:54,420
singly linked list and the head itself is null.

118
00:05:54,420 --> 00:05:59,280
If that is the case, then we have to make this particular node which we created the head.

119
00:05:59,280 --> 00:06:04,440
So we can say this dot head is equal to node, and the tail also is going to be the node itself, because

120
00:06:04,440 --> 00:06:05,790
there is just one node at the time.

121
00:06:05,790 --> 00:06:05,970
Right.

122
00:06:05,970 --> 00:06:08,460
So we can say this dot tail is equal to node.

123
00:06:08,460 --> 00:06:12,150
And then later once we are out of this we will increment the size.

124
00:06:12,150 --> 00:06:14,580
So we can say over here this dot size.

125
00:06:15,370 --> 00:06:16,210
Plus, plus.

126
00:06:17,000 --> 00:06:20,150
Now, why am I incrementing the size over here outside?

127
00:06:20,150 --> 00:06:22,790
Because we'll have an else condition also over here right now.

128
00:06:22,790 --> 00:06:24,800
In either case, we'll have to increment the size.

129
00:06:24,800 --> 00:06:27,080
So it's common to the if and else part.

130
00:06:27,080 --> 00:06:28,550
So that's why I've done it over here.

131
00:06:28,550 --> 00:06:33,200
Now again if if if the head is not null then what do we do.

132
00:06:33,200 --> 00:06:36,410
So we, we have seen that we have created a node.

133
00:06:36,410 --> 00:06:39,050
Now we need to make this point to the current head.

134
00:06:39,050 --> 00:06:42,290
So we can say in the else part node dot next.

135
00:06:44,790 --> 00:06:46,950
Is equal to this dot head.

136
00:06:50,510 --> 00:06:55,310
And then we need to make the new node the head so we can say this dot head.

137
00:06:56,280 --> 00:06:57,840
Is equal to node.

138
00:06:58,710 --> 00:06:59,130
All right.

139
00:06:59,130 --> 00:06:59,790
So that's it.

140
00:06:59,790 --> 00:07:04,650
So we have added at the head and let's say after this we're just going to return the complete singly

141
00:07:04,650 --> 00:07:05,160
linked list.

142
00:07:05,160 --> 00:07:07,500
So for this we can say return this.

143
00:07:08,310 --> 00:07:08,550
All right.

144
00:07:08,550 --> 00:07:09,900
So that's the end of this function.

145
00:07:09,900 --> 00:07:13,230
Now let's go ahead and write the next one which is to add at the tail.

146
00:07:13,230 --> 00:07:15,270
Now again the value is passed to us.

147
00:07:15,270 --> 00:07:18,480
So we're going to create a node out with this particular value.

148
00:07:18,480 --> 00:07:22,320
And for this we will make use of the node class which we have written over here.

149
00:07:22,320 --> 00:07:23,460
So let's use that.

150
00:07:23,460 --> 00:07:30,600
So over here we can say const node is equal to new node with the value which is passed to us.

151
00:07:30,960 --> 00:07:35,760
So after doing this we are going to check whether the singly linked list is null.

152
00:07:35,760 --> 00:07:39,210
So let's check if not this dot head.

153
00:07:39,240 --> 00:07:43,950
That means if head is null, that means there is nothing in this list at the moment.

154
00:07:43,950 --> 00:07:49,230
If this is the case, then we have to make this particular node which we just now created the head.

155
00:07:49,230 --> 00:07:51,360
So this dot head is going to be equal to node.

156
00:07:51,360 --> 00:07:55,350
And the tail also is going to be equal to this particular node.

157
00:07:55,350 --> 00:07:58,680
So we can say this dot tail is equal to node.

158
00:07:59,010 --> 00:07:59,700
All right.

159
00:07:59,700 --> 00:08:04,140
And if that is not the case if that is not the case then what do we do.

160
00:08:04,170 --> 00:08:09,000
We have to make the current tail point to this node because we are inserting at the tail.

161
00:08:09,000 --> 00:08:09,270
Right.

162
00:08:09,270 --> 00:08:14,460
So we can say this dot tail dot next is equal to node.

163
00:08:15,180 --> 00:08:20,850
And then we can say this dot tail is equal to node which is updating the tail to the node.

164
00:08:20,850 --> 00:08:24,210
So we have we have made the previous tail point to the node.

165
00:08:24,210 --> 00:08:27,060
And then we are updating the tail to this node over here.

166
00:08:27,060 --> 00:08:28,500
So that's what we're doing over here.

167
00:08:28,500 --> 00:08:32,190
And then because we have added a new node let's increment the size.

168
00:08:32,190 --> 00:08:35,340
So we can say this dot size plus plus.

169
00:08:36,070 --> 00:08:37,210
And that's it.

170
00:08:37,210 --> 00:08:41,740
So let's say after adding at the tail, we will just return the complete singly linked list.

171
00:08:41,740 --> 00:08:44,140
So over here we can say return this.

172
00:08:44,680 --> 00:08:45,010
All right.

173
00:08:45,010 --> 00:08:45,820
So that is it.

174
00:08:45,850 --> 00:08:47,590
Now we are done with this function.

175
00:08:47,590 --> 00:08:49,360
Now let's continue and complete these two.

176
00:08:49,390 --> 00:08:52,180
So the next one is to add at a particular index.

177
00:08:52,420 --> 00:08:56,680
Now if we want to add at an index it's going to be similar to what we've done over here.

178
00:08:56,680 --> 00:09:00,640
Now first we are going to check whether the index is valid.

179
00:09:00,640 --> 00:09:05,560
Now again in these two cases we did not have to check that because it was directly mentioned.

180
00:09:05,590 --> 00:09:09,100
The the function itself is to add at the head and add at the tail.

181
00:09:09,100 --> 00:09:13,330
Right now over here we could add at the head and tail using this function also.

182
00:09:13,330 --> 00:09:15,730
But then we will have to mention the relevant index.

183
00:09:15,730 --> 00:09:17,350
So let's get started with this.

184
00:09:17,350 --> 00:09:20,410
Now as we have checked in the get function.

185
00:09:20,410 --> 00:09:23,410
First let's check whether the index is valid or not.

186
00:09:23,410 --> 00:09:25,570
So let's use the same line of code over here.

187
00:09:25,570 --> 00:09:31,330
So first we are going to check if index is less than zero or index is greater than equal to this dot

188
00:09:31,330 --> 00:09:32,020
size.

189
00:09:32,200 --> 00:09:33,880
Again over.

190
00:09:33,880 --> 00:09:37,030
Previously we were checking for greater than or equal to this dot size.

191
00:09:37,030 --> 00:09:41,950
But because we are adding at the index, let's only check greater than this dot size.

192
00:09:41,950 --> 00:09:46,750
So if it is equal to this dot size we will just make the new node the tail.

193
00:09:46,750 --> 00:09:47,020
All right.

194
00:09:47,020 --> 00:09:48,160
So we will make it the tail.

195
00:09:48,160 --> 00:09:51,640
And we will make the existing tail point to the new node.

196
00:09:51,640 --> 00:09:54,910
So over here we are just checking if index is greater than this dot size.

197
00:09:54,910 --> 00:09:56,680
Then we will say it's invalid.

198
00:09:56,680 --> 00:09:59,560
Now in the in that case let's just return a message.

199
00:09:59,560 --> 00:10:01,240
We can say invalid index.

200
00:10:04,550 --> 00:10:04,940
All right.

201
00:10:04,940 --> 00:10:08,330
Now, if the index is not invalid, let's continue.

202
00:10:08,330 --> 00:10:11,660
So first let's check if index is equal to this dot size.

203
00:10:11,660 --> 00:10:19,430
So if index is equal to this dot size then we just need to insert at the tail right.

204
00:10:19,430 --> 00:10:21,440
So we just need to insert at the tail.

205
00:10:21,440 --> 00:10:23,510
Therefore we already have this function.

206
00:10:23,510 --> 00:10:27,410
So I'm just writing this code in a manner that we can reuse whatever we have written.

207
00:10:27,410 --> 00:10:30,290
So we already have the added tail function over here.

208
00:10:30,290 --> 00:10:32,300
So we can just return.

209
00:10:32,980 --> 00:10:34,420
This dot add a tail.

210
00:10:34,420 --> 00:10:35,020
So let's do that.

211
00:10:35,020 --> 00:10:38,320
So we can over here return this dot.

212
00:10:38,320 --> 00:10:39,520
Add a tail.

213
00:10:41,690 --> 00:10:43,670
And we are passing the value to it.

214
00:10:44,810 --> 00:10:45,230
All right.

215
00:10:45,230 --> 00:10:46,280
So that's it.

216
00:10:46,280 --> 00:10:49,940
So if index is equal to this dot size we're just adding at the tail.

217
00:10:49,940 --> 00:10:54,620
Now if that is not the case there is a possibility that index may be equal to zero.

218
00:10:55,450 --> 00:10:56,260
Right now.

219
00:10:56,260 --> 00:10:58,300
In this case we're just going to add at the head right.

220
00:10:58,300 --> 00:11:01,510
So again we can just return this dot add at head.

221
00:11:01,510 --> 00:11:03,640
And we're going to pass the value to it.

222
00:11:04,090 --> 00:11:04,600
All right.

223
00:11:04,600 --> 00:11:09,070
Now again if it's none of these if none of these is true then we continue.

224
00:11:09,070 --> 00:11:12,640
So in that case let's just create a node with this value.

225
00:11:12,640 --> 00:11:18,910
So we can say const node is equal to new node with this particular value which is passed to it.

226
00:11:19,390 --> 00:11:22,780
And then we have to find the previous index right.

227
00:11:22,780 --> 00:11:25,000
So again what is it that we're trying to do.

228
00:11:25,000 --> 00:11:27,310
Let's say the linked list looks something like this.

229
00:11:27,340 --> 00:11:33,130
We have a node with value one pointing to a node with value two pointing to a node with value three.

230
00:11:33,130 --> 00:11:35,530
And this is let's say pointing to null.

231
00:11:35,530 --> 00:11:37,900
Let's say this is how the linked list looks like.

232
00:11:37,900 --> 00:11:42,940
And let's say we want to insert at at position one or index one.

233
00:11:42,940 --> 00:11:44,860
So at index one we have two right.

234
00:11:44,860 --> 00:11:47,800
So let's say the value over here is five.

235
00:11:47,800 --> 00:11:53,410
So the output which we want is one pointing to five pointing to two.

236
00:11:53,410 --> 00:11:56,500
And then that points to three and that points to null.

237
00:11:56,500 --> 00:11:57,610
So this is what we want.

238
00:11:57,610 --> 00:12:00,460
If you want to insert five at index one.

239
00:12:00,460 --> 00:12:01,990
So what is it that we're doing.

240
00:12:01,990 --> 00:12:03,670
We have to find the previous node.

241
00:12:03,670 --> 00:12:06,880
So this is the node at the current index which is one.

242
00:12:06,880 --> 00:12:08,470
We have to find the previous one.

243
00:12:08,470 --> 00:12:13,000
And we have we have to make the previous point to the new node which we have just created.

244
00:12:13,000 --> 00:12:18,100
And the new node which we created has to point to the existing node at the index.

245
00:12:18,100 --> 00:12:19,930
So this is what we're going to do over here.

246
00:12:19,930 --> 00:12:20,320
All right.

247
00:12:20,320 --> 00:12:23,200
So first let's find the previous node for this.

248
00:12:23,200 --> 00:12:24,130
Let's have a variable.

249
00:12:24,130 --> 00:12:25,750
And we can just call it prev.

250
00:12:25,750 --> 00:12:28,390
And prev is going to be equal to this dot.

251
00:12:28,390 --> 00:12:30,940
Get at index minus one.

252
00:12:31,570 --> 00:12:35,170
Again we are making use of the get function which we have written over here.

253
00:12:35,170 --> 00:12:38,050
So this will return the node at the index.

254
00:12:38,050 --> 00:12:41,650
And over here the index which is passed to the function is index minus one.

255
00:12:41,650 --> 00:12:43,450
So this will give us the previous node.

256
00:12:43,450 --> 00:12:43,930
All right.

257
00:12:43,930 --> 00:12:47,440
Now once we have the previous node let's also have another variable.

258
00:12:47,440 --> 00:12:48,520
Let's just call it temp.

259
00:12:48,520 --> 00:12:51,280
Now this is going to be equal to prevnext.

260
00:12:53,630 --> 00:12:54,050
All right.

261
00:12:57,060 --> 00:13:00,780
Which in this case is going to be this one itself.

262
00:13:00,780 --> 00:13:01,050
Right.

263
00:13:01,050 --> 00:13:05,160
So the the node, the node at the index itself is going to be temp.

264
00:13:05,160 --> 00:13:09,210
Now what we have to do is we have just we have we just have to make these connections.

265
00:13:09,210 --> 00:13:10,860
That is prev dot next.

266
00:13:13,380 --> 00:13:14,880
Has to be equal to the node.

267
00:13:14,880 --> 00:13:15,540
All right.

268
00:13:16,280 --> 00:13:20,510
And then we have to say node.next is equal to temp.

269
00:13:21,210 --> 00:13:23,640
So you can see we just made these connections.

270
00:13:23,640 --> 00:13:24,270
Prev down.

271
00:13:24,270 --> 00:13:25,230
Next is equal to node.

272
00:13:25,230 --> 00:13:27,060
Is this connection from 1 to 5.

273
00:13:27,060 --> 00:13:28,380
And then node dot.

274
00:13:28,380 --> 00:13:31,560
Next is equal to temp is the connection from 5 to 2.

275
00:13:31,590 --> 00:13:33,780
So we just made these connections and that's it.

276
00:13:33,780 --> 00:13:36,270
So we have inserted the node successfully.

277
00:13:36,270 --> 00:13:38,190
And now let's just increment the size.

278
00:13:38,190 --> 00:13:40,950
So we can say this dot size plus plus.

279
00:13:41,040 --> 00:13:45,030
And after inserting the node let's just return the complete linked list.

280
00:13:45,030 --> 00:13:46,650
So we can say return this.

281
00:13:47,800 --> 00:13:48,070
All right.

282
00:13:48,070 --> 00:13:50,110
So that's the added index function.

283
00:13:50,110 --> 00:13:53,680
And finally let's go ahead and write the delete at index function.

284
00:13:53,680 --> 00:13:58,390
Now the interesting thing over here is we made use when we wrote the added index function.

285
00:13:58,390 --> 00:14:03,400
We have made use of the functions which you have previously written, which is added tail and added

286
00:14:03,400 --> 00:14:03,610
head.

287
00:14:03,610 --> 00:14:06,100
Right now in this case we don't have those functions.

288
00:14:06,100 --> 00:14:10,480
So we'll have to take care of all the possibilities in the function over here itself.

289
00:14:10,480 --> 00:14:12,730
So let's go ahead and do that now.

290
00:14:12,730 --> 00:14:15,640
First we are going to check if the index is valid.

291
00:14:15,640 --> 00:14:16,030
All right.

292
00:14:16,030 --> 00:14:21,700
So if the valid if the index has to be valid then it has to be not in not less than zero.

293
00:14:21,700 --> 00:14:24,370
And it should not be greater than equal to this dot size.

294
00:14:24,370 --> 00:14:26,200
So let's use the same code over here.

295
00:14:26,200 --> 00:14:32,500
So if index less than zero or index greater than equal to this dot size then we will just return invalid

296
00:14:32,500 --> 00:14:33,070
index.

297
00:14:33,950 --> 00:14:34,490
All right.

298
00:14:34,730 --> 00:14:36,020
So it can be just a message.

299
00:14:36,020 --> 00:14:37,070
Invalid index.

300
00:14:37,340 --> 00:14:41,900
Now again notice over here it's greater than equal to this dot size because it is zero index.

301
00:14:41,900 --> 00:14:47,330
So if there are let's say this if you are looking at this singly linked list over here you can see the

302
00:14:47,330 --> 00:14:50,060
index of the last node over here is going to be equal to two.

303
00:14:50,060 --> 00:14:51,470
And the size is equal to three.

304
00:14:51,470 --> 00:14:56,600
So if if you are saying delete index at position at index three then there is nothing over here.

305
00:14:56,600 --> 00:14:59,540
So that's why we have greater than equal to over here.

306
00:15:00,110 --> 00:15:00,530
All right.

307
00:15:00,530 --> 00:15:03,800
So if the index is not invalid then we proceed.

308
00:15:03,950 --> 00:15:07,280
Then let's just check if the index is equal to zero.

309
00:15:09,110 --> 00:15:12,260
Which, in which case we'll have to delete from the head.

310
00:15:14,290 --> 00:15:14,680
Right.

311
00:15:14,680 --> 00:15:16,090
So let's just have placeholders.

312
00:15:16,090 --> 00:15:23,380
And then the other possibility is if index is equal to this dot size minus one.

313
00:15:24,550 --> 00:15:26,680
Which means that we have to delete the tail.

314
00:15:26,680 --> 00:15:26,920
Right?

315
00:15:26,920 --> 00:15:28,150
So delete the tail.

316
00:15:29,610 --> 00:15:32,940
And then there is another possibility which is the generic case, right?

317
00:15:32,940 --> 00:15:33,960
Which is something else.

318
00:15:33,960 --> 00:15:35,100
Delete another node.

319
00:15:38,040 --> 00:15:38,280
All right.

320
00:15:38,280 --> 00:15:39,780
So these are the three possibilities.

321
00:15:39,780 --> 00:15:41,700
So let's go ahead and fill these parts.

322
00:15:41,700 --> 00:15:44,100
So first if you are going to delete at the head.

323
00:15:44,100 --> 00:15:45,210
So what do we do.

324
00:15:45,210 --> 00:15:47,280
We'll need a temporary variable.

325
00:15:47,280 --> 00:15:51,450
Let's say over here we are going to return the node that we are deleting.

326
00:15:51,450 --> 00:15:51,690
All right.

327
00:15:51,690 --> 00:15:54,240
So let me just write a comment over here.

328
00:15:56,260 --> 00:15:59,200
We will return the node that we are deleting.

329
00:16:05,450 --> 00:16:10,430
Again, you can ask your interviewer if this is fine and if he or she is fine with that.

330
00:16:10,430 --> 00:16:12,470
So let's now implement it in this manner.

331
00:16:12,470 --> 00:16:17,270
And if you want the complete linked list after deleting, you can just return this as we did in the

332
00:16:17,270 --> 00:16:18,260
case of addition.

333
00:16:18,260 --> 00:16:19,460
Now let's proceed.

334
00:16:19,460 --> 00:16:21,020
Let's say we are deleting the head.

335
00:16:21,020 --> 00:16:24,410
So because we want to return the node that we are deleting.

336
00:16:24,410 --> 00:16:25,400
So let's store it.

337
00:16:25,400 --> 00:16:28,250
So let's say let temp is equal to this dot head.

338
00:16:29,030 --> 00:16:29,600
All right.

339
00:16:29,600 --> 00:16:35,420
And then we are going to say this dot head is equal to head dot next temp dot next.

340
00:16:38,010 --> 00:16:39,420
So what does this mean?

341
00:16:39,420 --> 00:16:41,280
We are making the next node.

342
00:16:41,280 --> 00:16:43,620
Let's say we have this linked list over here.

343
00:16:43,620 --> 00:16:45,780
So temp is going to be node one.

344
00:16:45,780 --> 00:16:48,030
And then temp dot next is two.

345
00:16:48,060 --> 00:16:49,500
So we are making two the head.

346
00:16:49,500 --> 00:16:52,320
So we're saying this dot head is equal to the next node.

347
00:16:52,320 --> 00:16:53,850
So that is what we're doing over here.

348
00:16:54,090 --> 00:16:54,450
All right.

349
00:16:54,450 --> 00:16:56,160
And then we will just decrement the size.

350
00:16:56,160 --> 00:16:59,190
So this dot size minus minus.

351
00:17:00,270 --> 00:17:00,780
All right.

352
00:17:00,780 --> 00:17:06,930
And then finally we also have to check if this was the only node present in this list.

353
00:17:06,930 --> 00:17:11,370
So after removing the head let's check whether the size became zero.

354
00:17:11,370 --> 00:17:19,290
So if this dot size is equal to zero in that case we have to change the tail also to null right.

355
00:17:19,290 --> 00:17:20,430
So this dot tail.

356
00:17:21,610 --> 00:17:25,180
Is equal to null because we are tracking the head and the tail.

357
00:17:25,180 --> 00:17:26,440
So that's why we have to do this.

358
00:17:26,440 --> 00:17:29,740
If you don't do this, then the tail is not getting updated right.

359
00:17:29,740 --> 00:17:31,480
And we have removed every node.

360
00:17:31,480 --> 00:17:37,630
So the tail has to be updated only if you are deleting from the head where the singly linked list just

361
00:17:37,630 --> 00:17:42,250
has one node, in which case the head and the tail is the same node itself.

362
00:17:42,280 --> 00:17:43,360
Now that's it.

363
00:17:43,360 --> 00:17:48,790
So after this we can just return the node which we deleted, which is temp, which is stored in temp

364
00:17:48,790 --> 00:17:49,150
over here.

365
00:17:49,150 --> 00:17:49,510
Right.

366
00:17:49,510 --> 00:17:52,120
Because we have let temp is equal to this dot head.

367
00:17:52,150 --> 00:17:52,780
That's it.

368
00:17:52,780 --> 00:17:54,670
So that is deleting from the head.

369
00:17:54,670 --> 00:17:58,330
Now let's proceed and take a look at deleting from the tail.

370
00:17:58,330 --> 00:18:01,360
Now again for this let's store the old tail.

371
00:18:01,360 --> 00:18:05,920
So let's say let old tail is equal to this dot tail.

372
00:18:08,190 --> 00:18:11,040
And then we are going to have a new tail, right?

373
00:18:11,040 --> 00:18:13,080
So we have to find the new tail.

374
00:18:13,080 --> 00:18:18,180
So the new tail is going to be equal to this dot.

375
00:18:18,180 --> 00:18:20,310
Get at index minus one.

376
00:18:20,310 --> 00:18:20,850
Right.

377
00:18:22,180 --> 00:18:23,170
Why is that so?

378
00:18:23,170 --> 00:18:28,390
So in this case the index is equal to the size minus one.

379
00:18:28,390 --> 00:18:29,470
So let's take an example.

380
00:18:29,470 --> 00:18:32,170
Let's say again we have this example over here.

381
00:18:32,170 --> 00:18:34,270
So let's just copy it and get it over here.

382
00:18:34,750 --> 00:18:36,520
Now let's say we are delete.

383
00:18:36,520 --> 00:18:38,500
And the index over here is equal to two.

384
00:18:38,530 --> 00:18:41,380
So the size is three and three minus one is two.

385
00:18:41,410 --> 00:18:43,090
So let's say index is equal to two.

386
00:18:43,120 --> 00:18:44,860
So we want to delete this node.

387
00:18:44,860 --> 00:18:48,820
So we are going to find the previous node right which is index minus one.

388
00:18:48,820 --> 00:18:50,650
So two minus one is equal to one.

389
00:18:50,650 --> 00:18:56,290
So when we get the node at index one that's going to be the previous node which is this one over here.

390
00:18:56,290 --> 00:18:56,680
All right.

391
00:18:56,680 --> 00:18:58,600
So this is going to be the previous node.

392
00:18:58,600 --> 00:19:04,150
And now because we are removing the tail this is the previous node is going to be the new tail.

393
00:19:04,360 --> 00:19:06,550
So we have just found the previous node.

394
00:19:06,550 --> 00:19:08,320
And let's just call it new tail.

395
00:19:08,320 --> 00:19:12,370
And then we have to set the tail of the linked list to the new tail.

396
00:19:12,370 --> 00:19:15,520
So we can say this dot tail is equal to new tail.

397
00:19:15,880 --> 00:19:18,910
And then we also need this to point to null.

398
00:19:18,910 --> 00:19:21,910
Now currently this node over here is pointing to three.

399
00:19:21,910 --> 00:19:25,540
But because we are removing three we need to make two point to null.

400
00:19:25,540 --> 00:19:27,250
So that is what we are doing over here.

401
00:19:27,250 --> 00:19:29,230
So we need two to point to null.

402
00:19:29,230 --> 00:19:29,530
All right.

403
00:19:29,530 --> 00:19:30,790
So let's do that over here.

404
00:19:30,790 --> 00:19:33,640
We can say new tail dot next.

405
00:19:36,090 --> 00:19:37,770
Is equal to null.

406
00:19:38,340 --> 00:19:38,700
All right.

407
00:19:38,700 --> 00:19:39,330
So that's it.

408
00:19:39,330 --> 00:19:42,960
And now because we have removed a node let's decrement the size.

409
00:19:42,960 --> 00:19:45,060
So this dot size minus minus.

410
00:19:47,580 --> 00:19:51,390
Now over here, we don't need to check whether size is equal to zero.

411
00:19:51,390 --> 00:19:53,520
Let me just write a comment over here.

412
00:19:53,520 --> 00:19:56,520
Don't need to check if the size is equal to zero.

413
00:19:57,420 --> 00:20:01,410
Because in that case it would already be taken care in the previous right.

414
00:20:01,410 --> 00:20:03,750
So don't need to check if size.

415
00:20:04,610 --> 00:20:08,270
Is equal to zero because this would already be taken care over here.

416
00:20:08,270 --> 00:20:08,570
Right?

417
00:20:08,570 --> 00:20:15,830
So if the index is equal to this dot size minus one, and there is only one node in the index in the

418
00:20:15,830 --> 00:20:18,680
singly linked list, then the index would be zero itself, right.

419
00:20:18,680 --> 00:20:21,560
So we are already taking care of that possibility over here.

420
00:20:21,560 --> 00:20:24,500
So we won't come here itself if there is just one node.

421
00:20:24,500 --> 00:20:30,110
So that's why we don't need to check whether the size became zero after we decrement the size of the

422
00:20:30,110 --> 00:20:35,420
linked list, and then we will just return the old tail, which is the node that we have deleted.

423
00:20:35,420 --> 00:20:37,610
So we can say return old tail.

424
00:20:40,410 --> 00:20:41,250
All right, so that is it.

425
00:20:41,250 --> 00:20:46,290
So we have, uh, taken care of the function where we are deleting at the tail.

426
00:20:46,290 --> 00:20:49,710
And then finally we have the condition of deleting another node.

427
00:20:49,710 --> 00:20:51,090
So let's continue with that.

428
00:20:51,630 --> 00:20:54,060
Let's again take a look at this example for this.

429
00:20:54,060 --> 00:20:57,300
So let's say this is the singly linked list.

430
00:20:57,300 --> 00:21:00,810
Now let's say we want to let's say we have three also over here.

431
00:21:00,810 --> 00:21:01,200
All right.

432
00:21:01,200 --> 00:21:04,230
And let's say we want to delete this node over here which is two.

433
00:21:04,230 --> 00:21:06,930
Now in this case we have to find the previous node.

434
00:21:06,930 --> 00:21:11,580
And we need to make the previous node point to the next node of this particular node.

435
00:21:11,580 --> 00:21:13,470
That is what we will do over here now.

436
00:21:13,470 --> 00:21:15,600
So let's go ahead and find the previous node.

437
00:21:15,600 --> 00:21:19,380
So we can say let prev is equal to this dot.

438
00:21:19,380 --> 00:21:21,510
Get at index minus one.

439
00:21:22,780 --> 00:21:24,850
So this will give us the previous node.

440
00:21:24,850 --> 00:21:28,000
And then let's also store the node that we want to delete.

441
00:21:28,000 --> 00:21:30,490
So let deleted node.

442
00:21:31,460 --> 00:21:33,650
Is equal to prevnext.

443
00:21:36,940 --> 00:21:37,300
All right.

444
00:21:37,300 --> 00:21:38,920
So that's the node that we want to delete.

445
00:21:38,920 --> 00:21:40,210
So prev is equal to one.

446
00:21:40,210 --> 00:21:43,960
And prev dot next will give us two which is the node at index one.

447
00:21:43,960 --> 00:21:46,330
And let's say we want to delete that particular node.

448
00:21:46,330 --> 00:21:49,150
So then we just go ahead and say prevnext.

449
00:21:51,170 --> 00:21:53,030
Is equal to deleted node.

450
00:21:54,470 --> 00:21:55,640
Dot next.

451
00:21:58,930 --> 00:21:59,290
Right.

452
00:21:59,290 --> 00:22:02,290
So we are making this connection from 1 to 3.

453
00:22:02,320 --> 00:22:03,940
So that is this line of code.

454
00:22:03,940 --> 00:22:08,410
And then we will just decrement the size because we have deleted a particular node.

455
00:22:08,410 --> 00:22:10,960
So we can say this dot size minus minus.

456
00:22:11,500 --> 00:22:14,020
And we can return the node that we have deleted.

457
00:22:14,020 --> 00:22:16,090
So return deleted node.

458
00:22:17,870 --> 00:22:18,620
And that's it.

459
00:22:18,620 --> 00:22:20,000
So this should work.

460
00:22:20,000 --> 00:22:22,880
Now we're done with writing all the instance functions.

461
00:22:22,880 --> 00:22:23,960
Instance methods.

462
00:22:23,960 --> 00:22:26,180
So let's go ahead and test our code.

463
00:22:26,990 --> 00:22:32,600
Let's say we want to use our code and first create a singly linked list that looks like this.

464
00:22:32,600 --> 00:22:35,300
Let me just draw this over here so that we can visualize it.

465
00:22:35,300 --> 00:22:39,620
So let's say we want one which points to two and which points to three.

466
00:22:39,620 --> 00:22:41,480
And this points to null.

467
00:22:41,750 --> 00:22:45,410
So let's go ahead and create this singly linked list using our code.

468
00:22:45,410 --> 00:22:47,390
So first let's add at the head.

469
00:22:47,390 --> 00:22:53,120
So let's use the add at head um for instance methods to insert this one over here.

470
00:22:53,120 --> 00:23:00,080
So let's we have already created an object SL so we can just say SL dot add at head.

471
00:23:01,280 --> 00:23:03,590
And let's pass in the value as one.

472
00:23:05,250 --> 00:23:05,580
All right.

473
00:23:05,850 --> 00:23:07,530
So let's go ahead and run the code.

474
00:23:13,890 --> 00:23:14,400
All right.

475
00:23:14,400 --> 00:23:17,130
So you can see we are getting back a singly linked list.

476
00:23:17,130 --> 00:23:19,050
And it has one node.

477
00:23:19,050 --> 00:23:19,950
So that's working.

478
00:23:19,950 --> 00:23:21,030
So let's take a look at it.

479
00:23:21,030 --> 00:23:23,250
So the head is having the value one.

480
00:23:23,250 --> 00:23:25,350
The node with value one the size is one.

481
00:23:25,350 --> 00:23:27,210
And the tail also is the same node.

482
00:23:27,210 --> 00:23:28,380
So yes this is working.

483
00:23:28,380 --> 00:23:31,260
So let's continue building this singly linked list over here.

484
00:23:31,260 --> 00:23:33,390
Now let's test the added tail.

485
00:23:33,390 --> 00:23:38,130
So let's say we want to add uh this two over here at the tail.

486
00:23:38,130 --> 00:23:39,450
So let's go ahead and do that.

487
00:23:39,450 --> 00:23:42,960
So we can have SL dot add at tail.

488
00:23:43,730 --> 00:23:45,410
And the value is two.

489
00:23:45,410 --> 00:23:46,070
All right.

490
00:23:47,570 --> 00:23:49,010
So let's take a look.

491
00:23:49,010 --> 00:23:50,900
So we have the singly linked list.

492
00:23:50,900 --> 00:23:52,010
The size is two.

493
00:23:52,010 --> 00:23:55,340
And you can see the head is one and the tail is two.

494
00:23:55,340 --> 00:23:57,710
So we have built these two nodes.

495
00:23:57,710 --> 00:23:58,580
So it's working.

496
00:23:58,580 --> 00:24:01,490
One is pointing to two and then two is pointing to null.

497
00:24:01,490 --> 00:24:02,750
So yes that's working.

498
00:24:02,750 --> 00:24:05,420
Now let's again add three over here.

499
00:24:05,420 --> 00:24:07,310
So let's use the add at position.

500
00:24:07,310 --> 00:24:10,160
So let's take a look at our added position over here.

501
00:24:10,160 --> 00:24:15,920
Now we are checking if index is greater than this dot size only for returning an invalid index.

502
00:24:15,920 --> 00:24:17,210
So let's just check that first.

503
00:24:17,210 --> 00:24:23,900
So let's say we say SL dot add at index and we pass the value 012.

504
00:24:23,900 --> 00:24:25,310
Let's say we pass the value three.

505
00:24:25,310 --> 00:24:25,760
All right.

506
00:24:25,760 --> 00:24:28,550
So the size currently is two.

507
00:24:28,580 --> 00:24:30,860
We are having an index which is greater than two.

508
00:24:30,860 --> 00:24:32,570
And let's add it.

509
00:24:32,570 --> 00:24:35,660
So over here you can see we are getting invalid index.

510
00:24:35,660 --> 00:24:37,190
So this is not valid.

511
00:24:37,190 --> 00:24:39,920
But if we have this as two right.

512
00:24:39,920 --> 00:24:40,940
The index is two.

513
00:24:40,940 --> 00:24:43,220
And let's say the value is equal to three.

514
00:24:43,220 --> 00:24:44,600
And that's the correct order right.

515
00:24:44,600 --> 00:24:45,410
So let's just check that.

516
00:24:45,410 --> 00:24:50,180
So in our added index index is the first parameter and value is the second parameter.

517
00:24:50,180 --> 00:24:52,940
So let's add at index two the value three.

518
00:24:53,570 --> 00:24:58,010
And now you can see we have a linked list with the size equal to three.

519
00:24:58,040 --> 00:25:02,000
The head node is a node with value one, which is correct.

520
00:25:02,000 --> 00:25:03,590
The tail has value three.

521
00:25:03,590 --> 00:25:07,400
One is pointing to two, which is pointing to three, which is pointing to null.

522
00:25:07,400 --> 00:25:08,690
So yes this is working.

523
00:25:08,690 --> 00:25:09,170
All right.

524
00:25:09,170 --> 00:25:13,550
So we have tested the added head, added tail and added index function.

525
00:25:13,550 --> 00:25:19,970
Now let's try to get uh now let's try to get the node at a particular index using the get method that

526
00:25:19,970 --> 00:25:20,600
we have written.

527
00:25:20,600 --> 00:25:22,130
So this is the singly linked list.

528
00:25:22,130 --> 00:25:24,110
Now let's use the get function.

529
00:25:24,110 --> 00:25:25,910
So over here itself we can try that.

530
00:25:25,910 --> 00:25:27,260
So let's go ahead.

531
00:25:27,260 --> 00:25:29,030
So we have the singly linked list over here.

532
00:25:29,030 --> 00:25:31,220
Let's say SL dot get.

533
00:25:32,210 --> 00:25:34,910
And we want what is there at index two.

534
00:25:35,360 --> 00:25:38,870
So that should give us the node three because this is zero one and two.

535
00:25:38,870 --> 00:25:39,620
This is two right.

536
00:25:39,620 --> 00:25:40,610
So this is index two.

537
00:25:40,640 --> 00:25:42,560
So we're getting node three which is correct.

538
00:25:42,560 --> 00:25:45,020
So we have the value three which is correct.

539
00:25:45,020 --> 00:25:46,130
And its next is null.

540
00:25:46,130 --> 00:25:47,150
So this is working.

541
00:25:47,150 --> 00:25:48,650
So the get function is also working.

542
00:25:48,650 --> 00:25:54,350
Now if we have get and then we are adding an index like ten then we should get minus one.

543
00:25:54,350 --> 00:25:57,350
Yes we are getting minus one because this is an invalid index.

544
00:25:57,350 --> 00:25:57,860
All right.

545
00:25:57,860 --> 00:25:59,420
So our functions are working.

546
00:25:59,420 --> 00:26:03,020
Now let's go ahead and test delete at index function.

547
00:26:03,020 --> 00:26:05,240
So let's say we want to delete the head.

548
00:26:05,240 --> 00:26:07,730
So we could delete the first node over here.

549
00:26:07,730 --> 00:26:09,320
So let's go ahead and test that over here.

550
00:26:09,320 --> 00:26:12,470
So we can say SL dot delete at index.

551
00:26:12,470 --> 00:26:14,720
And we pass in the index zero.

552
00:26:16,160 --> 00:26:19,130
Now we are getting back the node which we are deleting.

553
00:26:19,130 --> 00:26:20,930
So that's what we want to do to do right.

554
00:26:20,930 --> 00:26:21,800
So we are delete.

555
00:26:21,800 --> 00:26:23,660
We have deleted the node with value one.

556
00:26:23,660 --> 00:26:24,980
So we're getting this back.

557
00:26:24,980 --> 00:26:28,490
Now if you want to take a look at the singly linked list let's do that.

558
00:26:28,490 --> 00:26:33,800
So over here you can see the size is two which is correct because we have removed this index over this

559
00:26:33,800 --> 00:26:34,550
node over here.

560
00:26:34,550 --> 00:26:37,640
And the head has value two and the tail has value three.

561
00:26:37,640 --> 00:26:39,800
So two is pointing to three which is correct.

562
00:26:39,890 --> 00:26:40,880
Three is pointing to null.

563
00:26:40,880 --> 00:26:41,300
All right.

564
00:26:41,300 --> 00:26:42,500
So this is working.

565
00:26:42,500 --> 00:26:46,130
So we have tested all the functions and it's working.

566
00:26:46,130 --> 00:26:50,120
Now let's take a quick look at how the code is working and walk through it.

567
00:26:50,120 --> 00:26:53,240
So first we take a look at the get index function over here.

568
00:26:53,240 --> 00:26:55,400
Now let me just grab a pen for this.

569
00:26:58,220 --> 00:26:58,730
All right.

570
00:26:58,730 --> 00:27:02,210
Now, let's say over here, we have this singly linked list already.

571
00:27:02,210 --> 00:27:05,630
And let's say the index which is passed is equal to two.

572
00:27:05,660 --> 00:27:08,120
So we want to get the node at index two.

573
00:27:08,150 --> 00:27:10,460
So first we check if the index is valid.

574
00:27:10,460 --> 00:27:13,580
So we can see over here the index is valid right.

575
00:27:13,580 --> 00:27:17,360
So index is not greater than equal to size which is three size is three.

576
00:27:17,360 --> 00:27:19,130
So the index is not invalid.

577
00:27:19,130 --> 00:27:22,070
So we continue and we have the counter equal to zero.

578
00:27:22,070 --> 00:27:27,860
And then the current is going to point at this head this node over here and then counter is zero and

579
00:27:27,860 --> 00:27:28,490
index is two.

580
00:27:28,520 --> 00:27:29,540
So they are not equal.

581
00:27:29,540 --> 00:27:31,160
So we're going to move current ahead.

582
00:27:31,160 --> 00:27:35,180
So current is equal to current dot next and counter is incremented to one.

583
00:27:35,180 --> 00:27:37,460
Again we check is one equal to two.

584
00:27:37,460 --> 00:27:38,570
No that's not the case.

585
00:27:38,570 --> 00:27:44,510
So current is increased is moved ahead to current dot next and the counter is incremented to two.

586
00:27:44,510 --> 00:27:47,570
Now we check is the counter equal to the index.

587
00:27:47,570 --> 00:27:48,770
Yes two is equal to two.

588
00:27:48,800 --> 00:27:52,460
So we come out of the while loop and we will just return this node over here.

589
00:27:52,460 --> 00:27:54,590
So that is how the get function works.

590
00:27:54,590 --> 00:27:54,890
All right.

591
00:27:54,890 --> 00:27:58,160
So let's go ahead and look at the other possibilities also.

592
00:27:58,160 --> 00:27:59,780
So we go to the next function.

593
00:27:59,780 --> 00:28:03,530
Now let's take the function added head and see what's happening.

594
00:28:06,460 --> 00:28:10,270
So let's say we want to add a value for at the head.

595
00:28:10,270 --> 00:28:11,740
So let's take that example.

596
00:28:11,740 --> 00:28:13,810
So the value let's say is passed as four.

597
00:28:13,810 --> 00:28:17,620
Now we will go ahead and create a new node with the value four over here.

598
00:28:17,620 --> 00:28:19,780
And then we are checking if the head is null.

599
00:28:19,780 --> 00:28:21,040
The head is not null right.

600
00:28:21,040 --> 00:28:23,680
So there are already nodes in the singly linked list.

601
00:28:23,680 --> 00:28:29,020
So we come over here and we are going to say node dot next is equal to this dot head.

602
00:28:29,020 --> 00:28:30,040
So this is the current head.

603
00:28:30,040 --> 00:28:34,330
So we are making this connection over here node dot next is equal to this dot head.

604
00:28:34,330 --> 00:28:36,700
And then we are saying this dot head is equal to node.

605
00:28:36,700 --> 00:28:39,400
So we are making this node over here as the head.

606
00:28:39,400 --> 00:28:41,230
And then we are incrementing the size.

607
00:28:41,230 --> 00:28:43,090
So the size is incremented to four.

608
00:28:43,090 --> 00:28:45,610
And then we are returning the whole singly linked list.

609
00:28:45,610 --> 00:28:48,490
So return this will return the whole singly linked list.

610
00:28:48,490 --> 00:28:50,620
So this is how the added head function works.

611
00:28:50,620 --> 00:28:54,430
Now let's take a look at the other functions which is added tail.

612
00:28:54,430 --> 00:28:55,660
The next one is added tail.

613
00:28:55,660 --> 00:29:00,880
So let's say again we come back to this singly linked list over here for the example.

614
00:29:00,880 --> 00:29:02,770
And then let's take a look over here.

615
00:29:02,770 --> 00:29:05,260
Let's say again the value is something like seven.

616
00:29:05,260 --> 00:29:06,850
So we have the seven over here.

617
00:29:06,850 --> 00:29:10,240
So we come over here and we create a node with value seven.

618
00:29:10,240 --> 00:29:12,010
And we check if the head is null.

619
00:29:12,010 --> 00:29:12,940
The head is not null.

620
00:29:12,940 --> 00:29:17,860
So we come over here and we are going to say this dot tail dot next is equal to node.

621
00:29:17,860 --> 00:29:19,360
That is this is the current tail.

622
00:29:19,360 --> 00:29:22,750
We are making this point to the node over here which is seven.

623
00:29:23,080 --> 00:29:23,560
All right.

624
00:29:23,560 --> 00:29:25,900
And then we are saying this dot tail is equal to node.

625
00:29:25,900 --> 00:29:28,090
So this over here is made the tail.

626
00:29:28,890 --> 00:29:33,420
And remember, this is already pointing to null because that's how we have written the node class,

627
00:29:33,420 --> 00:29:33,570
right?

628
00:29:33,570 --> 00:29:36,030
So this will already be pointing to null.

629
00:29:36,030 --> 00:29:41,490
And this connection is removed because we are making the previous tail point to this node over here.

630
00:29:41,490 --> 00:29:45,360
And then we increment the size and we are just returning the whole singly linked list.

631
00:29:45,360 --> 00:29:46,590
So this is how it works.

632
00:29:46,710 --> 00:29:47,190
All right.

633
00:29:47,190 --> 00:29:51,930
Now let's go ahead and look at the next function which is to add at a particular index.

634
00:29:52,440 --> 00:29:56,520
Again let's take this as the uh sample singly linked list.

635
00:29:56,520 --> 00:29:58,260
So let's just scroll down.

636
00:30:00,640 --> 00:30:03,250
So we have our added index function over here.

637
00:30:03,250 --> 00:30:09,280
Let's say we want to add at index um one which is this over here zero one and two.

638
00:30:09,310 --> 00:30:09,670
All right.

639
00:30:09,670 --> 00:30:12,550
Because we have already discussed adding at the head and the tail.

640
00:30:12,550 --> 00:30:14,800
So that's why I'm taking index as one.

641
00:30:14,800 --> 00:30:16,990
And let's say the value is equal to seven.

642
00:30:16,990 --> 00:30:19,330
So first we are checking if the index is valid.

643
00:30:19,330 --> 00:30:20,800
Now the index is valid.

644
00:30:20,800 --> 00:30:24,730
Now over here we are checking if the index is equal to the size which is three.

645
00:30:24,730 --> 00:30:25,000
Right.

646
00:30:25,000 --> 00:30:29,320
So if the index was equal to three we would have just called the added tail function.

647
00:30:29,320 --> 00:30:33,940
And we have already discussed that function that would have that function would have added the value

648
00:30:33,940 --> 00:30:36,550
the with seven as a node at the tail.

649
00:30:36,550 --> 00:30:40,510
Now if the index is equal to zero, we are just calling the added head function.

650
00:30:40,510 --> 00:30:43,000
And this node over here would be added at the head.

651
00:30:43,000 --> 00:30:44,830
Now over here it's not the condition.

652
00:30:44,830 --> 00:30:48,580
So we continue and we create a new node with this value seven.

653
00:30:48,580 --> 00:30:51,160
So we are having a node with value seven over here.

654
00:30:51,160 --> 00:30:55,510
And then we are going to say prev is equal to this dot get index minus one.

655
00:30:55,510 --> 00:30:56,740
So index is one.

656
00:30:56,740 --> 00:30:59,140
So one minus one will give us zero.

657
00:30:59,140 --> 00:31:02,950
So we are going to get the node at index zero which is this one over here.

658
00:31:02,950 --> 00:31:04,720
So this is going to be equal to prev.

659
00:31:04,720 --> 00:31:08,050
And then over here we are going to say temp is equal to prev next.

660
00:31:08,050 --> 00:31:11,740
So temp is this node over here which is prev dot next.

661
00:31:11,740 --> 00:31:13,420
And then we are going to say prev dot.

662
00:31:13,420 --> 00:31:15,070
Next is equal to node right.

663
00:31:15,070 --> 00:31:18,700
So this over here is going to point to the node which is seven.

664
00:31:19,510 --> 00:31:24,070
So we are making this connection and then we are seeing node dot next is equal to ten which is this

665
00:31:24,070 --> 00:31:25,000
connection over here.

666
00:31:25,920 --> 00:31:26,250
Right.

667
00:31:26,250 --> 00:31:29,850
And this connection is removed because we're seeing PrevNext is equal to node.

668
00:31:29,880 --> 00:31:30,420
All right.

669
00:31:30,420 --> 00:31:30,840
That's it.

670
00:31:30,840 --> 00:31:32,910
So now one will point to seven.

671
00:31:33,390 --> 00:31:35,730
And we can see seven is pointing to two.

672
00:31:35,730 --> 00:31:38,970
And two is pointing to three which is pointing to null.

673
00:31:38,970 --> 00:31:45,030
In this way we have inserted the node with value which is passed over here at the index which is one.

674
00:31:45,030 --> 00:31:47,760
So you can see now this node is at index one.

675
00:31:48,300 --> 00:31:48,690
All right.

676
00:31:48,690 --> 00:31:51,810
And then we are incrementing the size and returning the linked list.

677
00:31:51,810 --> 00:31:53,730
So this is how this function works.

678
00:31:53,730 --> 00:31:58,410
Now let's take a look at the last instance method that we have written over here which is the delete

679
00:31:58,410 --> 00:31:59,670
at index function.

680
00:31:59,670 --> 00:32:03,840
So again let's take this as the sample linked list which we have.

681
00:32:06,110 --> 00:32:07,850
And let's scroll down.

682
00:32:11,760 --> 00:32:13,830
So we have this function over here.

683
00:32:16,770 --> 00:32:17,850
Now what do we do?

684
00:32:17,850 --> 00:32:20,880
Let's say we want to delete at zero.

685
00:32:20,880 --> 00:32:24,300
If you want to delete this then it's going to be happening over here.

686
00:32:24,300 --> 00:32:26,610
So we see that the index is equal to zero.

687
00:32:26,610 --> 00:32:28,410
Then we will make this the temp.

688
00:32:28,410 --> 00:32:29,730
So this is going to be temp.

689
00:32:29,730 --> 00:32:32,730
And then we'll say this dot head is equal to temp dot next.

690
00:32:32,730 --> 00:32:35,100
So temp dot next is this node over here.

691
00:32:35,100 --> 00:32:36,810
And we're going to make this the head.

692
00:32:37,530 --> 00:32:39,120
And then we decrement the size.

693
00:32:39,120 --> 00:32:43,830
And if the size becomes zero that is if this was the node with just one node right.

694
00:32:43,830 --> 00:32:45,780
And then we are deleting this node over here.

695
00:32:45,780 --> 00:32:48,180
And we made this the head.

696
00:32:48,180 --> 00:32:50,280
So in this case head is pointing to null.

697
00:32:50,280 --> 00:32:53,160
We also need to make tail point to null right.

698
00:32:53,160 --> 00:32:54,870
So that's why we have this check over here.

699
00:32:54,870 --> 00:32:59,880
So if there was just one node over here then after removing this the size will become equal to zero.

700
00:32:59,880 --> 00:33:03,240
And in that case we will make the tail also equal to null.

701
00:33:03,240 --> 00:33:07,380
And then we are just returning temp which is the node that we have deleted.

702
00:33:07,380 --> 00:33:09,660
So that is how this part over here works.

703
00:33:09,660 --> 00:33:16,770
Now if the index is not equal to zero, let's say we wanted to uh pass an index which is equal to for

704
00:33:16,770 --> 00:33:18,360
example in this case two.

705
00:33:18,630 --> 00:33:20,520
So let's say the index is passed as two.

706
00:33:20,520 --> 00:33:21,000
All right.

707
00:33:21,000 --> 00:33:24,810
So we have the index two over here now 012.

708
00:33:24,810 --> 00:33:27,510
That's this, this uh part this place.

709
00:33:27,510 --> 00:33:31,650
So we actually want to delete the tail that would be coming to this part of the code.

710
00:33:31,650 --> 00:33:31,830
Right.

711
00:33:31,830 --> 00:33:34,200
So let's take a look at it.

712
00:33:34,960 --> 00:33:38,800
First what we do, we are going to store the old tail.

713
00:33:41,150 --> 00:33:44,360
We're going to store the old tail because we want to return it over here.

714
00:33:44,360 --> 00:33:44,660
Now.

715
00:33:44,660 --> 00:33:47,390
Old tail is going to be the tail at the moment, which is three.

716
00:33:47,390 --> 00:33:48,620
So this is three.

717
00:33:49,100 --> 00:33:55,520
And then we are going to calculate the find the new tail which is the node at index minus one.

718
00:33:55,520 --> 00:33:56,870
So index is equal to two.

719
00:33:56,870 --> 00:34:01,880
And we have seen that we came over here which means that index is equal to this dot size minus one.

720
00:34:01,880 --> 00:34:06,890
So we just need the previous node which is get index at index minus one.

721
00:34:06,890 --> 00:34:08,840
So which is equal to two minus one.

722
00:34:08,840 --> 00:34:11,150
This is two minus one which is equal to one.

723
00:34:11,150 --> 00:34:13,790
So we are going to get the node at index one which is this.

724
00:34:13,790 --> 00:34:16,160
So this is going to be equal to the new tail.

725
00:34:17,650 --> 00:34:18,100
All right.

726
00:34:18,100 --> 00:34:20,740
So again at this point it's just a variable.

727
00:34:20,740 --> 00:34:22,810
And now we have to set this to the tail.

728
00:34:22,810 --> 00:34:25,960
So for this we are going to say this dot tail is equal to new tail.

729
00:34:25,960 --> 00:34:27,520
So we are making this the tail.

730
00:34:28,190 --> 00:34:33,080
And at the moment two is pointing to three, but we need the tail to point to null.

731
00:34:33,080 --> 00:34:36,440
So over here we are saying new tail dot next is equal to null.

732
00:34:36,440 --> 00:34:38,180
So we are making this connection over here.

733
00:34:38,180 --> 00:34:41,660
So this connection is removed and it's pointing to null at the moment.

734
00:34:41,660 --> 00:34:42,260
And it is.

735
00:34:42,260 --> 00:34:45,710
And in this way we have removed the node at the tail.

736
00:34:45,710 --> 00:34:47,690
Now we just need to decrement the size.

737
00:34:47,690 --> 00:34:50,990
And we are returning the old tail which is this node over here.

738
00:34:50,990 --> 00:34:53,420
So this is how deleting at the tail works.

739
00:34:53,420 --> 00:34:54,680
Now let's continue.

740
00:34:54,680 --> 00:35:00,200
Now if we are deleting a node which is not at the tail and not at the head, then what do we do?

741
00:35:00,200 --> 00:35:02,840
Let's again take this same example over here.

742
00:35:07,030 --> 00:35:11,110
And let's say the index which is passed to us is equal to one.

743
00:35:11,140 --> 00:35:12,880
So this is zero, one and two.

744
00:35:12,880 --> 00:35:15,010
Let's say we want to delete this node over here.

745
00:35:16,520 --> 00:35:19,820
So we see that it is not the head and not the tail.

746
00:35:19,820 --> 00:35:21,440
So we will come over here, right?

747
00:35:21,440 --> 00:35:23,270
So we will come to this part of the code.

748
00:35:26,140 --> 00:35:29,200
And then again we go ahead and find the previous node.

749
00:35:29,590 --> 00:35:32,470
For this we use the get function which you have already written.

750
00:35:32,470 --> 00:35:35,410
So we get the node at index minus one.

751
00:35:35,410 --> 00:35:36,580
So that's going to be this.

752
00:35:36,580 --> 00:35:37,540
This is the pref.

753
00:35:37,540 --> 00:35:38,440
This is pref.

754
00:35:38,440 --> 00:35:42,400
And then we have the deleted node because we want to return it right.

755
00:35:42,400 --> 00:35:45,640
So we're going to store this particular node which is private dot next.

756
00:35:45,640 --> 00:35:50,170
And then we're just going to say prev dot next is equal to deleted node dot next.

757
00:35:50,170 --> 00:35:51,100
So deleted node.

758
00:35:51,280 --> 00:35:52,600
Next is this one over here.

759
00:35:52,600 --> 00:35:53,980
So we are saying prev dot.

760
00:35:53,980 --> 00:35:55,120
Next is this.

761
00:35:55,120 --> 00:35:56,530
So we are making this connection.

762
00:35:56,530 --> 00:35:59,410
And this connection which was there previously is removed.

763
00:35:59,410 --> 00:36:01,330
In this way this node is deleted.

764
00:36:01,330 --> 00:36:05,590
Then we reduce the size and we can just return the deleted node which is two.

765
00:36:05,620 --> 00:36:08,710
So this is how the delete at index function works.

766
00:36:08,710 --> 00:36:11,890
So we have taken a look at all the functions which we have written.