1
00:00:01,020 --> 00:00:01,500
OK.

2
00:00:01,530 --> 00:00:03,990
Welcome to another video lecture.

3
00:00:04,500 --> 00:00:12,750
Today's lecture is going to be primarily about adding an insert function to our list, but we will talk

4
00:00:12,750 --> 00:00:14,640
about some other things first.

5
00:00:15,390 --> 00:00:26,820
And one of those things lies in our list as BP file and is our append function specifically that this

6
00:00:26,940 --> 00:00:28,680
right here in the list.

7
00:00:29,790 --> 00:00:37,670
So we have been doing it in a sequential manner and for a reason.

8
00:00:38,220 --> 00:00:44,340
We it was important for us to go over how to traverse the link list using that current pointer.

9
00:00:44,340 --> 00:00:45,670
And we do it here.

10
00:00:45,690 --> 00:00:48,960
We already did it here and we do it in our print function as well.

11
00:00:50,520 --> 00:00:59,160
But if you recall during the theoretical slideshow, part, one of the main things that we talked about

12
00:00:59,430 --> 00:01:06,240
was the fact that inserting something into a linked list, which is kind of amusing in that is an ambiguous

13
00:01:06,570 --> 00:01:07,200
term.

14
00:01:07,440 --> 00:01:13,710
The fact that we add something into our linked list when it is an unordered linked list.

15
00:01:15,150 --> 00:01:22,620
That the reason the link list does well with that is because that can be considered a constant time

16
00:01:22,620 --> 00:01:27,420
operation, you might remember me mentioning that in that slideshow.

17
00:01:28,170 --> 00:01:32,730
And you might have caught on to this already and been like, Well, OK, well, why are we doing it

18
00:01:32,730 --> 00:01:34,320
like this, in our opinion function?

19
00:01:34,350 --> 00:01:39,360
This is clearly sequential time complexity.

20
00:01:39,690 --> 00:01:47,550
And you would be 100 percent correct if that is what you were thinking because we are in fact looping

21
00:01:47,550 --> 00:01:51,720
through in items in the list if we chose our basic operation here.

22
00:01:52,200 --> 00:01:56,790
It would be a big go of in time complexity.

23
00:01:57,450 --> 00:02:03,440
And that is not good because if we have an unaudited link list, it doesn't matter where we put it.

24
00:02:03,450 --> 00:02:08,040
We can just put it at the front or the back, the head or the tail.

25
00:02:08,850 --> 00:02:13,530
And there's no need for us to really maintain an order if it's on order.

26
00:02:13,550 --> 00:02:20,250
And that should be a simple Constantinou operation, and that is something that put a list above a vector

27
00:02:20,250 --> 00:02:21,960
for that specific operation.

28
00:02:24,660 --> 00:02:30,000
And like, you know, having to shift everything back, that's what we were talking about in that slide

29
00:02:30,000 --> 00:02:30,390
show.

30
00:02:31,310 --> 00:02:36,860
And so that is something that we need to change now, since we are going to make our insert function

31
00:02:36,860 --> 00:02:43,730
today, the reason that we would even make an insert function, in fact, is when we want our linguists

32
00:02:43,730 --> 00:02:53,870
to be ordered and we will see that we will in fact have to move sequentially through our linked list

33
00:02:53,870 --> 00:02:59,540
because we need to go to a specific position, the link list during insertion to put our new node in

34
00:02:59,540 --> 00:03:04,700
the right spot as as far as its data relates to the other nodes data around it.

35
00:03:05,600 --> 00:03:14,240
So something to take away if you take away one thing from this video lecture, it is to realize that

36
00:03:14,480 --> 00:03:20,780
the insertion operation into an unordered link list is going to be a cost and time operation.

37
00:03:20,780 --> 00:03:21,830
So a live one.

38
00:03:22,670 --> 00:03:27,590
But if we have a ordered link list and we need to insert.

39
00:03:28,830 --> 00:03:33,120
Then that becomes a sequential operation, which is big of in.

