1
00:00:00,620 --> 00:00:01,880
Hello, my name is Stephanie.

2
00:00:01,880 --> 00:00:04,830
Welcome to another lecture of our Oxford course.

3
00:00:04,850 --> 00:00:10,940
In this lecture we are cplusplus course we will insert an item in the linked list class.

4
00:00:10,940 --> 00:00:12,230
So let's get started.

5
00:00:25,790 --> 00:00:30,230
So let's move to on the insert operation for the Linkedlist class.

6
00:00:30,410 --> 00:00:37,130
So there are four cases for this operation and they are those are the first case is the new item is

7
00:00:37,130 --> 00:00:42,680
inserted at the beginning of the linked list, which is index index of sexual.

8
00:00:42,680 --> 00:00:44,180
Let's do that here.

9
00:00:44,810 --> 00:00:46,730
So which is index.

10
00:00:47,880 --> 00:00:49,020
Equals.

11
00:00:50,030 --> 00:00:56,900
Here equals zero, which index is zero so that it becomes the head here.

12
00:00:56,900 --> 00:01:01,370
So in this case, it's becomes the head.

13
00:01:04,120 --> 00:01:08,080
We also have in the at the second here.

14
00:01:08,110 --> 00:01:09,310
At the second.

15
00:01:11,290 --> 00:01:15,040
We would also have this is the second case.

16
00:01:15,250 --> 00:01:20,440
So the new item is added to an empty linked list.

17
00:01:20,560 --> 00:01:27,760
So if the linked list has only one element, so it's going to be both here in this case of empty list,

18
00:01:27,790 --> 00:01:29,890
the it's going to be hit.

19
00:01:31,680 --> 00:01:33,570
And a tale.

20
00:01:35,750 --> 00:01:38,840
Tail, which in this case it's going to be head and tail.

21
00:01:38,840 --> 00:01:41,780
And we'll point to the only element.

22
00:01:41,780 --> 00:01:48,890
So they are going to be point to the same element, Same element.

23
00:01:54,320 --> 00:01:56,480
And also let's make this like that.

24
00:01:59,420 --> 00:02:00,200
Here.

25
00:02:00,410 --> 00:02:05,150
Also, let's take this here and make it up here.

26
00:02:11,330 --> 00:02:11,900
So.

27
00:02:12,200 --> 00:02:14,240
And the third year.

28
00:02:15,420 --> 00:02:15,720
Here.

29
00:02:16,140 --> 00:02:24,900
The third case is that the new item inserted into the last of the linked list, which is is going to

30
00:02:24,900 --> 00:02:27,330
be the index.

31
00:02:28,780 --> 00:02:31,360
Index is going to be an.

32
00:02:32,910 --> 00:02:33,540
Here.

33
00:02:33,540 --> 00:02:37,050
So the it becomes the new tail here.

34
00:02:37,050 --> 00:02:40,890
So it will become the new tail.

35
00:02:42,290 --> 00:02:44,120
So new.

36
00:02:45,020 --> 00:02:45,650
Tail.

37
00:02:48,690 --> 00:02:53,310
And last here we will talk about is the fourth.

38
00:03:00,180 --> 00:03:08,520
And they also have the fourth, which is the new item is inserted in the other position of linked list

39
00:03:08,550 --> 00:03:12,240
where the index is going to be here index.

40
00:03:14,930 --> 00:03:17,480
Is going to be one.

41
00:03:18,180 --> 00:03:19,350
From one.

42
00:03:20,200 --> 00:03:24,040
To n minus one.

43
00:03:24,520 --> 00:03:33,430
So in this is going to be one to index from one to from one to n minus one.

44
00:03:33,430 --> 00:03:39,460
So let's actually hide this and let's see how to create our insertion.

45
00:03:40,850 --> 00:03:41,570
Process here.

46
00:03:41,570 --> 00:03:43,300
So now here.

47
00:03:43,310 --> 00:03:43,780
Oops.

48
00:03:47,300 --> 00:03:48,740
Let's create the implement.

49
00:03:48,890 --> 00:03:54,980
We will also create an implementation for inserting an operation for cases one and two so we can solve

50
00:03:54,980 --> 00:04:00,680
these problems by creating insert hid operation that in previous lecture we did it here, insert hit,

51
00:04:00,680 --> 00:04:03,740
insert tail and insert here just an insert.

52
00:04:03,890 --> 00:04:12,290
So the implementation of this operation here, after that, we're going to after get here, as you can

53
00:04:12,290 --> 00:04:14,210
see, we defined here get.

