Intro to Linked Lists in C++ | Fresdev99 | Skillshare

Playback Speed


  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Intro to Linked Lists in C++

teacher avatar Fresdev99

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Lessons in This Class

22 Lessons (1h 19m)
    • 1. Intro

      0:42
    • 2. Class Node Concept

      3:00
    • 3. Class Node Coding

      16:27
    • 4. Linked List Concept

      3:09
    • 5. Linked List Intro Coding

      3:04
    • 6. addFront Coding

      4:48
    • 7. addBack Coding

      3:16
    • 8. removeFront Concept

      2:02
    • 9. removeFront Coding

      3:15
    • 10. removeBack Concept

      3:12
    • 11. removeBack Coding

      5:03
    • 12. removeBack Revision Coding

      1:05
    • 13. Loop Through Linked List Concept

      2:49
    • 14. displayList Coding

      2:46
    • 15. Testing Linked List in main() Coding

      3:46
    • 16. Class Stack Concept

      1:51
    • 17. Class Stack Intro Coding

      3:02
    • 18. Class Stack Continued Coding

      2:36
    • 19. Class Queue Concept

      1:11
    • 20. Class Queue Coding

      4:53
    • 21. Testing Stack/Queue in main() Coding

      6:30
    • 22. Project Scope

      0:49
  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels
  • Beg/Int level
  • Int/Adv level

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.

22

Students

--

Projects

About This Class

Prerequisite Knowledge: I feel anyone could follow this tutorial, but it would help to have a basic understanding of how to define functions and use an array(so you can understand the contrast between a linked list and an array). You also need to know how to setup your coding environment for C++(i.e Visual Studio).

In this class we will be creating a node class which is the single component of a linked list. Then we will craft our linked list by connecting nodes together. Once our linked list is complete we will construct our stack and queue classes utilizing a linked list. All of these classes will be tested in our main() function.

If a video has the word "Concept" included that indicates it is a whiteboard explanation.

If a video has the word "Coding" included that indicates it is a screen demonstration.

Meet Your Teacher

Teacher Profile Image

Fresdev99

Teacher

Class Ratings

Expectations Met?
  • Exceeded!
    0%
  • Yes
    0%
  • Somewhat
    0%
  • Not really
    0%
Reviews Archive

In October 2018, we updated our review system to improve the way we collect feedback. Below are the reviews written before that update.

Why Join Skillshare?

Take award-winning Skillshare Original Classes

Each class has short lessons, hands-on projects

Your membership supports Skillshare teachers

Learn From Anywhere

Take classes on the go with the Skillshare app. Stream or download to watch on the plane, the subway, or wherever you learn best.

Transcripts