40
00:03:34,200 --> 00:03:42,060
So let's go ahead and in fact make our append function something that is a cost and time operation.

41
00:03:42,060 --> 00:03:43,800
We don't need this whole while loop here.

42
00:03:43,810 --> 00:03:48,600
So I'm going to go ahead and take this, delete it or go in here.

43
00:03:48,840 --> 00:03:55,290
All we really need to do since it's unordered is just put it right on the end, and we don't need to

44
00:03:55,290 --> 00:04:00,840
move over everything to get to the end because we're already keeping track of the end and that is with

45
00:04:00,840 --> 00:04:02,400
our tail number right here.

46
00:04:02,940 --> 00:04:05,460
So all I have to do is tail.

47
00:04:06,060 --> 00:04:16,630
Next is going to be new node and then I can say new nodes preve is actually going to be tail.

48
00:04:17,310 --> 00:04:22,560
And now I can update tail Munich because it's the new last thing in the list.

49
00:04:23,280 --> 00:04:29,730
Of course, I also want to put my size plus equals one here, but that is all we really need to do here

50
00:04:30,720 --> 00:04:34,530
through our list, so we don't need to move through it and add the new node to the end.

51
00:04:34,530 --> 00:04:38,910
We are just actually adding new node to the end.

52
00:04:40,470 --> 00:04:44,880
So if you already noticed that and you're kind of like, what the heck?

53
00:04:45,210 --> 00:04:47,760
There's these videos lectures going on?

54
00:04:47,760 --> 00:04:51,900
And he said that this is Constantine and we're not doing it in Constantine.

55
00:04:52,770 --> 00:04:53,640
What's with this?

56
00:04:54,750 --> 00:04:55,660
Apologies for that.

57
00:04:55,660 --> 00:04:56,610
If it's frustrating.

58
00:04:56,610 --> 00:05:04,890
But there I did want to show you how to move through the linked list and kind of ease people into it

59
00:05:04,890 --> 00:05:09,900
if it wasn't so obvious immediately, how to do that.

60
00:05:10,290 --> 00:05:12,420
So even though we did have our print function here.

61
00:05:13,290 --> 00:05:19,830
But now we are changing it, and I feel like it should show you the difference between moving sequentially

62
00:05:19,830 --> 00:05:24,270
and when you need to do that and when you do not need to do that.

63
00:05:24,780 --> 00:05:29,820
So you are trying to keep any specific order to things and certain things in order that is going to

64
00:05:29,820 --> 00:05:30,450
be linear.

65
00:05:30,630 --> 00:05:35,220
If not, if it's on order and you don't care, you can just add it to the end like this.

66
00:05:36,310 --> 00:05:39,760
OK, so let's move on to the actual insert function.

67
00:05:39,780 --> 00:05:47,220
I'm going to go to my header file here and I say, avoid, insert, and I'm going to put this to data

68
00:05:47,220 --> 00:05:48,540
valid just like Append.

69
00:05:49,320 --> 00:05:51,210
Go back to a CBP file.

70
00:05:51,220 --> 00:05:57,030
I'm going to copy this and I'm going to paste that here.

71
00:05:57,810 --> 00:06:14,370
And I'm going to say void list key in search, and I'm going to actually copy all of this up here because

72
00:06:14,940 --> 00:06:20,040
if we have nothing in the list, insert and append aren't really different.

73
00:06:20,040 --> 00:06:21,900
We're just putting one item in there.

74
00:06:21,900 --> 00:06:26,970
We have nothing and it's just going to be have equals tail equals Nenad because there's nothing to really

75
00:06:26,970 --> 00:06:31,530
compare it to, to put it in the right spot at the right size, just to insert it and set everything.

76
00:06:32,580 --> 00:06:40,680
This, though, if we have one item in this, yeah, if this size is equal to one, we're going to have

77
00:06:40,680 --> 00:06:42,270
to change this one a little bit.

78
00:06:42,270 --> 00:06:44,130
I will be copy paste in this code.

