1
00:00:01,110 --> 00:00:02,370
Hello, my name is Typhoon.

2
00:00:02,370 --> 00:00:04,920
Welcome to another lecture of our oxalic course.

3
00:00:04,920 --> 00:00:10,980
In this lecture of our oxide course, you will learn about the removing an item from the linked list

4
00:00:11,010 --> 00:00:12,230
a d t.

5
00:00:12,390 --> 00:00:14,130
So let's get started.

6
00:00:26,220 --> 00:00:28,620
So similar to the inserting operation.

7
00:00:28,620 --> 00:00:35,230
The removing operation also has several cases, and there are three cases here.

8
00:00:35,250 --> 00:00:39,840
So firstly, let's actually make this here the first case.

9
00:00:40,590 --> 00:00:45,400
Here, the second case and the third case here.

10
00:00:45,420 --> 00:00:53,080
So similarly here, the removed in the first case, the removed item is in the head.

11
00:00:53,100 --> 00:00:55,410
So in the head.

12
00:00:57,320 --> 00:01:02,630
So which is index is equals to zero.

13
00:01:02,810 --> 00:01:04,880
So index.

14
00:01:05,850 --> 00:01:07,710
Equals to zero.

15
00:01:11,170 --> 00:01:16,720
And the second case is the removed items is in the tail.

16
00:01:16,720 --> 00:01:18,520
So it's in the tail.

17
00:01:19,770 --> 00:01:22,450
Tail and linked list.

18
00:01:22,470 --> 00:01:26,910
So index is our index is going to be index.

19
00:01:27,960 --> 00:01:29,770
Is going to be an.

20
00:01:31,860 --> 00:01:34,680
And minus one.

21
00:01:35,550 --> 00:01:39,130
In case of it's our removed item, it's going to be in the tail here.

22
00:01:39,150 --> 00:01:48,120
So the removed item here in the third case we have a remove item is in the other position of the linked

23
00:01:48,120 --> 00:01:48,270
list.

24
00:01:48,270 --> 00:01:53,010
So in this case, it's going to we're going to write it other here and let's actually use a different

25
00:01:53,010 --> 00:01:53,970
color for other.

26
00:01:56,870 --> 00:01:57,560
Other.

27
00:01:57,560 --> 00:02:00,200
And here then.

28
00:02:01,310 --> 00:02:02,990
It's going to be index.

29
00:02:04,880 --> 00:02:05,990
Index.

30
00:02:13,120 --> 00:02:15,280
Is going to be one.

31
00:02:16,480 --> 00:02:22,840
From one to index N minus two here.

32
00:02:22,840 --> 00:02:26,410
So here, actually, let's write it in the different color.

33
00:02:26,410 --> 00:02:28,090
So from.

34
00:02:30,150 --> 00:02:32,970
From index one.

35
00:02:33,000 --> 00:02:34,440
The first index.

36
00:02:36,040 --> 00:02:38,200
To hear from.

37
00:02:39,630 --> 00:02:40,560
To.

38
00:02:43,190 --> 00:02:43,850
Here.

39
00:02:43,850 --> 00:02:47,600
So from it's going to be in the other.

40
00:02:47,690 --> 00:02:51,020
In the third scenario, our index is index.

41
00:02:51,260 --> 00:02:59,360
From index first index and then from that from the first index until the N minus one index here.

42
00:02:59,360 --> 00:03:02,930
So which is the last index, but minus one here.

43
00:03:03,830 --> 00:03:05,090
So now.

44
00:03:07,010 --> 00:03:08,030
The first case here.

45
00:03:08,030 --> 00:03:12,500
Let's develop the first case and then we're going to create our another cases here.

46
00:03:12,500 --> 00:03:16,640
So first, actually, let's move this here.

47
00:03:18,530 --> 00:03:19,190
Yes.

48
00:03:21,350 --> 00:03:21,950
Here.

49
00:03:24,670 --> 00:03:25,600
Now.

50
00:03:26,720 --> 00:03:28,790
Let's implement the first.

51
00:03:29,960 --> 00:03:31,190
Search here.

52
00:03:31,190 --> 00:03:36,860
So we're going to create a new tree here, which is going to be here.

53
00:03:36,860 --> 00:03:44,390
So we're going to have we have here the remove heat, remove tail and just remove, which is this is

54
00:03:44,390 --> 00:03:46,280
the third case here.

55
00:03:46,280 --> 00:03:47,900
This is third case.

56
00:03:47,900 --> 00:03:50,210
Remove tail is second case.

57
00:03:50,920 --> 00:03:55,660
And remove heat is first case here.