1. Intro: in this class, we're gonna be going over the introduction to link lists in the language of C plus plus. So the first thing will cover is creating our class. New after that will be creating our class link list, which will combine multiple knows together by using links and foreigners. Number three will be creating our class stack, which is a data structure that utilizes the link list. Number four will be creating our class que, which also uses the link list. And last of all, number five. We're gonna be utilizing the stack and queue classes and our main function to use functions such as pushing pop. Thank you and thank you. 2. Class Node Concept: So in this video, we're gonna be covering our class nude. So this is gonna be a small structure that we build that's gonna be used to build up our link list. So this is gonna be an example of each link in the lift first, before I tell you exactly what types and everything we're gonna be using, I'm just gonna kind of give you an example of what it would look an example note would look like. So I like to represent it. You know, basically, in a rectangle, this is just to kind of make it a little more cleared of what's going on. It doesn't exactly look like this in memory or anything. So we're gonna be using an energy value. So, for example, be storing a number three here and the second field we're gonna be storing a pointer which could be pointing at nothing should be a no lawyer. War could be pointing Teoh know that, just like this one. So that's that's the goal. The types to do this. So like I'm gonna be using variables, i d. For the number that will be like I d. And then for the the Pointer field I'm gonna be using and no pointer called next pointer. Have you looking like this? So the syntax for CPA? Suppose if you're not familiar, is if you put a star by the type. That's how you to note a pointer you could actually move this to, like, right here to the next point to be just a valid I kind of switched between two. It doesn't matter either way works. Um, but just know that the system point to the same type. You can't I can't point an integer to a node, etcetera. So just keep that in mind. So you basically have two choices. You're gonna either point to another note. We can point to nothing. But you can't point to other types. Um, yeah, that's this. If you're not that familiar with pointers, which some of you are some you are pointers basically gonna be pointing to something else in memory. Um, in an array, it's sequential. So the values in the rain will be right next to each other. Memory in a link list. That's not necessarily Truman is usually not true. So they're connected by these pointers. So basically these arrows, So these could be three completely different locations in your memory, but they're they're connected because of the pointers himself. 3. Class Node Coding: Hello, everyone. Welcome to this next video. So in this video, we're gonna be covering how to set up our basic template for our main dot CPP, which is gonna have our main function. And we'll also be going over how to create our node class. Um, so to start out, just make sure you have two files ready? Uh, main dot CVP and no, no, no dot h. Uh, I'm using visual studio, So basically these air in the same directory, I just have this under header files in this under source files. Um, whatever, I d You should be fine. As long as they're in the same directory. And they can, ah, you know, connect to each other later on. So to start my main file, I usually start them like this. All do include I o Stream, and I'll be using Name Space Standard. So I o stream is just so I could do see out and see in to display to the terminal, and then the name space standard just allows me to do this to print to the terminal instead of this. So it's just a little bit easier to work with. It's not required it's just a little easier. And then in the main, I'm gonna be doing return zero. So once I hit this line, my program will terminate. So we'll be well to be defining classes, and we'll be calling them in here later. So, like, will make an instance of a node or a link list or ah q r stack. Um, so that's basically all we're gonna have for our main to start out. Uh, we're gonna jump straight into creating our node class now, so click on no dot H. When you start your node class, make sure if you're using the header file like me, make sure you include the include guards, So you will do something like if and death. Uh, you do node underscore H and you'll define knowed escort each and then at the end of this, you're gonna do end if this is mostly just further compiler. So it checks. If you have anything else named this and if you had multiple, it'll only execute one. So it's just making sure you have a unique it's not trying toe duplicate the same header file or class or whatever you're using. So you actually create our class. We're gonna just type the word keyword class. And I'm going to use a capital for note here just to kind of show you the file name and the class name. They're not exactly. They're not the same. Um, this is within this file, but it is. This is the class name itself. So, for this class, um, like the concept video I went over, um, we're gonna be using a few variables, so I'm gonna set these variables under the private portion of our class. So we'll have meant I d here, and we'll have knowed star next pointer here. Um, the main thing when using private, it just means that you can only access thes variables within this class. So I can't access them directly through the main or another class, and then I'm gonna put the functions is public, so I can access them in the main or whatever class I'm using toe call the nude. So, um, the first thing you want to do when you define a function for a classes you want to make the constructor. So the constructor just takes the name of the node itself. So be like Node called uh, parentheses, parentheses, and I could define it here if I wanted to, but I'm just gonna choose to define everything below the class. So to define my function, I'm just gonna simply type the word node. Uh, colon. Colon. No, this is the function. So this is the class name, and this is the function within the class, and then I can define it here. So for the constructor, um, I'm gonna elect to make the I d negative one, and I'm gonna elect to have the next pointer people to know, Pointer. So this night of one just kind of indicates to me that I didn't assign another actual value to my node yet. And then when I created Node, it's just gonna point to nothing. So will be responsible for connecting the no toe other point. You know, other nodes in the future. By default, they don't point to anything. Okay, so we have our constructor. Now, we're basically gonna be working on centers and getters. So the 1st 1 will do is we'll do Ah, it'll be avoid. It'll be avoid set idee, and then it's gonna take a ent new I d like a lower case right there and will define that function right here. So we dio So you need to put the output of this function on the left side. So you do you avoid the class name corn corn set idee and you'll do and new I d which just matches this. So all we're doing here for the center is we are taking in a new value and we're updating what? Our current ideas. So this basically updates and saves our i d value to a new value. So Well, basically, dio a sign I d equal to the new I d. That's pretty much it for that one. Um, the next thing is to do ah, get her. So for a getter, we're gonna return the integer type, So we're gonna be returning the I d. Value. So you do get Heidi, and we don't actually need getting parameters to get it. So over here we'll do end node, and then we'll do get I d. And all we really have to do here is return our i d. Like I said, the main can't directly access this if we have it in private. So we just make a function called. Ah, get I d to access it. It's I would say it's good practice to do this. You could put this in public and access it directly. Um, but I would say this is generally a better way to go because you don't want to allow your variables to be accessed anywhere in some cases, but it depends on case by case you could do it. Also, if you wanted eso we have argued, I d. So the next thing we're gonna have here is we're gonna be, um we're gonna be doing the same exact thing for our next pointer. So once again, it's gonna be avoid set next PTR, and then we're going to do node star. Ah, new next pointer. So it's just gonna match this type so we'll go ahead and define this So we'll do knowed Star node. Uh, what is it, kid? Sorry Said next Pointer Teoh, it'll be node star. All right, so, to set it, we're basically just gonna do the same thing we're gonna do next. Pointer People's new next Poinar You can see my intelligence is a little slow. It doesn't show his green or anything should update so we define that one. So you just did turn green and then we'll dio get her so our get her will return the node pointer. So get next pointer and same thing Mess up slowing next set the next pointer I said next pointer. Oh, I see. I put the wrong It shouldn't be a nerd. Should be avoid here. I got too excited There. This one will be a node. This should be no star. So you are. Here we go, then. This one is just going to simply return our next Where? Okay, that looks better. Well, should be better. Okay, So reducing I was just gonna stop here. But I kind of like the idea of actually testing it out to make sure what we did actually works and toe show you guys. So I'm gonna use this in the main real quick, Um, to use it in the main. We need to go back here and we will include node dot each so that I include that file right here instead of tested out. We're going to dio we're gonna We're basically gonna have toe create an instance. Um so to create a instance, we need to use keyword new, so I'll show you. So this is the type is the node. We're gonna do a pointer and we're gonna be doing well. Call it a minute, then we'll say equals new node. So this is calling our constructor here. This is creating. So this is a pointer to our new node that we just made. So if we want to access our nude, we can. I'm just going to test out the constructor to show you the negative one value. So if I do a c out and I'll just make the formatting a little nicer So I'm just gonna add this tax year, I d And then we'll do my node get i d. So this is to see if the constructor actually returns negative one. Okay, so I saved everything, and then I'm just gonna run it. Okay, so this is just to show you guys that, um when we create a new instance of this node, it does return negative one. So that's what we wanted. So we want to update this value. We contest that too. So you could do just that. I get clear. We can say, um constructor. Okay. and then we will do. We will try doing this center so we'll just call this center. Okay, um, to do that, all we're going to do is call. We're gonna do my node. So the key is to have the arrow here. Whenever using pointers, you need toe use the arrow to get to these values. So we're gonna do set I d. And we're just gonna put a three in there, okay? And if we want to see, we want to see if it's actually in there. We can do this same thing as earlier. Actually, I could just do it again. Just copier for you guys when? All right, so you can try running this. Okay, So, as you see here for the constructor, it was negative one when we called this, um And then when we actually updated, the value did update when we, uh So we tested our center and our getter and 112 steps right there. So it looks like the idea is working. Fine. Um, we contest out real quick to see if we can connect to nodes. Um, this is basically a link list, but we're going to make a class for this, but there's just to see if it works. So to do that, we can do we can make another nude do node. I don't know your node he calls new node. Okay, so we have my note in your node here. So what we could do is we'll just we'll have my node point to your node. So to do that, you dio my node uh, set set next pointer. And we can simply put your note. Is it the types match? And just to test that they they're linked together. We can do this. So this will be ah ah, test Next pointer. It's called that. Okay, so we're gonna do this and then to test it. It's a little bit confusing, but we'll do this. Um, let's see. It would be would be your No, not minus. I will do. See out your node, I d. So we're gonna access your nodes. I d from my node. So that that just will indicate that they are indeed connected ingress space here and then to do this will do. This is the fun part, Will do my node So we'll get next pointer. So what do you my node get next, pointer, and then we can get idea of that one. So what I'm doing is I'm getting the pointer. And once I get the pointer value, I'm getting the i d. So reality I'm getting the idea of your node. See if it works. So I should get a negative one if I do it right. Okay, so these are the same as before. Um, the next pointer. So right here, I connected the two notes together. It's one direction. And here I'm basically getting the i d of your node by accessing my node. So I get the next value of my note, and then I get that i d. It's a little confusing, but it just kind of proves that they are connected. 4. Linked List Concept: Hello, everyone. Welcome to this next video. So, after completing our node class will now be able to use those nodes to be able to create a link list. So this is this is the general flow of the link list. What it should look like. So, for example, will make three notes here. I'm separated by with two parts we're talking about. These would be the pointers, the last one we always have pointing to No, we'll just put a three, but to no one. Okay, so the other thing that for our class link list, we need Teoh. Add two additional pointers that are not actually just part of the list to be able to do things like adding and no to the front or adding a note to the back or removing a node, because that's what we're gonna be doing in this class. So we need to include ahead, which is basically a node pointer. And for this tutorial, we're also gonna be making a tale. So this that's the general structure. Our linguist, um, we're also gonna be defining function to basically ad like, for example, add to the front. So at the front will would make like a new note. So for and then we would put this here. But you'll see we'll need to do things like if we add this to the front. Well, actually, have toe change where the head points to. It would now need to point to the new front that's not good here. Or if we wanted to add to the back, we would do something like this. We would we were basically put what's called fire whatever. And then we will change this to know. Then this would point here. And of course, the tail would be pointing there. Now, um, another thing we're gonna be doing is deleting from the front in the back. So, for example, we just deleted that when we were just changed of what we had earlier. So it would just be no where and same thing with the front, we would just make it how we had earlier, which just be like that. So that's basically we're gonna be covering. We'll go over the specific details in the code. In the following video 5. Linked List Intro Coding: Hello, everyone. So, uh, I just want to start off exactly where I left off earlier, before the concept video. So I just want to let you guys know that all this code that we're using for testing of node , we don't actually need it moving forward, so we can just remove that. And, uh, another thing is we can get rid of including no dot age, because we won't be accessing that directly through our mean. OK, so remain is just gonna be this little template that will be using later note will be keeping exactly the same. We didn't change anything. But the new thing is, I just made a header file called link list dot h. That'll be. This is using visual studio Microsoft Visual Studio. Uh, yeah. So it's under my header files folder. Okay, so now we're gonna actually be making our link list last year. So same as the node we're gonna have to do if in death. Uh, linked list. Underscore. Age do. Defying Boeing was score each and if at the end, and then we can put our define our class right here. Same things before using upper case for Lincoln List Okay, So just like the concept video, I'm gonna be making, um, two variables. One for the head and one for the tail. So they're both node pointers. So if you see if I do this, nothing shows up. So you need to make sure that you include our node class above this. So to do that, you would just do same is what we did earlier in the main. You just do know dot each. Then once you do that, you should be able to use our node class that we created and they were just gonna call ahead, and then we'll do another one called tail, and then we'll make our public functions and, uh, we're first. We'll do our constructor like we did earlier, and we will define it below here, so just be going list. Okay, So our default constructor, um, we're just going to tell what the head and Taylor point do, and by default will just have them putting to nothing, which is Ah, no pointer. So it's two had schools, Nor, I guess if we want to be cool, we could try this head, tell people's no pointer. That just means they're both pointing to nothing I could do to separate lines. But I just want to try that, I guess. Um, yeah. So that's our constructor part. 6. addFront Coding: So we'll be continuing from the last video in this video. I'm gonna basically make an ad front function. So just you will be returning. Nothing. So we'll do, Boy Ad. All right. And we don't Actually, Yeah, We need an I d. So we need to take in the value to save into the node. Okay, We'll be defining it down here. Avoid list front. Okay, so and this function, we're basically gonna be adding to the front of our link lists. Um, first of all, we need to create a note in the process. So just like what we did in the main when we created a new instance, we need to do that in this function. So we'll be calling node Pointer called Just call it unknown. He'll be equal to new keyword new, uh, new are constructor. And then we need to put this value into this nude. So say a node, uh, set I d. And on the issues I d. Okay, so now we actually have a node. Add whenever year, working with a link list. You need to. There's two main cases that you need to look at in general. Is one is if you have a list or if you don't have any list, it'll because if you were trying to call something like get next or set I D and it's a no list, it's a no pointer. There's nothing there. Your programs have not gonna work and crash so well, we'll check that first. So we'll say if we'll sit so the head. So if had is equal to know pointed. So this is basically are empty late, empty lists case. Okay, So if our head is equalled and nothing, that means you can just add this note in and not really worry about the rest or anything else. Really? So all we really need to do is set that had equal to, uh, node. And we can also set the tail, since there's only one nude tell was to note. So if it's empty list, we just need to have the head and tail pointing to that one node and as you can see like we could if there's only one node, we could really use Hydro hotel. It would be the same thing. So else this is the case where basically, there is an existing list. Okay, so If there's an existing list, it could be one note or it could be 100. It could be five. It's just more than zero. Basically, when you're adding a note to the front of a linguist doesn't really matter how long the list is because the connection that you're working on only has to do with the front. You're not touching anything beyond the original head of the list. Okay, so what we need to do is we have our our node right here. We're gonna set the next pointer of this node to the current head. So our current So now we're basically where we have our new no pointing to the old front of the list. And then once we do that, we can set head equals two a node. So we're resetting our had pointer, pointing to the front If you notice I'm not adjusting the tell because the tell is only adjusted when, after you know the very first time you put a note in the list and that will keep it in the back so we only have to adjust the head. If I wanted to optimize this, I could take this and put it right here because I'm doing the same thing for the head and each, but I just, uh you know, So it's easier to understand for you guys, for each case, I'm just gonna leave it here, okay? And, uh, that's it for this function. 7. addBack Coding: so in this video will be creating our ad back function. So we'll start with the void on back, and I d And we'll be defining it down here to avoid linked list ad back I d. So to start off, we're gonna do the same thing. Is that front? We need to actually create our nude knowed star. No. Feels new nerd. So just a side note of some of you are unaware I can reuse variable names as long as there like you see, I use the same one within this function. The scope of this is within this function, so I can repeat and then not have any, like, conflicts between them. Same thing with I d here. Okay, So same thing I need to set the node I d. I said I d just gonna be our i d here and same thing. We need to check if there's a list and if there's not a list, so this would be if there isn't a list. So we've had equal to know, Pointer. So adding to the back or adding to the front when there's nothing there. So when we create when it's only when it becomes one note only. It's the same exact thing. So we can just set head people to a note, a node and then same thing. Tell people to, uh, no. So they're just pointing to the same thing. So this would be, uh, empty last case. Well, doing else here. And this will be same things before exists. Thing less case. Okay. Um, so this is the one we gotta think about this a little bit different. It's similar, but kind of the opposite. I guess so. We want to add something to the back. I told you that we made a tail. So the tail is pointing at the note at the very end already. So if we dio so free to tell, you can actually do this. If its point of this, you can actually set the value from the tail. So if you set next pointer and you said it to a node, the one we're trying to put in. So now our tail now points to another node, and then all we have to do is reset the tail to a nerd. And if you see the pattern like and I can also put this on the bottom like I was telling you. So we're resetting the tail when we're adding to the list, which makes sense, right? Because of you making a longer need. Make the tell one note farther down, and that's it for this function. 8. removeFront Concept: All right. So this video go over? Kind of. How did do front? Because I felt like just doing the code itself was a little bit. So we have to make an example legless here. It's gonna do to do okay. Here. I'm not gonna put values. So we basically have our and are, too, you got. So we're trying to figure out how do we remove this? Um, the way I'm gonna do it is to make a copy of the head. So to make a coffee, I'm basically I'm gonna point to the same place service will be tempted. It's called temp Node Quarter does point to the same thing. So we want to move this over here, the head to the next one, because this is gonna get removed. So we do have cools. Get next. So remove this over here, which is what we want, and we're gonna delete this one right here. So key word will be C plus. Plus will receive the town. So I believe that that should remove this from memory. And as you see now, we have nothing. The front. The first 9. removeFront Coding: so in this video will be coating up. Had to remove the front note of the list. So we'll do you avoid remove front and will define it down here. Avoid first remove front. Um, yes. So we need to check off the list is empty. Also, Every time we got to do that, so do your head people's no pointer. So if it is empty, um, we're just gonna let we're just gonna let whoever know, Basically, that it's an empty list. Eso we're going to say nothing to remove from front. And just before I forget to mention to do that just like the main earlier I had to include Io stream appear and I also have to include using name space standard. Otherwise, I can't do a c out in this class directly. So that's what I did to be able to do this So else. So this is our says are existing in this case. So if we do actually want to remove from an existing list, which is, you know, basically actually doing something, um, we need to We need to actually make a copy of the head. Teoh, delete it correctly. So to do that will do. We'll declare a node pointer called to knowed pointer, and we'll set that equal to the head. So we're just making a copy. And what we're gonna do is we're gonna set the head equal to head. Uh, get next, pointer. So what this is doing is it's moving to the next node in the list because we're gonna be deleting the original head and to actually delete the original head way will be doing delete key word delete Here. Um, what is that? Tim Knowed where? So what is pointing to? So we're depleting the original head right here. Um, and C plus Plus, you have keyword new to create a instance you have keyword delete to delete that instance from memory. If you're familiar with Java, it'll actually like handle that for you, but in C Plus plus, you have to explicitly delete, um, delete to basically get rid of it and memory because there's no garbage collection. Uh, yeah, so I believe that's it for removing the front of the list. 10. removeBack Concept: Okay, so in this video, we're going going over the removed back function. I drew out an example. Three knows to get a started. Um, So the main challenge here to remove this one is if you see there's one note before this that we have to need to change this link, this one. So if we were removed this if we were to only remove this, this would still be pointing to something. So we need to change the value that this is pointing to To do that. What we'll do is we'll make a temp note pointer pointing to the head, okay? And we will navigate by using the next pointers will look through basically. So we're gonna get this to this note. So we want this point over here once we're pointing here, which is in this case is the 2nd 1 but it's always gonna be the note right before the last one. Okay, uh, reason why I chose three, not two, because would be confusing a little bit with the head. Only because we could just access the head, you know, easier. But in general, we need to get to the note right before the last, we would be basically changing. So you do like to no pointer, uh, set next. And we'd actually be setting that old pointer because you want to remove what's on the end . All right, so we're gonna be setting this pointing to nothing. So this is now It's gonna be no, where, which is what we want so far that looks right. Okay. The reason why we made this cause we can't. If we move the head here, we're gonna lose our list. We can't. We will no longer be able to access the first note. That's why we made a copy here. Okay? And the other step is with the tail. We need to really what our tails pointing to. So we'll just delete cartel, mention your this and then we need to reassign r tells. So tell you cools, Tim. This will now or tail now be pointing to the last. And that's basically how you remove the last night of a list 11. removeBack Coding: All right, so in this video will be removing from the back. So this is probably the hardest one. It's definitely doable, though. There's just one. I mean, everyone over in the concept video. But there's one struggle that you have to kind of get to the node before the end to delete to be able to add it. But we'll get into that Will do. Lloyd, move. I just came back again. I will define it down here. So do you list back? Okay. And I know that I'm gonna need a temp note pointer. So I'm just gonna declare right now. Sometimes you don't always know what you need, but I just haven't No. So yeah, so we made a copy here, and we'll do the same check here. So if I had people to know always good practice to see if there's actually a list, have problems later down the road. And then, you know, if it is, we'll just let me let the person know who's using it. Basically nothing. Teoh from notice, I actually, I put the key I put back in there just so I know which one is actually getting called make . So I knew where it's coming from, and then we'll do else in here. That is once again, our existing It was case. Okay, So our existing list case, which is the harder part. So what we want to do cause we want to get to the node before the last one so we can set that next pointer to know first said to do that, this is how you lose their, uh, link loose. So you do a wildly you would do. Uh, what is it to no pointer. So this is generally do you do not equal to no border? This would get you to the very last nude. Um, okay, it's a bad introduction, because you actually we want to get to the note before, but this is generally how you get through the entire list. So to get to the note before that, we have to add We have to get get next pointer. So what this does is it stops the second to last one. Yeah, so it's It's basically one step ahead, and actually, it right through the list, which I forgot to mention, is you basically you do Tim knowed pointer. So you're gonna you're gonna Reese. You're basically change the value of attempted pointer each time to get to move through the list. So do you Tempt pointer, Get so we have a pointer and to keep Iterating, we said it to the next pointer of that nerve. And then we said, It's the next point of the next nude and so forth. So that's how you get through the list. A link list? Um, it's a little different than an array you can't just use, you know, like a four loop and then go through. The index is you have to do it something like this. Okay, so once we do this loop, we should be in the second allows note for attempt, node, pointer, which is what we want. And once we're there, we need to set the next value of it. So we're gonna do Tim knowed pointer. No, reset. Next. So we're gonna set our next value to know winner, because we're trying to Sorry, pointer. It happened seven point. Uh, well, I got all messed up. Okay? Put an arrow there, setting x pointed in no pointer because we want to remove the last one and basically set the one before that, too in all. So we do that and then we're gonna actually delete the original tell. And we're going to reset the tail, not tell tail too. Our temp node pointer. So basically one before, and that's basically it for removing the last note in your link lists. 12. removeBack Revision Coding: Hello, everyone. So I want to make one revision on our removed back. So problem was, I was going one too far. And I was getting Ah, I was not actually setting the second to last note to know I was setting the last note to know which wasn't my desired output. Uh, so to do that, you would just add another, uh, get next pointer right here. So you say, Tim, Node, pointer, get next, pointer, Aero. Getting exporters don't equal to know. That's how you get to the second to last. So, second to last node, this is really the most confusing part that we're gonna cover, I would say, because you're calling this twice. And like for me, I had to actually draw it out, even understand why I called it twice again. So I forgot myself. And then once you do that, you should be able to do the same steps for the remove back 13. Loop Through Linked List Concept: Okay, So I wanted to go over a little bit how to actually look through the link list. I got always stuck myself. I forgot a few things. So when actually going through this Lindquist, this is what would happen if you do. While, uh, let's say no pointer. Not cool to know. So this is what would happen. You did this so you would be here. And if you're here, this is not know. So you would move to this note, and obviously this is not know. So you moved to this? This isn't no pointer. So you go to this new This still doesn't know. So you go here. So, reality, I'm actually going one set more than I need to So I could actually do I could change this to a 10 pointer, Get next when it's not equal to no. Now would actually get me to this without taking this one extra stuff. So that's just the point I want to make. And because we actually need it if we're trying to get to the second last one. So we're trying to get the second last one. We actually need to do you get next, pointer get an X pointer. Not a political no. Do you have to put this twice? It's gonna be ugly. But you're basically putting this era. So we get next is not able to know. And if you did that so he did that. So if you're here, next is not No, this is not know. So you'd move to here, You say next. Nominal. This is not know. So you get to hear you would check nexus not goal. But next next is no. So you would stop here so earlier? We need actually need get next pointer era getting exporter is not able to know. That's how we stop here. So the syntax and the way this is is pretty ugly. But just know the goal is to get to this node in our like this the second to last new so we can remove this one said this link here to know 14. displayList Coding: All right, so in this video will first be covering how to make a display function toe show the values of our link list. To do that. Well, calling will be defining display list function, and we'll be defining it at the bottom here. Another thing to point out. I noticed earlier leave on my remove front. I only had one equal sign here, so make sure you have to compare equality here. I wasn't trying to assign it. Okay, so, yeah, avoid linked list display list. I find it. So just like before. Uh, we need to make a copy of our head so we'll make another pointer here. Attempted quarter. You know, I wonder notice set it equal to our head value. So it's pointing the same spot and then to generate, we're gonna make that similar loop. So this will get us all the way through. Our linguists do while Tim Pointer. It is not equal to know Poinar Some of you might be using, like, an older version of C plus plus, Just know that I think I know I used to use just capital in U. S oil, so I think that would be a sin tax Also eso And now to actually do the iterating we do tempt node Coyner Ukuleles. Tim, No pointing. Get next. Where? So this will I recall that That will just keep moving it from note to note. And if we want to display, we could do a c out right here. Um, you just do tip No Poinar You just do. You just do get I d do it live. Yeah, So that's not gonna look the nicest. So I'm going to include just a little I d, uh, tax here. Just so we know we're looking at some of your i d corn space. These that so this should iterated through our link list and then display each I d within our liquid. 15. Testing Linked List in main() Coding: Okay, so now that we have our display list done, we actually have our class link list completed. Um, we could do a little testing to try it out in our main function. New. So we go over the main dot see PP. So to be able to access this link list class header file, we need to include it. So we'll include. Make sure you use the quotes here to include a custom class. So to be link list out h don't forget the dot each. Okay, so now we can, uh, basically create an instance of our link lists and test it out. So to do that, we'll be using our own type that we define, which is linked list like a pointer. And we'll just name it my list heels. So we basically knew. Willing. That's the constructor right here. Okay, so we know how our list now we can start adding some numbers to it. To do that, you could just do my list. Era do you can add to the front. So we just put a one here, and then it we'll add another one to the front. Why not? Here we go. Add front That's good too. And let's just add one to the back. My lose, uh, three in the okay. And we made our display function, so we contest that out, so it's just my list and display list. Okay, so if you want to try that out, we should be able to run it. Okay, So the way that our display function works is it displays the front of the list first. And the way this ad works is well, basically, it's from top to bottom. So we added one to the front. So what happened was one was in the front. Yeah, one was in the front, and then we added to to the front, so it actually went before that. So this is the new front. We got a three to the back. So this is actually the correct order right here. Um, let's try a removed. Let's try removing. Remember, for for these for this tutorial, we're only adding and removing from the front in the back because the structures of Q and stack Onley utilize the front in the back. We don't have to actually go in the middle and take anything out. So let's try removing the front and the back. Why not? So we have this and then do you see out? Uh, say removal Testing, Okay. And then we can just do my list, Do one at a time just to make sure. Sorry, not that my list. Uh, let's remove from the front first, and then we can just do my list, display a list that right there. Okay. And we should be able to run that. Okay, so this is earlier. I just left it. So we're trying to remove from the front, and we took the two off, which is exactly what we needed. 16. Class Stack Concept: Okay, So in this video, I'm going to go over the structure of class stack. So, like our length lists usar node, our staff is actually use our linguist. So in general, Stack looks kind of something like this. So these kind of things would just be note. So for example, 3 to 1 zero. Yeah, this would be pointing to this. He pointed to this. This would be pointing to this. This is pointing to know where. So it's basically the link list. It's just representative. I'm just representing it vertically. That's usually the way it shows. So, yeah, that's our stack. Um, so what? The stack, you basically want to you always add to the top, remove from the top and we usually call that pushing pop. So when we when we push, I had something to this top of the stack, I say for this would just go like this. So that would be our top for here. We pop, you simply removed the top. And that's the main idea for a stack. Just basically, we always access that top by removing at 17. Class Stack Intro Coding: So in this video, um, we're gonna be implementing our class stack class just leaving off from earlier. So I just want to get rid of this testing the testing calls I did here in the main so we can remove this, and we're not gonna be accessing link list directly from the main. So you so my main basically looks like this again. We still have our note in our link list implemented. So now we're gonna create another header file. I called Stack. So we're gonna do new item header file. It's just gonna be stacked out each dot h and and I want here. Okay. And same thing is, before we have to do if in depth for the header file, we'll just do stack on that score. Age do fine. It was back score H and they won't put our class in here. Says, uh, good practice for learning how to build classes. Keep doing the same thing. Here we go. Class stack, I'll keep it capitalized. Okay, so we'll have private and the only thing we need, which we're gonna dio if you wait to do it. But basically, I'm gonna have a linked We're gonna have a link list, which is my list. So, a pointer to link list, That's all we're gonna have in the variable section for public. I think we didn't most the hard work, so we'll just do the constructor in the linguist class earlier. So you stack and we'll find it down here, so we'll just do sorry. No. Are going to do that. Stack stack. Okay. And yeah. So we're just gonna do my list. People's new late. Exactly what I did in the main earlier. So you kind of see the theme. What I was doing in the main is what I'm actually doing in this class. It's kind of they're all connected. So when we Stan, she ate the stack. We're making new linguists behind the scenes. The users won't actually see the link list. They'll just know that they're using a stack. They don't know how it's implemented. 18. Class Stack Continued Coding: Okay, So in this video, I'm going to try to cover three functions Will be pushed cop on display stack. Okay. So first will define push Do you avoid and to push we actually need. I integer i d just like earlier. Darling, Close class. We'll find it down here. So you avoid stack put and I need and you'll see this is really just abstracting the link lists were using in history. In a way. Yeah. So we have my list here. So do you all we're doing to push do my list, my list, and then we will do on a It was at front. Yeah, at front and then put that idea in the front. So really, we're just adding to the front of our link list because that's what pushes adding to the front and then pop avoid. I thought I don't need Teoh passing anything. Just avoid. I thought to do this. So pop is always gonna be from the front of the list also. So be my list and then removed for so yeah, That's basically how the stack it works. We're adding to the front, were removed from the front, and I just do display list. We're actually gonna use our display less from the A linguist. Same same idea would be void. Uh, display a list, and we're really just abstracting at one layer. So do you avoid stack display a list to do that? We'll just do my list. This So this is from the link list. This is from the stack. I just named in the same thing, but we're actually accessing the one from the liquid. Yeah, that's really it for our stat class. 19. Class Queue Concept: this video just going to show you the concept of a cube that we're gonna be implementing in Glass Cube. Um, it's basically a linguist. Same thing we got earlier. But the main concept of the queue is there. We always service the person who got there first, and we add to the back the list so they will have functions called in Cuba, which will basically add to the back right here. And we'll have details which will remove this one from the front. So it's basically like a line in real life waiting at the grocery store or whatever. Um, if you got there first, you know, you're expected to get service first. Um, yes, just like the staff were using the link list, and we're just gonna be accessing a certain way. 20. Class Queue Coding: So we just made our stat class. I'm actually gonna make our que class, too. And then we'll test both the stack and queue together in the mean so to make the Q class. Once again, we're gonna add a header file. You item here, and it's gonna be called que dot Each this remove this, I will do that. And, uh, way sport, do they end up with your class? Well, okay, so it's very similar to stack. It's just the way the functions that we call from the link list is gonna be a little bit different. Private will do. Pulling this my list and then public, we will have our constructor. I wanted name this capital to keep it consists. So to we'll find that so do okay. And this is where we, uh San shade our list. So my Yeah, my My list kills new waas instructor making that link list. And then so for Q, we're gonna have in Q and D Q instead of pushing pop, so avoid Sorry. I need to do and will define that down here. So, boy, Okay. And to do that, we're just gonna call our linguist. So do my a list and, uh, in Q for basically gonna add to the back because that's the way. Thank you. Works. You're always adding to the back the line. You don't go to the grocery store and go straight to the front. You're not supposed to. Sure you'd like to. So yeah. So you gonna add to the back God, that you gotta put All right. Okay. That's are in queue. Sure, I guess. Rdq avoid. So do void. And then So when we're d queuing, we're going to remove from the front. So do my list move, and that's really it. I forgot a very important thing. So I didn't My stack and I wanted it was over. So my stack Oh, I did it in both. Okay. Says a quick revision. So for both of these, you need to include your link west. Or you can access it, of course. So can include link list in this one. We should be good and same thing for our cue language. If you don't include it, you can't even do this. Okay, so that should be it for are up. I want to add a display functional so you can do that right now. Avoid display, and we'll find that down here. So avoid display a list simply enough. We just do my list display with which is from the link list, not from Thank you. Okay. That should be yet for link lists and our staff. 21. Testing Stack/Queue in main() Coding: Okay. Hello, everyone. So in this video will be going over how to actually use our stack and queue in our main. The first thing is, you need to include both of them. So we'll include, uh, stack, not a church. And then we'll also include que Okay, so we got both of those, and we'll just declare a stack and a Q. So your stack my stack, I could do you, my dear. Yeah, if you want to test these out, uh, basically, do this. You could do my stack dots, push and say we Let's just keep the order. Simple issues a one. And we could do my stack. I just felt right. Sh to three numbers in my three. Okay, so we got three numbers in there, and if you want to display it, you can use our display function. That and I just want to make it clear, because we're gonna be testing here on the stack. We'll just put us see out here. I would say stack testing. Okay, So our stack testing and then we'll make another one for you. Testing which were not doing yet. Okay. See what we got here. Okay, so our stack testing, you see, So the front of the list is gonna be appear or the top. However, you won't refer to it, which is stack your called the top. So first we put in a one, went to the bottom, then we put it to On top of that, we put it three on that. So that looks correct. We can let's add to the Q first so we could do the same thing for the queue. So to do that, I just do my cue. God, thank you. No one. And I'll just copy this and I'll put the same orders before run this. It's when you guys to see the difference. I do. How? I didn't display it. Okay, that makes him so. We need to display it, of course display. Okay, now let's compare the two. Okay, So I said, This is correct. You notice the orders different. It's because the structures are different. Um, the way the Q works is, our one was there first, and it stays at the top of the line or the front of the line. Then the two and behind it on the three went behind it. Okay, so This is the correct ordering for Stack and cute. Let's try. It's try our pop in our D. Q. So if we want, we could do this. So my stack God. Uh, so it's always gonna pop from the top so we can try that out. Let's try it out first. No, I didn't display it. So you're not gonna see anything. So it's displayed again. My stack God display. Now let's see, actually see something, and I should have made a break. So let's just do this. I don't know. Pop popping. Whatever. Okay. Least that should look a little bit better. Not the best. But as you can see, we popped. We pop the top. And for the future, I'll make a M line right here. Okay, so our pop looks good. Let's try de que So do similar things. So I'm gonna do some copying here. Okay, So this would be call can que thank you. So in curing all right, that do pop. But anyway, so we'll call it right here. Die. Thank you. No, thank you. I'm antique. You Sorry. Could you? That should be deep. Here. Thank you. Yeah. Okay. Let's try that. Okay. Okay, So original Stack. We had 3 to 1. You popped. We have to one. That's correct. Your top. You testing their 123 We did cute. Took it out from the front. No, Sorry. We took it out for the back. Oh, I see. See what happens when you copy. All right, guys, don't do that. I was wondering why that didn't look right. Okay, to be my Okay. Now try it again. Because we're just looking the stack again, and that's not correct. Can't justify that one. So, yes, we have the Q 123 and then we D Q. So we remove the guy who got there first, so that's correct. 22. Project Scope: Hello, everyone. So, for the project for this class, I want you to implement basically everything that I have here from Maine Node link list, stack and queue. But on top of that, I'd like you to create the function in in your link list class that basically, uh, peaks the front of the list. So it should display the first note in the list. And then in the stack, you should be able to make a function that says peak top, and then the queue. You should make a function that says peak front. So they're basically the same. It's just different wording. And yeah, that's basically it. If you have any questions, feel free to contact me. Do the best I can to get back to you on. Uh, yeah. Good luck.