79
00:06:44,460 --> 00:06:50,880
But first, we're going to have to compare with what's in there, and I'm going to use the head instead

80
00:06:50,880 --> 00:06:53,340
of the tail to look at its data.

81
00:06:53,340 --> 00:07:04,950
So I'm going to say if heads data is greater than or equal to new nodes data, then what I'm going to

82
00:07:04,950 --> 00:07:06,540
do is say heads.

83
00:07:06,840 --> 00:07:14,430
Previous is new node and then I'm going to say new nodes.

84
00:07:15,630 --> 00:07:18,300
Next is going to be head.

85
00:07:19,320 --> 00:07:28,170
And then I'll update the head to new node because we just inserted it in front and I will, of course,

86
00:07:28,170 --> 00:07:29,490
update my size.

87
00:07:32,880 --> 00:07:40,080
So I'm going to go along with a little visual drawing here to just make things a little more clear,

88
00:07:40,080 --> 00:07:45,450
hopefully instead of just smashing code and hoping that you get it from this text right here.

89
00:07:45,630 --> 00:07:49,770
So this operation is going to look like this drawing right here.

90
00:07:50,040 --> 00:07:55,890
I have admitted the previous pointer and next pointer here, the pretty pointer for new note and had

91
00:07:55,900 --> 00:07:59,640
pointers next just because we're not changing those pointers.

92
00:07:59,940 --> 00:08:04,620
But you should, you know, if you don't like that, then just envision them right here because there

93
00:08:04,620 --> 00:08:06,090
would this one be pointing to null?

94
00:08:06,090 --> 00:08:10,980
And this next pointing would be pointing all over here in the case that we're looking at right now,

95
00:08:11,010 --> 00:08:12,060
there's just one item.

96
00:08:12,960 --> 00:08:20,190
So we're inserting in front of head because in fact, the case that we were looking at was the case

97
00:08:20,190 --> 00:08:24,130
in which head actually had a greater data value than new node.

98
00:08:24,900 --> 00:08:31,110
And so we're just setting has previous to new node and Nuno's next to head, just like you noticed here,

99
00:08:31,230 --> 00:08:33,750
has previous new node units next to head.

100
00:08:35,130 --> 00:08:35,640
OK.

101
00:08:35,760 --> 00:08:44,340
So, otherwise, if that's not the case and it is heads data is not greater than or equal to Nuno's

102
00:08:44,340 --> 00:08:48,810
data, then we're just going to copy this logic here because we're going to add it on the other side.

103
00:08:50,340 --> 00:08:56,610
So I'm going to copy and paste this right here, and I don't really need to put this new here somewhere

104
00:08:56,610 --> 00:08:57,780
in a race that.

105
00:08:59,020 --> 00:09:04,210
OK, so hopefully that makes sense in that case, we would just be adding this new node over here on

106
00:09:04,210 --> 00:09:04,780
this side.

107
00:09:06,710 --> 00:09:09,320
OK, so.

108
00:09:12,410 --> 00:09:15,890
The Else. case is going to be a little bit more complicated.

109
00:09:19,210 --> 00:09:23,500
And so what I'm going to need to do for that.

110
00:09:24,210 --> 00:09:26,740
Yeah, I will kind of want to copy paste, but I.

111
00:09:28,200 --> 00:09:43,110
Got rid of some of my stuff right there, but I can just do this in New L.A. corner, okay, it's A.

112
00:09:44,610 --> 00:09:49,650
T. Pointer or eagles head.

113
00:09:51,120 --> 00:09:53,130
So I'll put that there.

114
00:09:53,130 --> 00:10:00,180
So we have a curve pointer and then I am going to put the same wildly here.

115
00:10:02,250 --> 00:10:11,010
So there is not equal to null pointer, but we're going to have to look at a few different things here.

116
00:10:11,010 --> 00:10:16,320
If we want to insert it somewhere in this one, which I'm calling like the middle, you know, the middle

