How to Create a Linked List C++ Introduction to Linked Lists

hey everybody this is Paul this is an introductory example to using linked lists and I'll be using C++ language to demonstrate how to build a linked list so basically the basic concept of a linked list is we have a bunch of nodes and they're connected to each other by using these pointers and you can place values inside each of these nodes and we can kind of just create a list of values or a list of data members and so for example we could fill this one with the number 1 2 3 4 and so on we could just kind of create a big list here and so that's the basic concept of a linked list so the first thing we want to cover is how do we make one of these nodes well in C++ we can simply type in struct and then we'll just name our struct node and then we'll put our opening curly brace and then inside the struct just to make it simple I'm just going to have an int and we're going to name that data and then I'm going to have another data member in here and it's actually going to be a node pointer and we're just going to call that next and then we're going to put our end curly brace and then our semicolon to finish the struct so what I just made here is I created one of these nodes and if you want to think about it like this you've got basically have this node struct here so we'll just put a node here and we'll split it in half top half will be this int data part so we can hold our data right here we can hold an integer value and we can store it in this part of our node and then the node star next is it creates a node pointer named next so basically the other part of our node contains a pointer and it is able to point to another node so that's what our struct looks like so now let's just go ahead and just write some code and see how this works so basically what we're going to want to do is we're going to want to create a few more node pointers so I'm just going to do node star N and then we'll create another one node star T for temporary and we're going to do node star H for head or the beginning of the list so basically what we are doing when we heard when we type in these things into our program is we're basically just creating these little node pointers we'll just call that one N and there they just have the ability to point to another node we'll just call this one T and this one we'll call H so by typing these three lines of code in right here we're basically just creating these little pointers and they can point to another node so we'll just go ahead and erase this now and I think we've got this down now so we'll just kind of continue so now we've created our three different pointers and so after we've created our pointer is what we want to do is we're just going to say that n is equal to a new node and so what this does is it doesn't make a new node but rather what it does is it has n point to a newly created node so now we basically have our data part right here and we have our next part right here which is just another pointer just like n is so then if we want it to fill up our node with some data we could just write N and then a little arrow here and then we're accessing the data member of this node and we could just set its value equal to 1 and so then that places a 1 in the data part of our node so the next thing we probably want to do is we're going to want to assign a value the head and for the temporary pointer so we're just going to say that T is our temporary we're just going to set that equal to N and then we're also going to set our head equal to n for now and so by typing in these two things basically what we're doing is we're telling our our head and temporary pointers to point to the same node that n is pointing to so they're not actually going to point to n they're actually going to point to the same thing that n is pointing to so that's T and that's H so H our head is basically going to stay in this position the whole time and the temporary pointer is just kind of going to follow n as it kind of goes down and builds the linked list so a head is important to leave at the beginning so that we can later on come to the starting point of our list and access all the data so this just kind of stays in place now so then the next thing we probably want to do is start building our list so to do that we could type in N equals new node again so by typing in N equals new node basically what we're doing is we're changing what our end pointer is pointing to and it's pointing to a newly created node so now n is over here pointing to a new node so now at this point the list isn't linked yet we simply just have n pointing to a new node and that node has an X pointer and it has some data that it can fill you can fill in some data here and so what we can do is we can say n data equals 2 and by placing this line of code into our program it puts a 2 in that box right there so we still haven't linked this together yet so what we can do is we can use our temporary pointer we leave that one step behind and we can use our temporary pointer to extend this next arrow to the next node and so the way we would do that is we would simply write T next is equal to n so basically it's saying okay access the next part of the node that T is pointing to so look at this part right here says okay look at the the node that T's pointing to and then access the next data member inside that node and then make it point to whatever n is pointing to so it basically just extends this arrow and says okay now I'm pointing to this node over here and once we've done that we can simply advance T so now we can say that T is equal to T next we could have said T is equal to n that should work too so basically now T is going to look for T next well T next is what this guy is pointing to and so basically it just moves our T over here now and now we have TN n pointing to the same node so I'm just going to erase this right here and so now we're at the point to where we're just going to put let's just put another third link here to make the point sink in and so what we're going to do is we're going to say that once again we're going to say N is equal to a new node and by doing that we're basically creating a new node and we can access it by using the end pointer so now N is over here pointing to some new node and we've got a next part of that node and it's just kind of pointing somewhere into the program and so basically what we want to do is we want to fill it with some data and then connect this node to the new node so what we're going to do once again is we're going to type in N data in arrow data and this time we could set it equal to three and that would put the value three in the data section the N is pointing to so then the next thing we'd want to do is we'd want to connect this node to the new node and so we could do that by just saying T next T arrow next is equal to n so by typing this line of code in we would basically be telling where the next part of this node the node that T is pointing to where the next part needs to point to so we're just going to make it point to N or not to n but to the node that n is pointing to just by typing in this line of code here and so then we could just kind of continue this process once again if we wanted to we could just do N equals new node one more time so by typing in N equals new node what it would do is it would just make our n pointer point just to some new node over here now and we could do we would want to advance T now we could do that by just saying T equals T next so it's saying basically make T point to whatever T's next element is currently pointing to so that moves T to this node then we could say n data equals four that would place for and here and we could just say in this case if we wanted to we could just say T next equals n so T next equals n would basically make the next part of this node that T is pointing to point to the node that n is pointing to and if we wanted to finish our list here what we could do is we could just say n-next is equal to no and that way we know that it terminates and so that just kind of sends this guy off to nothing so he doesn't this guy's next doesn't point to anything so basically we just created a list and we're keeping track of it by this head pointer here so we can always go back and set our values equal to the to H because H is keeping track of the beginning of our list and now we have a list that's connected by these nodes that we can access through the head and we can we have the numbers 1 2 3 4 contained in them and then we end it with the last nodes next pointing to a null so it's not really pointing anything to anything here it's not pointing to another node it just ends right there so anyway hopefully that helps you guys understand linked lists and how to implement them in C++ let me know what you think about this video in the comments thank you guys for watching have a great day and if you like the video don't forget to subscribe

Channel: Paul Programming

Views: 786,242

Rating: 4.9351387 out of 5

Keywords: What, Is, Linked, List, Tutorial, Help, How, To, Code, Node, Paulprogramming, how to make a linked list, how does a linked list work, how to program a linked list, how to code a linked list, linked list help, pointer, node pointer, create, how to create a linked list, c++, make

Id: o5wJkJJpKtM

Length: 12min 24sec (744 seconds)

Published: Wed Dec 12 2012