54
00:04:14,210 --> 00:04:18,890
And after that we're going to add the insert head here.

55
00:04:18,890 --> 00:04:21,530
So with length list.

56
00:04:21,530 --> 00:04:23,780
And we also need to add the template here.

57
00:04:23,810 --> 00:04:27,590
The template is going to be type name.

58
00:04:28,550 --> 00:04:30,560
Template typing t here.

59
00:04:30,560 --> 00:04:32,870
And after that void the Linkedlist.

60
00:04:32,870 --> 00:04:37,880
As you can see here, our insertions are our returns.

61
00:04:37,910 --> 00:04:38,480
Nothing here.

62
00:04:38,480 --> 00:04:41,140
So that's why we created a void here.

63
00:04:41,150 --> 00:04:47,360
So now it's going to be t and insert insert heat.

64
00:04:47,360 --> 00:04:52,040
So it's going to we don't need val, we don't need index if we know where we are adding.

65
00:04:52,040 --> 00:05:00,350
So in, in insert we have to, we have to here but in insert.

66
00:05:02,190 --> 00:05:02,750
Hit.

67
00:05:03,210 --> 00:05:10,710
We don't have we just have the value that we're going to insert at the head of our list.

68
00:05:10,710 --> 00:05:13,530
So let's quickly clear this and come here.

69
00:05:13,530 --> 00:05:17,810
So now we're going to add the insert hit.

70
00:05:17,820 --> 00:05:21,690
And as you can see here, we just need one as a parameter.

71
00:05:22,770 --> 00:05:24,780
So after that.

72
00:05:25,680 --> 00:05:27,000
Uh, actually here.

73
00:05:27,210 --> 00:05:34,530
So after that, we're going to inside the inserted function, we're going to create a new node.

74
00:05:34,560 --> 00:05:37,980
So node to note here.

75
00:05:37,980 --> 00:05:39,660
So the new node is going to be.

76
00:05:40,840 --> 00:05:41,890
Template.

77
00:05:42,620 --> 00:05:43,070
Not.

78
00:05:43,850 --> 00:05:50,560
It's going to be a template and value here after that.

79
00:05:50,570 --> 00:05:58,010
So the current node or the current heat will no longer become a heat.

80
00:05:58,010 --> 00:06:02,780
So the next pointer of the new node will point to the current heat here.

81
00:06:02,780 --> 00:06:09,500
So the node next is going to be point to the current heat.

82
00:06:10,190 --> 00:06:14,840
After that, let's actually create the new node to become the heat.

83
00:06:14,840 --> 00:06:18,530
So here we're going to create heat equals node.

84
00:06:19,190 --> 00:06:21,200
Sign the heat to node here.

85
00:06:21,200 --> 00:06:23,750
So let's actually create another condition here.

86
00:06:23,750 --> 00:06:25,190
So another condition.

87
00:06:25,190 --> 00:06:32,480
So if the link list is empty, the tail is also the heat as we discussed in third case here.

88
00:06:32,480 --> 00:06:40,340
So if the if the my count is equals zero, then our tail is also heat.

89
00:06:41,760 --> 00:06:46,390
And after that we will add the after outside the if.

90
00:06:46,410 --> 00:06:51,870
Here we will add one element, which is going to be a increment, the one element here.

91
00:06:51,870 --> 00:06:58,200
So we inserted heat and after insertion here, we will add one element here.

92
00:06:58,200 --> 00:07:01,740
And as you can see here, the element is going to be plus one.

93
00:07:02,580 --> 00:07:05,640
And we will add this element inside our list.

94
00:07:06,870 --> 00:07:07,650
Here.

95
00:07:09,380 --> 00:07:17,660
So as you can see here, the insert hit operation will create a new node that assigns it to a new hit.

96
00:07:17,660 --> 00:07:25,670
So if the linked list is empty before applying this operation, the new node also become the tail.

97
00:07:27,260 --> 00:07:28,880
So, um.

98
00:07:30,720 --> 00:07:31,380
For this.

99
00:07:31,410 --> 00:07:35,160
The complexity of this operation is going to be zero.

100
00:07:36,170 --> 00:07:37,130
And one.

101
00:07:38,750 --> 00:07:42,110
So regardless of the number of the for the linked list is limited.

102
00:07:42,110 --> 00:07:45,530
So it's actually not that complex here for case three.

103
00:07:45,560 --> 00:07:54,230
As I as we learned earlier of this lecture, in the inserting operation, we can implement the insert

104
00:07:54,260 --> 00:07:55,340
tail operation.

105
00:07:55,340 --> 00:07:57,290
So the operation is simple and efficient.