117
00:10:16,320 --> 00:10:21,570
or the end, in fact, is going to be the same since our strategy is going to be similar to what we

118
00:10:21,570 --> 00:10:28,770
did right here, where I am inserting it before the node that we're looking at.

119
00:10:29,190 --> 00:10:31,670
So I would be inserting it before occur.

120
00:10:31,680 --> 00:10:38,640
I'm kind of looking to see whether, you know, let's keep moving until we find something that is greater

121
00:10:38,640 --> 00:10:39,450
than or equal to.

122
00:10:39,450 --> 00:10:41,460
And then I'm going to insert the new node before that.

123
00:10:42,270 --> 00:10:44,070
So encourages greater than or equal to.

124
00:10:44,070 --> 00:10:45,750
I will insert the new node before that.

125
00:10:46,620 --> 00:10:50,340
And I have another visualization here that can make this a little bit easier.

126
00:10:52,560 --> 00:10:57,060
So this is one where you insert insert new node in between to other nodes.

127
00:10:57,690 --> 00:11:03,750
So if you don't, if you imagine this not existing here Courier's previous, it would be pointing to

128
00:11:03,750 --> 00:11:05,380
here and this node.

129
00:11:05,400 --> 00:11:10,770
That's why I have named this node cur preve because we are actually going to be using something like

130
00:11:10,770 --> 00:11:11,850
this in our code.

131
00:11:12,360 --> 00:11:14,520
So if that's a little confusing, you don't like that.

132
00:11:14,530 --> 00:11:15,120
Apologies.

133
00:11:15,120 --> 00:11:18,590
I just put it there because it's it's what we're going to use in the code.

134
00:11:18,600 --> 00:11:20,940
So I was thinking it might be a good thing to name this.

135
00:11:21,960 --> 00:11:29,010
And also, another really important thing is more so to explain why there is needs to be a specific

136
00:11:29,010 --> 00:11:31,020
order in which we change these pointers.

137
00:11:31,530 --> 00:11:38,010
That's why this is also useful in that situation if I can come up with an example here.

138
00:11:39,450 --> 00:11:41,100
Is basically.

139
00:11:42,040 --> 00:11:45,340
If you were to set, let's see.

140
00:11:46,440 --> 00:11:55,770
If you were to say curse, if Kirk Preve is a new node, if you did that first.

141
00:11:56,910 --> 00:12:02,010
And then afterwards, you did new nodes preve.

142
00:12:02,960 --> 00:12:04,940
Is cur preve.

143
00:12:06,270 --> 00:12:11,760
If you think about that, you just set her approved to new node, so essentially you're just saying

144
00:12:11,760 --> 00:12:14,820
new nodes, PREVE is a new node.

145
00:12:15,900 --> 00:12:22,320
So that's pretty much the only example I can think of right now, and I'm not sure that's the only example,

146
00:12:22,320 --> 00:12:27,510
but that is why we need to do things in the right order, and you'll see that we will be doing these

147
00:12:27,510 --> 00:12:30,000
in a specific order that avoids that issue.

148
00:12:32,020 --> 00:12:36,880
But then besides it, besides that, this picture just kind of helps you get the gist of what we're

149
00:12:36,880 --> 00:12:38,440
going to be doing is pretty simple.

150
00:12:38,650 --> 00:12:40,000
We want to insert it here.

151
00:12:40,330 --> 00:12:41,830
We need to make this thing.

152
00:12:42,280 --> 00:12:45,340
You know, if it's going to move here, this thing needs to point to that.

153
00:12:46,270 --> 00:12:48,400
Nuno's next need is the point here.

154
00:12:49,000 --> 00:12:51,820
It's previous news to point here and this thing, this point here.

155
00:12:52,270 --> 00:12:59,830
And so it's just avoiding that like strange like updated this to new node when this is the thing that

156
00:12:59,830 --> 00:13:05,830
I need to reference and I'm just pointing a new node to itself now, somehow that's not what we want

