Today, we are going to go over the actual code implementation of a singly linked list.
So that was the first one that we talked about in the slideshow, which was more theoretical explanation
of link lists.
Now we are going to write the code for it.
So I went ahead and created a new project in Sea Lion, just called it singly linked list, and it gave
me a main file here and main function, which we will be using as our client file to instantiate the
link list and prove that it works.
So I'm going to go ahead and leave it, but delete that.
Hello world, of course.
And I'm just going to leave main CBP alone for now.
And so today is going to be a very basic.
We're just going to make like a super barebones version of a linked list, so it's not going to have
everything that it probably should have.
We will go into that and some of the next videos.
But right now, it's just kind of making the link list data structured just enough to show that it works
and that we know what those pointers are doing and everything.
And it'll just be kind of a proof of concept.
But so we're not going to add like an assignment operator or any overloaded operators or a copy constructor
or anything.
We're just going to kind of do the least work that we can to get a link list up and going.
So I'm going to go ahead and create my first class here.
I'm going to make a header file.
This is going to be for the nodes of the link list.
So for make this new header file and I'm going to call it El Node, so that's going to be L.A. H.
All right.
And so let's define our L.A. class
and put a public section here.
We're going to make our constructor and then the next thing I'm going to do is make a function that
can return the pointer to the next node.
And so that is going to be returning an L node pointer.
And I'm going to call it next.
And then I'm going to make a function that can set the next node, so that is going to be a void function,
and I'm going to pass it a node pointer, then I'm going to call next as well.
And then we have our other component, which we saw in the slideshow, and that is our data component.
So we want a way to access and set our data.
And so I'm going to make this together and put the ampersand there and all that data.
So if you are not encountered this before, by putting an ampersand, we are able to have this function
as a setter and together in one.
But that might have been gone over already.
And let's go ahead and make the members.
So we have our data.
I'm just going to underscore data.
And then we are going to have our next pointer.
So that's one node and L.A. pointer, and I'm going to do call that underscore next.
So let's go ahead and move on to the implementation and we'll see exactly what we're going to do with
these next pointers.
It's pretty simple, but.
All right, so let's do a source, file my call this download step.
And of course, we want to include our header, so I'm going to do that first and I'm going to do namespace
STD.
And here's our constructor.
And so as I mentioned in the slideshow, we are going to set our next pointer to null in the beginning.
No point here
and you'll see in a bit.
And how similarly to how I explained in the slide show, it is nice to have it is null pointer so we
can check against that to make sure that we're not going off the end of our link list or and or trying
to reference some random area of memory or something like that.
OK, so I'm also going to put data equal to zero to start that off.
So let's make this first.
Next function, this is going to return the node pointer.
And so what we are going to do is just return that next value.
So this will be our getter, essentially for a node next pointer.
OK, well, I want this to be Boyd.
And this is just going to be the setter.
So I'm going to
pass this next value in there.
And then we will just be setting our private data member next equal to this past value next.
And then the last thing to do is to put our data.
Part of it is this will be our surrogate here for the data, and all we're going to do is return data,
and that's it.
Not a whole lot going on.
We have all the basic things that we need now.
And yeah, as I've actually you can see, I'm just going to make it link list of integers for our data
component.
It's just going to be a simple, simple link list of numbers there.
So I'm going to go ahead and make the link to this file now.
Both those files little English class, so I'm going to make a header.
I'm just going to call this list.
OK.
So let's go ahead and define a class
and then in our public section and the constructor, of course.
And so the two functions that we're going to do to make this as simple as possible is we need a function
to add stuff to our linguist.
And so I'm just going to make a function that appends items to the end of the linked list.
It's just adding items to the end of the link list, basically.
And later on, we'll look at the operations of inserting into a link list and some arbitrary position,
kind of like we talked about in the lecture, and we will maybe add things to the front like pre spending
items.
And then besides that, we the only other function we're really interested in right now is just a print
function that will move through the link list and print out all the values so we can see that we successfully
created a link list and we're able to add them correctly.
So I'm going to start out with this function of adding them to the end, and I'm just going to call
it append rather than add.
And I'm just going to call this data Val for the integer that is passed that you want to add to the
list.
And then I'm just going to call this pin function print p void function as well.
And then as we mentioned in the slideshow, I'm going to want and a pointer and node pointer for head
and tail.
So this keeps track of the first node in the list and the last node in the list, and it's asking me
to add that L node class here.
So I am going to add that I'm president alternator, but it didn't seem to work, so
I'm just going to add that there.
And then we're going to also want to keep track of the size of the linked list, so I'm going to put
a member variable here for the size of the list as well and.
I don't really it probably would be good to put a.
Getter function for size.
But, you know, I'm just going to tell you that right now we can add that if we end up needing that,
but I don't think that.
Not sure where they're actually going to want that right now, but next thing to do is do the implementation,
so let's go ahead and supervise sort of source file.
Won't you list us Rippy?
OK.
So I'm definitely going to want to include our header.
And we're also going to want to include the well-known class.
Right,
well, it's OK.
And since we're printing, we should include I stream.
And I'm also going to you using space as well.
So let's make the constructor, of course.
And just like we did with our next pointer in the node class, we are going to set our node pointers
head and tail equal to null pointer as well.
And size equal to zero.
So I want to jump right into this append function.
All right, so the first thing that we're going to want to do is, of course, create a new node to
put in our list.
So let's go ahead and do that and put a little comment here and say create a new node and set the data
member as well.
So to do that, we'll just be L Node.
Call this new node and then we're going to dynamically allocate this.
So it's going to be a new node pointer, and I'm immediately just going to set the data value right
now equal to the past data.
Well, we want to add to our list.
So.
For any new value to the end, we actually have kind of three cases that are going to be different.
We have the case in which the list is empty.
We have a different case in which the size is one.
And then we have a third case in which the size is anything greater than one.
And we'll see why we need these three different cases here, so I'm going to put if the list is empty
and so that's going to be if the size variable is equal to zero in this case, our head and our tail
are going to be the same because we only have one node that we're adding, which is our new node, then
we only have the option for the head in the tail to be the same thing.
So I'm going to say an equal tail equals new node because those are both node pointers and our new node
is also a node pointer.
And then I'm going to increase the size.
So I'm going to say, I'm going to say size.
I can just say size plus based on the same size possible form.
And then I have this other condition here.
Actually, let me put a comment.
So this is if the size of the list is one and let's say elseif
size equals one.
And this is actually going to be very similar to if the size is anything greater than one, except that
we're just going to want to set our head pointer our head, sorry, our heads next pointer to the new
node because we know that our.
Head is we only have one value, and we're adding the second one.
And so we're just going to be able to update our head pointer like that instead.
If we were add something adding a node later on, like, let's say, it had three values already in
it or sorry, even just two values.
We wouldn't really need to update our head pointer because we're just adding that third value.
We're not really doing anything that should change the head pointer.
So I'm going to say head
arrow next.
And then new node.
And so this is our.
Node classes next function that is the center there.
So if we go back to L.A. CP, it's this one right here.
We are calling this function and passing a new node pointer to it.
So that's what we're using on this line, 28 right here, and then we're going to say tail equals new
note because now we have two nodes.
We said our heads next to that and we're going to have the tail be the latest node that we just added.
So and then tails next.
Just so to point that out again, tails next was said to no pointer.
So that's what tail is.
Tails next pointer is.
So now for the no last option, we're going to have to move through our list to the last node in the
list so that we can successfully add it to the end.
So I'm going to say move through list and add new node to the end.
And so this is going to be.
So anything basically the case that it's not either of these two conditions.
And so to do this, to move through the list, what we're going to do is we're going to create a temporary
pointer that starts at the head.
So it's going to be equal to the head pointer.
Someone declare a new node pointer pointer and we call this curve for current.
And I say equals head.
So it starts out as the head and then we're going to want to loop through.
Until we get to the very end and then we're going, I want to add our new value there.
And so what I'm going to do actually is I'm going to say, Wow, this current pointer is actually not
equal to no point here because I know if it's equal to no pointer, then that means that I've gone off
the end.
Like I kept going and kept referencing the next pointer going on and on until I got to a point where
I was off the list.
And now I was at no point here because the.
The last items next pointer to the last nodes next pointer, it's going to be pointing to null.
So if I went off the end, I'd be in pointer.
So then I'm going to put a condition and I'm going to say if turns next is in fact null pointer.
And this is our getter here.
The one where we hear let me just jump back here, so we're calling this right now.
And I must say, if that's equal to null pointer,
then I'm going to say that it's next.
And now I'm going to use this other next function, the one that we used on this line.
28 here I'm going to say that is going to be new node.
So we're just connecting things with pointers here.
It's really all that's going on, and I'm going to update my tale now to that, you know, just like
if we just like we did in both of these.
Conditions up here.
And if that's the case, I've already added that I don't even need to do anything else in this loop
at that at this point in this condition, if that's been met.
So I'm just going to actually return because we don't even need to do anything else in the function
at this point.
And then the last thing this is really what it does.
All the work here, this line right here.
So I'm saying current equals cur arrow next strike her equals her arrow next.
And so this is our getter in what we're doing here is essentially moving the current.
Pointers, so it is a known pointer, but we can also think of this as like a a pointer just kind of
iterating through our list like an iterator.
So this is how you move it to the next item.
This is essentially what is driving our sequential movement through the linked list.
And that should be good for the pin function.
I'm just going to leave it pretty basic now.
We said we aren't really doing a whole lot except just trying to prove that we can get this thing working.
OK, so let me add this print function now.
So we're going to essentially do the same exact thing that we did.
Right here.
Moving through the list instead of adding things, we're just going to be printing them out, of course.
So I'm going to say look through the list and print out these values.
So let's go ahead and make another current point here, and I'm going to do the same thing and just
call it Carrier said equal ahead.
So we started at the beginning and then make this other while live.
It's exactly the same.
I really could just copy it, but I'm just going to tape it and I'm going to say it's good.
Let's not equal null pointer.
And then all we're going to do is print out our data so I can call that function here.
So we're calling that same function.
Here is where we said it.
It's probably something I should have mentioned if you haven't done this before, this is also going
to be the syntax for using that setter getter where we put the ampersand reference in front of it.
So basically when you.
Said it and get it is kind of the same syntax, so here we set it equal to something we're calling it
and then putting the assignment operator.
And then down here, we're just calling it, and that's giving us what we want, so we could, you know,
if we wanted to say something else equal to it, we would just be like putting the assignment right
here and add some variable.
But you might argue know that.
So of that, if that's something that you're already familiar with.
And I'm also going to add a little arrow here, just so it just kind of makes a little extra sense visibly
if that means anything to you.
But yeah, these will just be like you can imagine these as our pointers chaining them together.
So I'm going to print this out and I'll just kind of be in a line so we can see what our link list looks
like.
And then, of course, I'm going to want to add this line that really drives it, which is the curve
equals K Arrow next.
And then after this, I'll go ahead and just print out a new line there.
OK, so that is actually all we're going to put here.
Well, go ahead and save this.
And then let's go to our client code that is going to be our driver program for this.
So I think that what I'm actually going to do is just have a stake in some.
Input from a file, so I'm going to go ahead and include the stream library there
and then of course, what else do we have to include our.
Header file.
And yeah, I think that's all we really need.
I think I need the known class.
OK, so for that, of course, I'm going to want to put some command line answer to this, which we
will just be doing in our edit configurations for Sea Lion, but we don't want that.
And then let's do a little check here to make sure that the users actually enter into arguments.
Of course, we won't be using the terminal for this.
We're just going to run it and sea lion, but still want to put it here.
OK, yes, we did want to run it differently.
So I'm going to say usage and put our executable here are in V0.
And then say you should do that and then put the name of the entire file
just a little error message there in case there is no argument for an input file.
OK, so I'm going to stand Ireland to list here.
I'm just going to call it link to list equals new list and then we'll declare our stream here
and call this list stream.
And then we will open our stream and then we'll make a variable for our data and then we'll just take
it in a loop.
So up to this stream, open
the one place and
to load data variable there to take in the integers.
And I'm going to say, well, this stream input data and we're going to say linked list and then we're
going to color append function and we're going to put that data value that we're reading from the file.
And so we're passing that here.
And then we're creating our new node and then setting that data value right here and then, of course,
the rest of the function that we're already aware of.
All right.
And then once that's done, I'm just going to want to go ahead and call the print function on my linked
list
so we can see that we vetted everything correctly.
And so at this point, I probably should add an input file.
So let me just go here, I'm going to make a new file and I'm just going to call this and put.
Let's see.
Text file, yes, I should have said and put that text, he.
All right.
So.
Like that?
Yeah.
So I'm just going to do like something like that one through seven.
So you go ahead and say this and let's go back to Maine and then we want to set our.
Make sure everything looks good.
Go ahead and.
Said this in the edit configurations.
So.
And put that to me, and then I'm going to set my working directory here.
Simple, singly linked list.
OK.
So that all be set up to play.
And then let's see if it runs.
So go ahead and right now.
OK.
No.
Did not run what seems to be the problem.
I think that maybe.
You know what I'm going to add, I think it's actually just inputs.
Don't actually have the extension on there, so let's do this.
OK.
So did not successfully add the.
Items to the linked list.
So let's figure out what the problem is.
Let's go to our link list implementation here for the append function.
Just.
Let's just see some.
Let's just do some D.
Bugging.
So.
Head size of continue.
So tell us one.
They do value three.
So let's just go ahead and step through this year.
Aha!
We did not update our size.
That is the problem.
OK, so we're going to want to add.
Definitely going to want to make sure to update our.
Size of our blank list.
We never did that here and in there, either, so
size plus equals one.
And in here, we also want to do that as well, so we successfully at A..
Size, think of one.
OK.
So hopefully that fixes our problem.
Sorry for the delay there.
Sometimes I think that getting errors on it, though, is kind of nice.
Just as a chance to go through the debugger and, you know.
It's just naturally, it airs on a lot of things, so it's good to kind of walk through it, and debugging
is definitely one of the most valuable skills, so sometimes it's a benefit.
So let's run this, and yet that looks like it's pretty nice.
One two three four five six seven And we see our little corners there that we print out as well.
So like I said, this is just a really basic link list implementation.
There are a few different ways you can do it.
You, of course, can use a struct for your node.
And I definitely encourage you to go online and kind of see what other people have done for implementing
link lists and just use the style that you're comfortable, comfortable with and whatever makes sense
to you.
Everyone has their own programming style, and of course, you get used to the coding style and code
base of whatever place you might end up working at.
So it's good to look at different ways of doing it.
And then in the next video, we will hopefully get into maybe changing this into a link list and then
add some more stuff that we should have, like copy constructors, assignment operators, things like
that, because this is really just a super basic implementation of a link list just to just to, like,
ease into it.
So everything makes sense before we start adding all the bells and whistles and everything like that.
OK, so I hope this was educational for you, and I will see you in the next video.