106
00:07:57,290 --> 00:08:02,270
So we just need to create a new node and then assign it to the new tail.

107
00:08:03,170 --> 00:08:08,180
So the next pointer to previous tail will point to the new tail here.

108
00:08:08,180 --> 00:08:11,630
So let's actually delete this and come here.

109
00:08:11,630 --> 00:08:15,380
We create our insert hit.

110
00:08:16,460 --> 00:08:19,160
Insert is developed insert tail here.

111
00:08:19,160 --> 00:08:23,960
We're going to add now and here let's go to our coding process.

112
00:08:23,960 --> 00:08:29,120
So now we're going to also create a type name after the insert head.

113
00:08:29,740 --> 00:08:34,630
So the template type name.

114
00:08:36,930 --> 00:08:43,170
Name is going to be T And after that void, the length list is going to be T here.

115
00:08:43,170 --> 00:08:45,210
Also the insert tail.

116
00:08:45,720 --> 00:08:47,730
Insert tail.

117
00:08:47,760 --> 00:08:48,150
Oops.

118
00:08:48,840 --> 00:08:51,270
Insert tail here.

119
00:08:52,260 --> 00:08:53,710
Insert tail.

120
00:08:53,730 --> 00:08:56,950
And now we will pass that value here.

121
00:08:56,970 --> 00:08:59,220
So let's create another condition here.

122
00:08:59,220 --> 00:09:02,670
So if the linked list is empty, just simply invoke the insert.

123
00:09:03,630 --> 00:09:11,310
So here we're going to make it the if my count is empty or yeah is equal to zero, then it's going to

124
00:09:11,310 --> 00:09:14,730
be insert hit and just end the function here.

125
00:09:14,730 --> 00:09:16,410
So we will return function.

126
00:09:16,410 --> 00:09:26,910
So insert hit and we will pass that value to our insert hit which this will pass to our insert hit here.

127
00:09:26,970 --> 00:09:27,930
So.

128
00:09:30,110 --> 00:09:31,520
In this case is going to give.

129
00:09:31,550 --> 00:09:33,470
It's going to be well here.

130
00:09:33,470 --> 00:09:34,940
After that, we will return.

131
00:09:36,080 --> 00:09:36,740
Return.

132
00:09:38,700 --> 00:09:41,130
So if this condition is not.

133
00:09:42,210 --> 00:09:44,990
True, then we will create a new node.

134
00:09:45,020 --> 00:09:50,150
So not here, not t, not here.

135
00:09:50,150 --> 00:09:59,600
So new node is going to be T and we will pass value here and here we will create this code and I will

136
00:09:59,600 --> 00:10:01,340
explain now here.

137
00:10:01,340 --> 00:10:03,080
So we will write this code.

138
00:10:03,080 --> 00:10:07,930
So in case of that, the current tail will no longer become a tail.

139
00:10:07,940 --> 00:10:13,190
So the next pointer of the current tail will point to the new node here.

140
00:10:13,190 --> 00:10:21,110
So and we will also then a new node B, it's going to be become the tail, so tail equals node.

141
00:10:21,110 --> 00:10:30,020
And after that we will add one element as we did in the add in the ADD heat method here.

142
00:10:30,020 --> 00:10:33,530
So we will add one element plus one here.

143
00:10:33,710 --> 00:10:35,930
So in this case it's going to be.

144
00:10:37,530 --> 00:10:40,150
My count of sexual.

145
00:10:40,150 --> 00:10:41,310
Let's delete this.

146
00:10:43,830 --> 00:10:44,460
Here.

147
00:10:44,550 --> 00:10:48,550
So the my count is going to be plus plus.

148
00:10:48,570 --> 00:10:49,320
That's it.

149
00:10:50,720 --> 00:10:56,480
Also, please keep in mind that we might run the insert tail operation.

150
00:10:56,480 --> 00:11:00,770
Insert tail operation when the linked list has no elements.

151
00:11:00,770 --> 00:11:07,520
So if this occurs, the case two as we discussed in previous lecture and in the beginning of this lecture,

152
00:11:07,550 --> 00:11:14,330
the case two will happen and we can simply invoke the insert hit method.

153
00:11:14,630 --> 00:11:19,820
So the complexity of the insert tail method is same as our insert head method.

154
00:11:19,820 --> 00:11:22,910
So in this case it's going to be zero multiply by one here.

155
00:11:23,210 --> 00:11:28,970
So regardless of the number of the linked is list elements here, so the complexity is going to be same.

156
00:11:28,970 --> 00:11:31,790
So it will even invoke the insert head operation.