157
00:13:05,830 --> 00:13:06,080
to do.

158
00:13:06,100 --> 00:13:11,440
We don't want this pointer to actually be like following this arrow and coming back of this arrow to

159
00:13:11,440 --> 00:13:11,890
itself.

160
00:13:12,970 --> 00:13:20,860
So we're going to avoid that, and we'll jump back to this drawing, too to confirm what we are actually

161
00:13:20,860 --> 00:13:21,670
doing in our code.

162
00:13:22,960 --> 00:13:33,070
So what I'm going to do is I'm going to start out by saying if parents data is greater than or equal

163
00:13:33,070 --> 00:13:37,450
to new nodes data.

164
00:13:38,170 --> 00:13:43,630
So we're just checking to see if that is the fact that this is in fact the case.

165
00:13:43,630 --> 00:13:48,580
We have arrived somewhere where current data is greater than or equal to our new nodes data.

166
00:13:49,930 --> 00:13:55,780
And then I'm going to look at this case where I'm going to check if we are at the head.

167
00:13:57,430 --> 00:14:01,750
So I'm going to say if parents.

168
00:14:03,160 --> 00:14:04,120
Previous.

169
00:14:06,810 --> 00:14:09,600
Is equal to null pointer.

170
00:14:09,900 --> 00:14:15,330
So that is the case in which current is just at the head and we haven't moved at all.

171
00:14:15,990 --> 00:14:20,850
And this is fully possible, you know, we could have a links, links list of links, whatever you know

172
00:14:20,850 --> 00:14:26,190
in and we are at the head and suddenly we realize that our new item is actually smaller than everything

173
00:14:26,190 --> 00:14:29,510
else in the linked list, so or equal to.

174
00:14:29,520 --> 00:14:31,890
So we need to deal with that.

175
00:14:34,530 --> 00:14:43,230
And so we are going to be doing something that is very similar to what we just did up here, so I'm

176
00:14:43,230 --> 00:14:44,670
going to copy this, actually.

177
00:14:47,490 --> 00:14:55,180
Because it's the same type of pointer changing we're doing here, except this is going to be her.

178
00:14:55,860 --> 00:14:56,790
So we'll say.

179
00:14:57,750 --> 00:14:59,280
Cur preve.

180
00:15:00,600 --> 00:15:08,010
Chris Preve is New A. And we are going to put colonel, it's going to put that just because we put her

181
00:15:08,010 --> 00:15:12,390
here and we're updating the head to new node changing the size.

182
00:15:12,390 --> 00:15:18,330
And once we did this, we can just return because we've already added our nodes so we can break out.

183
00:15:19,260 --> 00:15:23,490
And you'll see that this kind of affects the way we write the code in a bit as well, the fact that

184
00:15:23,490 --> 00:15:24,810
we have the returns in here.

185
00:15:26,100 --> 00:15:38,430
So otherwise, if we are not really otherwise, but it's a else, if I'm going to say if we are in between

186
00:15:39,990 --> 00:15:41,550
for the end.

187
00:15:42,390 --> 00:15:44,100
And so I'm going to say.

188
00:15:47,510 --> 00:15:50,750
Actually, yeah, this will be an Alice.

189
00:15:50,900 --> 00:15:56,330
This will be an Alice, my apologies, because it's basically those are all the cases we're either in

190
00:15:56,330 --> 00:16:01,610
between anything and so I'm going to have an else there and I must say new nodes.

191
00:16:02,360 --> 00:16:08,090
Previous is now going to be curved for you.

192
00:16:09,680 --> 00:16:10,940
And so let's take a look here.

193
00:16:11,990 --> 00:16:14,060
We're saying new nodes.

194
00:16:14,360 --> 00:16:16,590
Previous is her previous.

195
00:16:16,620 --> 00:16:23,510
I'm doing that before this right here because if I said KERS, previous new node and then I said Nuno's

196
00:16:23,510 --> 00:16:24,960
preve is reprieve.

197
00:16:25,520 --> 00:16:27,050
Well, that's new node.