58
00:03:55,930 --> 00:03:59,200
So now let's create our application.

59
00:03:59,200 --> 00:04:01,990
Firstly, we're going to create the case one here.

60
00:04:02,320 --> 00:04:05,110
So the implementation is straightforward here.

61
00:04:05,110 --> 00:04:10,600
So we're going to create we just need to point the heat pointer to the node, which is pointed by the

62
00:04:10,600 --> 00:04:12,450
next pointer of the current heat.

63
00:04:12,460 --> 00:04:16,330
In other words, the second element and delete the first element of the linked list.

64
00:04:16,330 --> 00:04:26,770
So here template the type name T and after that void linked list, we're going to create the.

65
00:04:28,580 --> 00:04:30,080
Remove heat here.

66
00:04:30,080 --> 00:04:33,890
So remove heat.

67
00:04:33,890 --> 00:04:42,200
And after that we can create a condition which is going to be do nothing if the if the list is empty.

68
00:04:42,230 --> 00:04:45,170
Since we don't have anything to remove in this list here.

69
00:04:45,170 --> 00:04:52,820
So my count, if our list count is zero, then just return and do nothing but.

70
00:04:54,140 --> 00:04:56,960
After that, we're going to save the current hit to new node.

71
00:04:56,960 --> 00:04:59,300
So in this case node here.

72
00:04:59,810 --> 00:05:02,090
Node and hit.

73
00:05:02,420 --> 00:05:07,340
And we will point the hit pointer to the element next to the current hit.

74
00:05:07,340 --> 00:05:17,990
So in this case it's going to be the hit equals hit and next year initialize hit to hit next here and

75
00:05:17,990 --> 00:05:23,660
after that now it's safe to remove the first element so delete node.

76
00:05:24,350 --> 00:05:24,950
Here.

77
00:05:24,950 --> 00:05:26,420
After that, we will.

78
00:05:29,750 --> 00:05:33,110
Decrement our count here, which is going to be minus one.

79
00:05:33,790 --> 00:05:35,200
So here.

80
00:05:37,860 --> 00:05:42,380
Decrease the one element from my count since we removed one from the heat.

81
00:05:42,450 --> 00:05:48,600
So as we can see in this code, regardless of the number of the length list element, the complexity

82
00:05:48,600 --> 00:05:55,380
of operation is zero and one, which is the best case scenario here.

83
00:05:57,140 --> 00:05:58,030
Zero one.

84
00:05:59,100 --> 00:06:00,060
So.

85
00:06:01,440 --> 00:06:03,180
For the removed tail operation.

86
00:06:03,180 --> 00:06:07,350
We have to traverse all list elements so that we have two less nodes.

87
00:06:07,350 --> 00:06:11,550
So which are indexes in minus one and N minus two.

88
00:06:11,550 --> 00:06:19,520
And then we set the next pointer to the next pointer of the end to, to the point of null.

89
00:06:19,530 --> 00:06:25,680
So after that we can safely remove the last node since the operation must traverse all list elements.

90
00:06:25,680 --> 00:06:31,110
So the complexity will be here zero here in the if we're going to write it here.

91
00:06:31,110 --> 00:06:34,770
So the complexity is going to be zero multiply by N.

92
00:06:34,770 --> 00:06:40,560
So here we're going to template template type.

93
00:06:41,480 --> 00:06:51,320
Typename t void the linked list we're going to hear t and after that we will remove tail.

94
00:06:52,010 --> 00:07:01,490
So after that, as we're going to as we did in this here, if my if count my count equals to zero,

95
00:07:01,520 --> 00:07:05,240
then return just do nothing.

96
00:07:05,420 --> 00:07:11,510
And after that, if list element is only one, just simply call the remove hit here.

97
00:07:11,510 --> 00:07:20,990
If my count is equal to one, then just simply call the return or remove hit here.

98
00:07:20,990 --> 00:07:24,650
So remove hit and after that we will return here.

99
00:07:24,650 --> 00:07:27,560
Since we removed and completed our operation here.

100
00:07:27,560 --> 00:07:31,940
And after that we need to start a start.

101
00:07:33,090 --> 00:07:33,480
Yeah.

102
00:07:33,480 --> 00:07:35,740
Start to find previous note from the heat.

103
00:07:35,760 --> 00:07:38,850
So in this case, we're going to create the here.

104
00:07:39,650 --> 00:07:40,250
Not.

105
00:07:41,270 --> 00:07:42,570
Not here to.

106
00:07:43,820 --> 00:07:46,160
And previous note.

107
00:07:49,840 --> 00:07:50,710
Hit here.