157
00:11:31,790 --> 00:11:38,780
Since the insert operation complexity is also zero one here.

158
00:11:38,780 --> 00:11:45,500
So now let's actually create the case for here which we need to traverse the elements for the linked

159
00:11:45,500 --> 00:11:50,910
list to find two elements where we want to insert the new element between them.

160
00:11:50,910 --> 00:11:53,640
So we will call them previous node and next node.

161
00:11:53,640 --> 00:12:00,720
So after we find them, we then create a new node point to the next pointer of previous node, so to

162
00:12:00,720 --> 00:12:05,490
new node and then point to the next pointer of the new node to the next node.

163
00:12:05,520 --> 00:12:07,560
So the implementation of the insert operation.

164
00:12:07,560 --> 00:12:12,840
So it might be complex here, but after we writing our code you will understand all of this.

165
00:12:12,840 --> 00:12:14,640
So after our.

166
00:12:15,450 --> 00:12:19,410
Insert tail method, we will create the again, the template here.

167
00:12:20,040 --> 00:12:21,870
So template.

168
00:12:22,170 --> 00:12:25,950
Template is going to be type name T.

169
00:12:28,300 --> 00:12:31,120
Here and we will create an insert method.

170
00:12:31,120 --> 00:12:34,120
So in this insert method here, we will add.

171
00:12:34,920 --> 00:12:36,810
The index and value.

172
00:12:37,530 --> 00:12:41,640
Except as you can see, we just had the value here because we are inserting.

173
00:12:41,640 --> 00:12:43,360
We know where we inserting, right.

174
00:12:43,380 --> 00:12:45,200
In this case, we're going to insert the heat.

175
00:12:45,210 --> 00:12:46,710
In this case, we're going to insert a tail.

176
00:12:46,740 --> 00:12:49,470
But in this case, we're going to need the index here.

177
00:12:49,470 --> 00:12:52,980
So that's why we're going to create two parameters.

178
00:12:53,340 --> 00:13:00,930
And here it's going to be void length list T here insert.

179
00:13:01,960 --> 00:13:04,180
Insert just an insert here.

180
00:13:04,180 --> 00:13:06,460
So first we have index and Val.

181
00:13:06,490 --> 00:13:09,900
And first we need to check if the index is out of bounds.

182
00:13:09,910 --> 00:13:23,770
So if our if our index is less than zero or our index is greater than my count, then just return here.

183
00:13:23,980 --> 00:13:28,090
If this not happen, let's run our function here.

184
00:13:28,090 --> 00:13:28,920
So if the.

185
00:13:30,170 --> 00:13:33,780
Let's actually insert a new hit.

186
00:13:33,800 --> 00:13:40,820
So if index is equal to zero, then insert hit.

187
00:13:41,360 --> 00:13:43,160
And we will pass our value.

188
00:13:43,160 --> 00:13:48,590
And as you can see, we are again using the insert hit because if our index is zero, then we can also

189
00:13:48,590 --> 00:13:49,720
insert hit here.

190
00:13:49,730 --> 00:13:52,880
So that's why we executed this, created this.

191
00:13:52,910 --> 00:13:58,580
If and after that then we didn't miss the our insert is completed and just return here.

192
00:13:59,360 --> 00:14:04,070
After that, uh, if if we are inserting a new tail.

193
00:14:04,070 --> 00:14:04,670
So.

194
00:14:06,190 --> 00:14:07,570
Else if.

195
00:14:07,660 --> 00:14:16,930
If our else if in our index is my count equals to my count, then we will insert a new tail.

196
00:14:17,980 --> 00:14:21,760
So in this case, I will explain all of things now.

197
00:14:21,910 --> 00:14:29,380
Insert insert tail is going to be val and return.

198
00:14:29,380 --> 00:14:30,700
So in this case.

199
00:14:31,700 --> 00:14:39,530
Uh, it will run if our node has zero elements.

200
00:14:39,530 --> 00:14:48,830
But if here, if, for example, if our in this case we have five elements and we we want to add in

201
00:14:48,830 --> 00:14:54,170
the fifth index, then we can also use the insert method for this.

202
00:14:54,170 --> 00:14:56,420
So we don't need to write separate method for this.

203
00:14:56,420 --> 00:15:03,830
So that's why we created this conditions for more efficient programming here.

204
00:15:04,130 --> 00:15:05,480
So now.

205
00:15:08,270 --> 00:15:10,580
We will start to find previous note from the Heat.

206
00:15:10,610 --> 00:15:12,170
In order to do that, we will create.