198
00:16:27,050 --> 00:16:27,920
Previous new node.

199
00:16:27,920 --> 00:16:29,250
So that's what we're voting right here.

200
00:16:29,250 --> 00:16:31,640
I'm given that out of the way, right off the bat.

201
00:16:33,740 --> 00:16:37,510
So then next we will do cur preve.

202
00:16:37,520 --> 00:16:41,330
So this is just that next thing that I was talking about her.

203
00:16:41,450 --> 00:16:43,310
Previous Next.

204
00:16:43,760 --> 00:16:46,250
Which is actually going to be on this same node here.

205
00:16:46,250 --> 00:16:48,260
So Curves previewed her.

206
00:16:48,260 --> 00:16:49,480
Previous Next.

207
00:16:49,490 --> 00:16:50,630
It's going to be new node.

208
00:16:53,030 --> 00:16:59,780
So hopefully, the drawings can help you as well when you're doing this, it's kind of nice to just

209
00:16:59,780 --> 00:17:05,120
draw it out on paper to make sure that you can understand what's going on before you just start coding.

210
00:17:06,590 --> 00:17:09,280
So we're setting curves to be of next Noonan.

211
00:17:10,580 --> 00:17:14,290
Next, I'm going to say curves for you.

212
00:17:14,790 --> 00:17:15,080
Nope.

213
00:17:15,320 --> 00:17:18,380
I'm going to say new nodes next.

214
00:17:18,380 --> 00:17:25,280
Actually, in our time today, Nuno's next is going to be.

215
00:17:26,830 --> 00:17:27,430
Kerr.

216
00:17:27,580 --> 00:17:31,180
So we have new notes next, now going to Kerr.

217
00:17:31,630 --> 00:17:34,040
We did this one and we did this one.

218
00:17:34,480 --> 00:17:37,450
And now we're going to do this one and then this one.

219
00:17:38,570 --> 00:17:39,440
So that's the order.

220
00:17:40,820 --> 00:17:44,690
So Nuno's next is her.

221
00:17:46,550 --> 00:17:51,680
Actually, I was doing her, I'm doing her pretty full after this.

222
00:17:52,190 --> 00:17:56,450
We could do this either way, I believe, but I'm just going to say her reprieve this new node here.

223
00:17:57,440 --> 00:18:00,260
So I'm sorry, I'm actually going to do that the different way, a different way.

224
00:18:00,980 --> 00:18:03,320
I'm doing her reprieve and then new nodes next.

225
00:18:05,730 --> 00:18:06,400
I like that.

226
00:18:07,210 --> 00:18:12,730
And then I don't want to forget to do my size, so I'm going to do that, so I suppose one.

227
00:18:14,800 --> 00:18:18,460
And of course, we can just return right away after that.

228
00:18:22,190 --> 00:18:24,140
OK, so.

229
00:18:27,520 --> 00:18:40,120
Now what we need to do is put and if actually so I'm going to come down here, so this is.

230
00:18:41,280 --> 00:18:43,770
We have an F and an A+ right here.

231
00:18:47,970 --> 00:18:51,000
But then what I'm going to do is I'm going to put.

232
00:18:52,820 --> 00:19:01,940
And if after this is well and we are going to check again, if Current's next is no pointer for the

233
00:19:01,940 --> 00:19:02,330
end.

234
00:19:04,040 --> 00:19:07,790
And I'll explain why we're doing that in just one moment.

235
00:19:09,040 --> 00:19:12,730
So I want to make sure that these are lining up here.

236
00:19:14,250 --> 00:19:15,660
I have that.

237
00:19:19,590 --> 00:19:21,300
OK, so.

238
00:19:23,230 --> 00:19:33,760
I'm actually putting it outside of here, and I'm saying if parents next go to no point here, so that

239
00:19:33,760 --> 00:19:41,350
means we're at the end of the list, I'm going to say parents next year, you know?

240
00:19:44,360 --> 00:19:47,720
And new nodes for you.