108
00:07:52,000 --> 00:07:59,650
And after that, we're going to create a candidate of items, candidate of removed items, which is

109
00:07:59,650 --> 00:08:01,270
the element next to the preview node.

110
00:08:01,300 --> 00:08:09,700
Here in this case, we're going to create the node t pointer here and hit points to next.

111
00:08:10,990 --> 00:08:15,460
After that, we will traverse elements until the last until the last elements here.

112
00:08:15,460 --> 00:08:23,650
So in this case, while while the node next here is not equal to null.

113
00:08:24,710 --> 00:08:25,580
Null.

114
00:08:25,610 --> 00:08:30,050
Then we're going to print node three.

115
00:08:30,080 --> 00:08:33,980
Previous node next here.

116
00:08:35,430 --> 00:08:36,290
Next.

117
00:08:36,300 --> 00:08:38,910
And after that node equals node.

118
00:08:40,010 --> 00:08:40,790
Next.

119
00:08:42,110 --> 00:08:51,470
So the then the pre note here previous note now became a tail so that the next pointer of the pre note

120
00:08:51,560 --> 00:08:52,380
points to null.

121
00:08:52,400 --> 00:09:02,090
So in order to do that we're going to create the pre note pre note here next and null here.

122
00:09:02,090 --> 00:09:12,290
So the tail is going to be pre note here so now it's safe to remove the last element delete delete note

123
00:09:12,290 --> 00:09:15,110
and after that we will.

124
00:09:16,790 --> 00:09:22,190
Decrease the decrement the size of our my count since the element is removed here.

125
00:09:22,190 --> 00:09:24,590
So the last operation is the remove operation.

126
00:09:24,590 --> 00:09:28,970
And here this is the complexity of this operation is going to be.

127
00:09:29,300 --> 00:09:31,610
Yeah, the complexity of this operation is going to be.

128
00:09:35,220 --> 00:09:36,150
Yeah, it is.

129
00:09:36,960 --> 00:09:39,660
Uh, it is the same with the heat.

130
00:09:39,660 --> 00:09:40,890
So it's going to be.

131
00:09:42,120 --> 00:09:43,950
Zero and one.

132
00:09:43,950 --> 00:09:51,300
So the best case scenario here and we can also develop our review operation.

133
00:09:51,510 --> 00:09:57,450
This is the last operation which we will remove the least element between the first and last element.

134
00:09:57,450 --> 00:10:02,160
So in this operation, we need to traverse the least element until the selected item is index.

135
00:10:02,160 --> 00:10:09,660
Selected indexes reached so similar to the index of insert operation, we need to find the element before

136
00:10:09,660 --> 00:10:11,760
and after selecting index.

137
00:10:11,760 --> 00:10:18,180
So after we find them we can link them together and then we can safely remove the element in the selected

138
00:10:18,180 --> 00:10:19,320
index here.

139
00:10:19,320 --> 00:10:24,660
So let's create our delete or remove operation here.

140
00:10:24,660 --> 00:10:40,620
So now template Typename here T and after that void the linked list t here and remove remove here just

141
00:10:40,620 --> 00:10:43,630
to remove which is going to get the index parameter here.

142
00:10:43,630 --> 00:10:49,150
And after that, if our list is empty, my count is empty zero.

143
00:10:49,180 --> 00:10:52,930
Then return and do nothing since we don't have anything to return.

144
00:10:52,930 --> 00:10:55,900
And after that let me actually check the lecture time.

145
00:10:55,900 --> 00:10:56,260
Yeah.

146
00:10:56,260 --> 00:10:58,210
So after that return here.

147
00:10:58,210 --> 00:11:00,100
So if our.

148
00:11:01,450 --> 00:11:04,000
And also we're going to also do the.

149
00:11:05,050 --> 00:11:14,200
If here if index is less than zero or index is greater than equal, index is greater than or equal to

150
00:11:14,200 --> 00:11:18,430
my count, then return.

151
00:11:20,430 --> 00:11:22,560
So awesome.

152
00:11:22,560 --> 00:11:26,370
And yeah, in this case, we're going to just return and do nothing.

153
00:11:26,370 --> 00:11:27,990
So if our.

154
00:11:28,830 --> 00:11:30,810
So in this case, it's going to be out of bounds.

155
00:11:30,810 --> 00:11:37,200
So if our index is less than zero or index is equal to or greater than zero, then this is the out of

156
00:11:37,200 --> 00:11:37,710
bounds.

157
00:11:37,710 --> 00:11:40,410
And here then return and do nothing.

158
00:11:40,410 --> 00:11:46,620
So if our, uh, if we don't have anything in our list, then also return signs.

