OK.
Welcome to another video lecture.
Today's lecture is going to be primarily about adding an insert function to our list, but we will talk
about some other things first.
And one of those things lies in our list as BP file and is our append function specifically that this
right here in the list.
So we have been doing it in a sequential manner and for a reason.
We it was important for us to go over how to traverse the link list using that current pointer.
And we do it here.
We already did it here and we do it in our print function as well.
But if you recall during the theoretical slideshow, part, one of the main things that we talked about
was the fact that inserting something into a linked list, which is kind of amusing in that is an ambiguous
term.
The fact that we add something into our linked list when it is an unordered linked list.
That the reason the link list does well with that is because that can be considered a constant time
operation, you might remember me mentioning that in that slideshow.
And you might have caught on to this already and been like, Well, OK, well, why are we doing it
like this, in our opinion function?
This is clearly sequential time complexity.
And you would be 100 percent correct if that is what you were thinking because we are in fact looping
through in items in the list if we chose our basic operation here.
It would be a big go of in time complexity.
And that is not good because if we have an unaudited link list, it doesn't matter where we put it.
We can just put it at the front or the back, the head or the tail.
And there's no need for us to really maintain an order if it's on order.
And that should be a simple Constantinou operation, and that is something that put a list above a vector
for that specific operation.
And like, you know, having to shift everything back, that's what we were talking about in that slide
show.
And so that is something that we need to change now, since we are going to make our insert function
today, the reason that we would even make an insert function, in fact, is when we want our linguists
to be ordered and we will see that we will in fact have to move sequentially through our linked list
because we need to go to a specific position, the link list during insertion to put our new node in
the right spot as as far as its data relates to the other nodes data around it.
So something to take away if you take away one thing from this video lecture, it is to realize that
the insertion operation into an unordered link list is going to be a cost and time operation.
So a live one.
But if we have a ordered link list and we need to insert.
Then that becomes a sequential operation, which is big of in.
So let's go ahead and in fact make our append function something that is a cost and time operation.
We don't need this whole while loop here.
So I'm going to go ahead and take this, delete it or go in here.
All we really need to do since it's unordered is just put it right on the end, and we don't need to
move over everything to get to the end because we're already keeping track of the end and that is with
our tail number right here.
So all I have to do is tail.
Next is going to be new node and then I can say new nodes preve is actually going to be tail.
And now I can update tail Munich because it's the new last thing in the list.
Of course, I also want to put my size plus equals one here, but that is all we really need to do here
through our list, so we don't need to move through it and add the new node to the end.
We are just actually adding new node to the end.
So if you already noticed that and you're kind of like, what the heck?
There's these videos lectures going on?
And he said that this is Constantine and we're not doing it in Constantine.
What's with this?
Apologies for that.
If it's frustrating.
But there I did want to show you how to move through the linked list and kind of ease people into it
if it wasn't so obvious immediately, how to do that.
So even though we did have our print function here.
But now we are changing it, and I feel like it should show you the difference between moving sequentially
and when you need to do that and when you do not need to do that.
So you are trying to keep any specific order to things and certain things in order that is going to
be linear.
If not, if it's on order and you don't care, you can just add it to the end like this.
OK, so let's move on to the actual insert function.
I'm going to go to my header file here and I say, avoid, insert, and I'm going to put this to data
valid just like Append.
Go back to a CBP file.
I'm going to copy this and I'm going to paste that here.
And I'm going to say void list key in search, and I'm going to actually copy all of this up here because
if we have nothing in the list, insert and append aren't really different.
We're just putting one item in there.
We have nothing and it's just going to be have equals tail equals Nenad because there's nothing to really
compare it to, to put it in the right spot at the right size, just to insert it and set everything.
This, though, if we have one item in this, yeah, if this size is equal to one, we're going to have
to change this one a little bit.
I will be copy paste in this code.
But first, we're going to have to compare with what's in there, and I'm going to use the head instead
of the tail to look at its data.
So I'm going to say if heads data is greater than or equal to new nodes data, then what I'm going to
do is say heads.
Previous is new node and then I'm going to say new nodes.
Next is going to be head.
And then I'll update the head to new node because we just inserted it in front and I will, of course,
update my size.
So I'm going to go along with a little visual drawing here to just make things a little more clear,
hopefully instead of just smashing code and hoping that you get it from this text right here.
So this operation is going to look like this drawing right here.
I have admitted the previous pointer and next pointer here, the pretty pointer for new note and had
pointers next just because we're not changing those pointers.
But you should, you know, if you don't like that, then just envision them right here because there
would this one be pointing to null?
And this next pointing would be pointing all over here in the case that we're looking at right now,
there's just one item.
So we're inserting in front of head because in fact, the case that we were looking at was the case
in which head actually had a greater data value than new node.
And so we're just setting has previous to new node and Nuno's next to head, just like you noticed here,
has previous new node units next to head.
OK.
So, otherwise, if that's not the case and it is heads data is not greater than or equal to Nuno's
data, then we're just going to copy this logic here because we're going to add it on the other side.
So I'm going to copy and paste this right here, and I don't really need to put this new here somewhere
in a race that.
OK, so hopefully that makes sense in that case, we would just be adding this new node over here on
this side.
OK, so.
The Else. case is going to be a little bit more complicated.
And so what I'm going to need to do for that.
Yeah, I will kind of want to copy paste, but I.
Got rid of some of my stuff right there, but I can just do this in New L.A. corner, okay, it's A.
T. Pointer or eagles head.
So I'll put that there.
So we have a curve pointer and then I am going to put the same wildly here.
So there is not equal to null pointer, but we're going to have to look at a few different things here.
If we want to insert it somewhere in this one, which I'm calling like the middle, you know, the middle
or the end, in fact, is going to be the same since our strategy is going to be similar to what we
did right here, where I am inserting it before the node that we're looking at.
So I would be inserting it before occur.
I'm kind of looking to see whether, you know, let's keep moving until we find something that is greater
than or equal to.
And then I'm going to insert the new node before that.
So encourages greater than or equal to.
I will insert the new node before that.
And I have another visualization here that can make this a little bit easier.
So this is one where you insert insert new node in between to other nodes.
So if you don't, if you imagine this not existing here Courier's previous, it would be pointing to
here and this node.
That's why I have named this node cur preve because we are actually going to be using something like
this in our code.
So if that's a little confusing, you don't like that.
Apologies.
I just put it there because it's it's what we're going to use in the code.
So I was thinking it might be a good thing to name this.
And also, another really important thing is more so to explain why there is needs to be a specific
order in which we change these pointers.
That's why this is also useful in that situation if I can come up with an example here.
Is basically.
If you were to set, let's see.
If you were to say curse, if Kirk Preve is a new node, if you did that first.
And then afterwards, you did new nodes preve.
Is cur preve.
If you think about that, you just set her approved to new node, so essentially you're just saying
new nodes, PREVE is a new node.
So that's pretty much the only example I can think of right now, and I'm not sure that's the only example,
but that is why we need to do things in the right order, and you'll see that we will be doing these
in a specific order that avoids that issue.
But then besides it, besides that, this picture just kind of helps you get the gist of what we're
going to be doing is pretty simple.
We want to insert it here.
We need to make this thing.
You know, if it's going to move here, this thing needs to point to that.
Nuno's next need is the point here.
It's previous news to point here and this thing, this point here.
And so it's just avoiding that like strange like updated this to new node when this is the thing that
I need to reference and I'm just pointing a new node to itself now, somehow that's not what we want
to do.
We don't want this pointer to actually be like following this arrow and coming back of this arrow to
itself.
So we're going to avoid that, and we'll jump back to this drawing, too to confirm what we are actually
doing in our code.
So what I'm going to do is I'm going to start out by saying if parents data is greater than or equal
to new nodes data.
So we're just checking to see if that is the fact that this is in fact the case.
We have arrived somewhere where current data is greater than or equal to our new nodes data.
And then I'm going to look at this case where I'm going to check if we are at the head.
So I'm going to say if parents.
Previous.
Is equal to null pointer.
So that is the case in which current is just at the head and we haven't moved at all.
And this is fully possible, you know, we could have a links, links list of links, whatever you know
in and we are at the head and suddenly we realize that our new item is actually smaller than everything
else in the linked list, so or equal to.
So we need to deal with that.
And so we are going to be doing something that is very similar to what we just did up here, so I'm
going to copy this, actually.
Because it's the same type of pointer changing we're doing here, except this is going to be her.
So we'll say.
Cur preve.
Chris Preve is New A. And we are going to put colonel, it's going to put that just because we put her
here and we're updating the head to new node changing the size.
And once we did this, we can just return because we've already added our nodes so we can break out.
And you'll see that this kind of affects the way we write the code in a bit as well, the fact that
we have the returns in here.
So otherwise, if we are not really otherwise, but it's a else, if I'm going to say if we are in between
for the end.
And so I'm going to say.
Actually, yeah, this will be an Alice.
This will be an Alice, my apologies, because it's basically those are all the cases we're either in
between anything and so I'm going to have an else there and I must say new nodes.
Previous is now going to be curved for you.
And so let's take a look here.
We're saying new nodes.
Previous is her previous.
I'm doing that before this right here because if I said KERS, previous new node and then I said Nuno's
preve is reprieve.
Well, that's new node.
Previous new node.
So that's what we're voting right here.
I'm given that out of the way, right off the bat.
So then next we will do cur preve.
So this is just that next thing that I was talking about her.
Previous Next.
Which is actually going to be on this same node here.
So Curves previewed her.
Previous Next.
It's going to be new node.
So hopefully, the drawings can help you as well when you're doing this, it's kind of nice to just
draw it out on paper to make sure that you can understand what's going on before you just start coding.
So we're setting curves to be of next Noonan.
Next, I'm going to say curves for you.
Nope.
I'm going to say new nodes next.
Actually, in our time today, Nuno's next is going to be.
Kerr.
So we have new notes next, now going to Kerr.
We did this one and we did this one.
And now we're going to do this one and then this one.
So that's the order.
So Nuno's next is her.
Actually, I was doing her, I'm doing her pretty full after this.
We could do this either way, I believe, but I'm just going to say her reprieve this new node here.
So I'm sorry, I'm actually going to do that the different way, a different way.
I'm doing her reprieve and then new nodes next.
I like that.
And then I don't want to forget to do my size, so I'm going to do that, so I suppose one.
And of course, we can just return right away after that.
OK, so.
Now what we need to do is put and if actually so I'm going to come down here, so this is.
We have an F and an A+ right here.
But then what I'm going to do is I'm going to put.
And if after this is well and we are going to check again, if Current's next is no pointer for the
end.
And I'll explain why we're doing that in just one moment.
So I want to make sure that these are lining up here.
I have that.
OK, so.
I'm actually putting it outside of here, and I'm saying if parents next go to no point here, so that
means we're at the end of the list, I'm going to say parents next year, you know?
And new nodes for you.
I'm putting this extra thing at the end.
So we avoid the case, so basically this was all wrapped in an effort that said, if current data is
greater than or equal to Nuno's data and then we have this down here, we're adding stuff either in
between or at the end, but we don't want to only just add that when it is greater than or equal to,
because if we did get to the end node and the case is that our current data is actually not greater
than or equal to Nuno's data, then that means we actually need to add it on the very end and make it
be the tail.
So I add and accommodated for that case quite yet.
So that's why it's going to be outside of these brackets because it is not going to be within this if
where it's greater than it's the other case.
So I'm actually going to just add that death right here and we can just make it an if since we are returning
and all these cases anyway.
So I'm going to say now tail equals new node because all we had to do before adding it out there is
change.
These currents next is going to be new node because this is basically the tail that we're on right now.
And then we just point back from new node to occur in our new nodes.
Next is null as well.
So that's why we only have to change these two pointers and update the tail and update the size.
And we are good to go.
I'm also going to just return as well.
So the only thing we really need to add now is the cur equals cur arrow next because we need to move
along.
And this is what drives it, as we talked about before.
OK, so hopefully everything is right, if not, I will be encountering some errors that we get to debug.
But this should be good.
We have accommodated for pretty much all the cases that we need to think about.
So we insert in the beginning if it's necessary, if some, if this was the case, that there was more
stuff over here.
So heads next pointed to something.
And then maybe we have X amount of items after that, an amount of items, I should say.
But the new node was less than everything in our list.
We would do this and add it in the front.
So this would be the operation that we would do.
We would do otherwise.
If it is greater than CUR.
I'm sorry.
If CUR is greater than or equal to new node, then we would just be doing this and adding it before
and then the last.
If that we did is not represented here, but what we would be doing is taking this and adding it over
here.
So less pointer changing.
OK, cool.
So hopefully that worked out, OK.
Let's go ahead and update our main because we are now using Append.
I'm going to change this to insert.
And I've already commented this out, so I'm just going to be printing the integers.
I went ahead before the video was being recorded and changed my input to just have an out and out of
order, a sequence of single numbers here, single digits.
So if you going to go ahead and put anything in whatever order, but I'm just adding single digits here
since we are reading things and as chars.
So let's go ahead and run this and cross our fingers and hope everything works OK?
OK, so we have.
At issue.
We're.
And.
Okay, next.
OK, so I did not add parentheses here.
It looks like let's go ahead and run that again.
OK, so.
Looking pretty good.
One, two, three four, five, six, seven, eight, and I put all those values one three eight in
this input file here out of order, so it read them in and printed them out in order.
So that means that our insert function is working correctly.
OK, so hopefully you have enjoyed this video and it made sense to you.
You can definitely refer back to these drawings.
I will try to include them in the course content so you can refer back to them.
And it is a little confusing the changing of the pointers, but practice makes perfect and a good exercise.
I will not be having this as a coding exercise, but a good exercise for yourself is to try and insert
based on some different.
Some different ordering.
Just try and make nodes with whatever type of data they can even be like comparing ASCII values of strings
and summing those up or something like that and maybe inserting things, or if you find something that's
equal like, you know, added if if it's equal, if there's an equal data member or something for one
of the nearby nodes or something like that.
I just mean like to know that you're currently on like her, so messing around with that will help you
get a better grasp on it.
And the more you do, the more you understand and the easier it will be to write this code quicker and
more efficiently and.
Hopefully this made sense you very important point is that the unordered list insertion should definitely
be cost in time operation, no need to go through like we were before with a loop and make it sequential.
OK, and with that, I will see you in the next lecture you.