241
00:19:49,550 --> 00:19:51,620
I'm putting this extra thing at the end.

242
00:19:54,440 --> 00:19:59,960
So we avoid the case, so basically this was all wrapped in an effort that said, if current data is

243
00:19:59,960 --> 00:20:05,390
greater than or equal to Nuno's data and then we have this down here, we're adding stuff either in

244
00:20:05,390 --> 00:20:13,340
between or at the end, but we don't want to only just add that when it is greater than or equal to,

245
00:20:13,340 --> 00:20:22,340
because if we did get to the end node and the case is that our current data is actually not greater

246
00:20:22,340 --> 00:20:30,410
than or equal to Nuno's data, then that means we actually need to add it on the very end and make it

247
00:20:30,410 --> 00:20:32,140
be the tail.

248
00:20:32,750 --> 00:20:36,680
So I add and accommodated for that case quite yet.

249
00:20:37,310 --> 00:20:45,710
So that's why it's going to be outside of these brackets because it is not going to be within this if

250
00:20:45,710 --> 00:20:47,570
where it's greater than it's the other case.

251
00:20:47,990 --> 00:20:55,280
So I'm actually going to just add that death right here and we can just make it an if since we are returning

252
00:20:56,480 --> 00:20:57,890
and all these cases anyway.

253
00:20:57,910 --> 00:21:08,900
So I'm going to say now tail equals new node because all we had to do before adding it out there is

254
00:21:08,900 --> 00:21:09,320
change.

255
00:21:09,320 --> 00:21:15,980
These currents next is going to be new node because this is basically the tail that we're on right now.

256
00:21:15,980 --> 00:21:24,920
And then we just point back from new node to occur in our new nodes.

257
00:21:24,920 --> 00:21:26,440
Next is null as well.

258
00:21:26,450 --> 00:21:31,280
So that's why we only have to change these two pointers and update the tail and update the size.

259
00:21:31,280 --> 00:21:32,300
And we are good to go.

260
00:21:34,720 --> 00:21:38,470
I'm also going to just return as well.

261
00:21:40,670 --> 00:21:51,110
So the only thing we really need to add now is the cur equals cur arrow next because we need to move

262
00:21:51,110 --> 00:21:51,680
along.

263
00:21:52,040 --> 00:21:54,410
And this is what drives it, as we talked about before.

264
00:21:56,580 --> 00:22:01,800
OK, so hopefully everything is right, if not, I will be encountering some errors that we get to debug.

265
00:22:05,070 --> 00:22:06,190
But this should be good.

266
00:22:06,210 --> 00:22:10,620
We have accommodated for pretty much all the cases that we need to think about.

267
00:22:10,860 --> 00:22:21,300
So we insert in the beginning if it's necessary, if some, if this was the case, that there was more

268
00:22:21,300 --> 00:22:22,650
stuff over here.

269
00:22:23,760 --> 00:22:26,250
So heads next pointed to something.

270
00:22:26,250 --> 00:22:30,930
And then maybe we have X amount of items after that, an amount of items, I should say.

271
00:22:31,650 --> 00:22:33,990
But the new node was less than everything in our list.

272
00:22:33,990 --> 00:22:36,510
We would do this and add it in the front.

273
00:22:36,540 --> 00:22:39,870
So this would be the operation that we would do.

274
00:22:39,930 --> 00:22:43,260
We would do otherwise.

275
00:22:43,680 --> 00:22:47,520
If it is greater than CUR.

276
00:22:48,090 --> 00:22:48,630
I'm sorry.

277
00:22:48,630 --> 00:22:58,440
If CUR is greater than or equal to new node, then we would just be doing this and adding it before

278
00:22:59,010 --> 00:22:59,910
and then the last.

279
00:22:59,910 --> 00:23:05,370
If that we did is not represented here, but what we would be doing is taking this and adding it over

280
00:23:05,370 --> 00:23:05,760
here.