159
00:11:46,620 --> 00:11:48,900
We don't have anything to remove here, so.

160
00:11:50,140 --> 00:11:52,930
Here, we will develop our.

161
00:11:54,040 --> 00:11:56,260
If our index is zero.

162
00:11:57,380 --> 00:12:00,800
Signs if our index is zero.

163
00:12:00,800 --> 00:12:07,490
So this means we are going to delete the first element since we already developed our the remove heat.

164
00:12:07,520 --> 00:12:09,920
Then we're just going to remove the heat here.

165
00:12:09,920 --> 00:12:16,160
So we will execute, remove heat and successfully executed here and removed item.

166
00:12:16,160 --> 00:12:24,740
So if the here after that if our removing or remove if our removing the current tail we're going to

167
00:12:24,740 --> 00:12:27,650
also add the else if here.

168
00:12:29,250 --> 00:12:32,580
Index and my count.

169
00:12:32,610 --> 00:12:33,780
Minus one.

170
00:12:34,640 --> 00:12:36,230
And remove tail.

171
00:12:36,980 --> 00:12:39,350
After that, we can also return here.

172
00:12:39,440 --> 00:12:43,910
So this is also successfully executed and we removed item from the list.

173
00:12:43,940 --> 00:12:48,260
Now let's get started with the our real remove method here.

174
00:12:48,260 --> 00:12:52,390
So now we're going to traverse the list here from the heat.

175
00:12:52,400 --> 00:12:59,960
So note to previous note, please note here and heat here.

176
00:13:00,980 --> 00:13:02,630
Not like this here heat.

177
00:13:02,630 --> 00:13:05,810
And we will find the element before the selected index.

178
00:13:05,810 --> 00:13:08,450
So we're going to create a for loop integer.

179
00:13:08,840 --> 00:13:11,120
Integer is zero here.

180
00:13:11,120 --> 00:13:21,350
E while e less than index minus one, then increment E plus e by one here, increment e by one.

181
00:13:21,350 --> 00:13:28,820
After that we will print here equals previous note pre note.

182
00:13:29,650 --> 00:13:30,520
Next.

183
00:13:31,900 --> 00:13:33,490
And here.

184
00:13:36,210 --> 00:13:39,870
We will the removal remove the element is after the preview node here.

185
00:13:39,870 --> 00:13:40,830
So we will.

186
00:13:41,040 --> 00:13:41,550
Oops.

187
00:13:41,790 --> 00:13:42,450
Here.

188
00:13:42,450 --> 00:13:42,780
Yeah.

189
00:13:42,780 --> 00:13:52,710
So here node t here and not the previous node and the next.

190
00:13:54,170 --> 00:13:55,100
Next year.

191
00:13:55,130 --> 00:14:01,500
After that, the node will be the neighborhood of the previous node.

192
00:14:01,520 --> 00:14:02,720
So if the node is removed.

193
00:14:02,720 --> 00:14:08,390
So in this case, we're going to do the node to the next node.

194
00:14:09,410 --> 00:14:10,280
Node.

195
00:14:10,820 --> 00:14:16,610
Yeah, the next node to the next node is going to be node here.

196
00:14:17,940 --> 00:14:18,720
Next.

197
00:14:20,240 --> 00:14:23,700
And after that we will link the previous node to the next node.

198
00:14:23,720 --> 00:14:26,750
So previous node to.

199
00:14:28,230 --> 00:14:30,570
Next and next node.

200
00:14:32,300 --> 00:14:35,660
And after that, now it's safe to remove the selected index element.

201
00:14:35,690 --> 00:14:39,200
Now we're going to go delete Node.

202
00:14:39,350 --> 00:14:40,640
And after that we.

203
00:14:41,990 --> 00:14:48,920
Need to decrement the decrement count of our list since the one element is removed here.

204
00:14:48,920 --> 00:14:56,140
So as you can see in this code, we will invoke the remove heat operation if the index is equal to zero

205
00:14:56,150 --> 00:15:01,100
and will invoke the remove tail operation here.

206
00:15:01,100 --> 00:15:02,000
Remove tail operation.

207
00:15:02,000 --> 00:15:05,180
If the index equals my count minus one.

208
00:15:05,180 --> 00:15:12,260
So it's not clear that in the best case here, which is remove heat and remove tail is invoked, the

209
00:15:12,260 --> 00:15:14,420
complexity is zero one.

210
00:15:14,420 --> 00:15:21,230
And in the worst case, when the remove tail actual remove tail is invoked, the complex is zero.

211
00:15:21,230 --> 00:15:22,160
And here.