207
00:15:12,200 --> 00:15:12,890
Note here.

208
00:15:12,890 --> 00:15:14,120
Previous note here.

209
00:15:17,310 --> 00:15:22,680
Note it's going to be previous, not pre note here.

210
00:15:22,680 --> 00:15:24,700
It's going to be hit here.

211
00:15:24,720 --> 00:15:31,110
Hit And after that we'll need to traverse the elements until the selected item is found.

212
00:15:31,110 --> 00:15:33,690
So we will add four here.

213
00:15:33,690 --> 00:15:43,620
Integer is zero and while our e is less than index, then our index minus one then plus plus E here.

214
00:15:44,790 --> 00:15:45,540
And we will.

215
00:15:46,630 --> 00:15:47,650
Some previous node.

216
00:15:48,130 --> 00:15:51,640
Previous node equal Previous node.

217
00:15:52,450 --> 00:15:54,220
And next.

218
00:15:56,720 --> 00:16:04,070
Okay, So after that, we need to create the next node, which is the element after the previous node

219
00:16:04,100 --> 00:16:04,810
here.

220
00:16:04,820 --> 00:16:18,470
So note here the next node and assign it to previous node previous node and we will make it next here.

221
00:16:19,100 --> 00:16:19,460
Oops.

222
00:16:19,910 --> 00:16:20,870
Next.

223
00:16:21,080 --> 00:16:22,040
And also delete.

224
00:16:22,840 --> 00:16:23,090
Because.

225
00:16:24,970 --> 00:16:25,360
Here.

226
00:16:25,780 --> 00:16:28,600
So we will also make.

227
00:16:31,330 --> 00:16:32,530
Uh, also create a new node.

228
00:16:32,560 --> 00:16:33,520
Firstly here.

229
00:16:34,090 --> 00:16:41,200
So note here the oops node to node.

230
00:16:41,230 --> 00:16:51,780
The new node is going to be T, which is we will pass value here and after that we will insert, insert

231
00:16:51,910 --> 00:16:53,950
this, insert this new node here.

232
00:16:53,950 --> 00:16:59,170
So we will insert this new node between the previous node and the next node.

233
00:16:59,200 --> 00:17:00,130
So.

234
00:17:02,160 --> 00:17:04,230
Not here.

235
00:17:04,260 --> 00:17:05,280
Next.

236
00:17:07,450 --> 00:17:08,650
And next not.

237
00:17:11,600 --> 00:17:17,660
And previous note we will insert previous node to our next and it's going to be node here.

238
00:17:18,680 --> 00:17:23,930
And we ask after that signs we are executing the insert after insert operation.

239
00:17:23,930 --> 00:17:31,190
We're going to add one element as we did in the insert tail and insert heat method.

240
00:17:32,940 --> 00:17:34,230
So my count.

241
00:17:34,260 --> 00:17:35,030
Plus, plus.

242
00:17:35,190 --> 00:17:43,350
So since we need to traverse the list element, the complexity of this insert operation is n here.

243
00:17:45,360 --> 00:17:52,980
So, however, in the best case, the complexity is going to be here less best case, the complexity

244
00:17:52,980 --> 00:17:59,970
is going to be zero one, as in insert it and insert tile.

245
00:17:59,970 --> 00:18:06,960
So that's because since we might insert a hit, so here our tail or after the operation.

246
00:18:06,960 --> 00:18:09,780
So complexity of this code here.

247
00:18:10,690 --> 00:18:17,790
Complexity of this code is actually let me write this and make it right here.

248
00:18:17,800 --> 00:18:18,700
So.

249
00:18:21,390 --> 00:18:26,930
The complexity of this code is zero one.

250
00:18:26,940 --> 00:18:29,120
Signs are inserted.

251
00:18:29,130 --> 00:18:31,530
Complexity is zero one.

252
00:18:31,530 --> 00:18:37,650
That's because we know where we're inserting our value and insert is the same like the insert here.

253
00:18:37,650 --> 00:18:40,920
We know where we ending our.

254
00:18:42,070 --> 00:18:42,670
A value.

255
00:18:42,670 --> 00:18:48,250
But in this case, we don't know where our index is or where our values.

256
00:18:48,250 --> 00:18:52,120
That's why we have the o n here.

257
00:18:52,510 --> 00:18:55,540
So n is the index here.

258
00:18:55,540 --> 00:18:56,320
So.

259
00:18:57,130 --> 00:18:59,830
If that's why we added this here.

260
00:18:59,830 --> 00:19:07,270
So to reduce the complexity and a bit more code efficiency for our C plus plus.