281
00:23:05,890 --> 00:23:07,440
So less pointer changing.

282
00:23:10,270 --> 00:23:10,990
OK, cool.

283
00:23:11,380 --> 00:23:14,170
So hopefully that worked out, OK.

284
00:23:14,950 --> 00:23:22,840
Let's go ahead and update our main because we are now using Append.

285
00:23:23,800 --> 00:23:26,170
I'm going to change this to insert.

286
00:23:29,120 --> 00:23:34,340
And I've already commented this out, so I'm just going to be printing the integers.

287
00:23:34,580 --> 00:23:43,420
I went ahead before the video was being recorded and changed my input to just have an out and out of

288
00:23:43,490 --> 00:23:49,970
order, a sequence of single numbers here, single digits.

289
00:23:50,300 --> 00:23:57,020
So if you going to go ahead and put anything in whatever order, but I'm just adding single digits here

290
00:23:57,020 --> 00:24:01,280
since we are reading things and as chars.

291
00:24:02,000 --> 00:24:07,560
So let's go ahead and run this and cross our fingers and hope everything works OK?

292
00:24:11,920 --> 00:24:13,690
OK, so we have.

293
00:24:15,110 --> 00:24:16,910
At issue.

294
00:24:18,340 --> 00:24:19,150
We're.

295
00:24:22,970 --> 00:24:23,140
And.

296
00:24:26,830 --> 00:24:29,770
Okay, next.

297
00:24:32,470 --> 00:24:35,350
OK, so I did not add parentheses here.

298
00:24:35,470 --> 00:24:38,230
It looks like let's go ahead and run that again.

299
00:24:41,650 --> 00:24:43,720
OK, so.

300
00:24:45,330 --> 00:24:46,290
Looking pretty good.

301
00:24:46,500 --> 00:24:51,030
One, two, three four, five, six, seven, eight, and I put all those values one three eight in

302
00:24:51,030 --> 00:24:58,860
this input file here out of order, so it read them in and printed them out in order.

303
00:24:58,860 --> 00:25:02,940
So that means that our insert function is working correctly.

304
00:25:05,490 --> 00:25:11,670
OK, so hopefully you have enjoyed this video and it made sense to you.

305
00:25:13,950 --> 00:25:16,890
You can definitely refer back to these drawings.

306
00:25:16,920 --> 00:25:24,000
I will try to include them in the course content so you can refer back to them.

307
00:25:24,810 --> 00:25:33,810
And it is a little confusing the changing of the pointers, but practice makes perfect and a good exercise.

308
00:25:34,440 --> 00:25:40,800
I will not be having this as a coding exercise, but a good exercise for yourself is to try and insert

309
00:25:40,800 --> 00:25:42,420
based on some different.

310
00:25:43,930 --> 00:25:45,430
Some different ordering.

311
00:25:46,360 --> 00:25:54,040
Just try and make nodes with whatever type of data they can even be like comparing ASCII values of strings

312
00:25:54,040 --> 00:26:02,980
and summing those up or something like that and maybe inserting things, or if you find something that's

313
00:26:02,980 --> 00:26:09,850
equal like, you know, added if if it's equal, if there's an equal data member or something for one

314
00:26:09,850 --> 00:26:13,120
of the nearby nodes or something like that.

315
00:26:15,110 --> 00:26:20,090
I just mean like to know that you're currently on like her, so messing around with that will help you

316
00:26:20,090 --> 00:26:21,320
get a better grasp on it.

317
00:26:21,320 --> 00:26:28,670
And the more you do, the more you understand and the easier it will be to write this code quicker and

318
00:26:28,670 --> 00:26:30,290
more efficiently and.

319
00:26:31,550 --> 00:26:39,290
Hopefully this made sense you very important point is that the unordered list insertion should definitely

320
00:26:39,290 --> 00:26:48,870
be cost in time operation, no need to go through like we were before with a loop and make it sequential.

321
00:26:50,090 --> 00:26:53,270
OK, and with that, I will see you in the next lecture you.