what's up guys this is Teddy welcome to my YouTube channel this video we're going to be talking about linked list and linked list is something that Junior developers need to know linked list is something college students need to know linked list is something every programmer needs to have an understanding of and it's sort of nuanced you you actually don't see link list like hardly at all in um modern software development like you you never see people use a linked list but the linked list is like the ancestor it's the dinosaur of the data stru we still study dinosaurs for a specific reason to understand where we came from I'm being corny but you get what I'm saying we we go sometimes we go down into the bedro of programming so that we can understand things and understanding how a link list works is going to be just absolutely crucial to your understanding of how even arrays work like how everything works because you have a reference and you can compare them and I like to call a linked list this is like a little saying that I like to say it's like an it's an array that's been objectified and nobody likes to be objectified but a linked list is an array that has almost been objectified and I'm going to talk more about that and what that means but just kind of give you a cool little play on words to just kind of think about so bad things about arrays they're fixed technically you can still uh make arrays like you can f you can you know roll your own array and you can make your own array that is you know dynamic and there's a list which is technically array which is dynamic but a traditional array where you're initializing and you're newing up isn't um it's fixed it's you can't actually do anything with it and you can't insert into the middle without it being very expensive you can insert and we talked about AR array assertions and how to actually do them but as you saw before inserting into an array is an o n operation and that is what we don't that's the middle one remember that's like the Acura or that's the that's like the Honda when we really want the Ferrari the Ferrari would be constant the you know an o n insertion and inserting into an array is um it's not ideal it's not the worst but it's not ideal so what we came up with is we came up with a linked list and the good thing about a linked list is that you can insert anywhere in to it and it's Dynamic so you can just you know wherever you you at the very beginning and it we're going to be inserting at the very start um it's a constant operation and that's kind of the reason why we even use Link list and it's Dynamic it's not fixed and it uh it's almost like a balloon like it however much air you put into a balloon it expands and a linkless is like that but with data instead of air there's data inside of the linkless balloon not so much a the best analogy but here's a better analogy an array is a park bench and I talked about this a little bit beforehand an array data is being stored in an array in contiguous places in memory when people sit on a park bench like you have to sit in one spot and then the next person sits in the next spot and the next person sits in the next spot but a linked list is almost like people are holding hands and they can kind of go anywhere in memory and they can uh they can expand and people can you know everybody's holding hands and everything is great and you know it's like that picture we're all on the beach and we can go anywhere but a park bench is like think about how those if those people were to be connected somehow and they were to sit on the Park Bench they couldn't just go wherever they wanted to they they would have to be sitting in specific places on the Park Bench but a link list is kind of like you've got places all around in memory and everything's kind of Flo floating around but it's logically tied together and another um analogy is like a balloon like some people talk about a balloon and when you and we're going to go ahead flip over to uh I'm going to you know kind of get a little bit more detail so this right here is a link list and I just went and bought a wack tablet but it's I'm still not able to use it well so I'm just still just going to use my mouse but this right here is what lock logically ties things together and this right here is called a reference so you are referencing and it's important to know the parts of um a link list if I think if you can just kind of get like the parts down and if you want to write this down that would be great so this right here and I'm actually I'm going to see if I can't use this wack tablet if I can bear with me for a second we're going we're going into the main frame okay so this is a node so these little blocks right here these are called nodes and nodes are what objectifies arrays like these are actual objects these aren't stored in like an array memory these are nodes that you actually create it's almost like you're fashioning your own little data storage buckets and these reference points are what ties these together remember I gave the analogy of the train and I gave the analogy of people holding hands and that's what allows you to be able to store and instead of having an array where things have to be next to each other this reference point in this node in this little container or bucket of data is what gives you the ability to hold data and the uh reference is going to be what allows data to be stored all around in memory and what object objectifies your data structure or kind of like an array but all the instead of like I said instead of being stored side by side it's all throughout memory and you also need to know that this is very crucial because nobody ever explained this to me and you it's one of those like I said it's like one of those things nobody ever explains and then you figure it out like a year later and you're like well why didn't anybody tell me that the very last part is going to always be null if you don't have a null right here that's going to cause problems because one of the like foundational Parts in being able to actually find stuff in a link list is for this part to be null so at the very end just remember at the Caboose of the train there's always there always has to be a null if there's not a null I don't even think it's like a real length list so the null is the Caboose it's like the Caboose of the train and then the head every link list is going to have a head at head is very important because you always have to know where the start of the train is if you don't know where the start of the train like what if we just got we just lived in an alternate reality and there was no head and you know maybe we just said this was the head or we just didn't have that you would never be able to actually keep track of it it's almost like the length or it's almost like a a pointer to help you logically keep track of where all of this is actually going on and right now let let's actually just let's start small and we're going to kind of work our way up let's go in here and I'm going to boot up visual studio and let's actually create let's just create a node like I think that that's actually probably the best part to actually start is just create creating a node let's not worry so much about the link list and I'm actually I was actually making a video on in place array operations so um don't mind that we're going to go in here then we're going to go we're going to call this link list then we're going to create our node we're going to create a node class and the node like I said is the is the the squares it's the blocks it's the containers for your data and the node always has two parts you have the actual data and then you have the thing that points to the next data or the arrow so we're going to go here and we're going to declare our two parts remember it always has the two parts it has the actual place where you the bucket where you actually keep the data and we're just going to store integers in here just so people don't get confus you could go in here you could store strings you could store whatever you wanted to it's your data structure you could store other you could store link list inside of Link list instead of Link list I don't know why you would do that but it's possible and then we're going to have a self- referencing I don't know the actual term for this but I think it's called like a self- referencing property and you you don't really see this very often unless you're actually working with link list it is kind of like a weird um property I guess you would call it but just it's you're going to you're going to see it in link you're going to see it in link list so just all right so and we're going to go down here and we're going to go console. rightline and this part we don't actually this isn't crucial down here we're just going to have this so that this is going to benefit us later on down the road what's really important is this part right here and let me see here I've actually got a I've actually got a node we're gonna we're gon to go even deeper into nodes so we've got our data we've got four we've got our next it's going to be the same exact thing if you look data is where we're going to store the actual data the next the node is going to be the arrow and it's going to point to the next bucket and it's going to point to the next bucket and if you don't understand exactly what that means let's just actually go in here and let's create let's I'm going to show you exactly what this means so we're going to go if you want we can just call this linked list or uh yeah I'm just going to put a title up here so we're going to go linked list then we're going to go here and we're going to initialize this node so we're going to go node and we're going to call this node a we're going to call this new node and we're going to initialize this so we're going to go here boom and we're just gonna we're going to we're not going to tie them together yet we're just going to go in here and we're going to we're going to just create a bunch of nodes and the intellisense is working awesome so node C is equal to new new node node we'll do one more so go node D is equal to new node so then we got that and now let's put some data in here and we could you could put any type of data in here it doesn't need to be any um you could literally put anything but in our case we put we made it so that our nodes Can Only Hold integers but feel free to go back and change it and put a string in there if you want to but I'm just for right now I'm just going to do this so I'm going to go data and then I'm go four and I'm going to change up these number I'm going to make these numbers random so it doesn't like have look too similar to the actual reference so let's I'm going to go here and I'm going call this C I'm want to put some data in here and we're going to go 9 888 then down here we're going to go node D and we're going to go d D is equal to data is equal to 222 and basically what I've done is I've gone in here and put data inside of here just just like I did just logically representing that that's what just what I did now we need to go into here and we need to go into our next and make the arrow this is going to be cool this is actually very elegant like sometimes I a lot of times in programming you just look at stuff and you're just like man this is so elegant I can't believe somebody actually came up with this and then we're going to point it to the then we point it to the next object and that's why I say a linked list is like an objectified an array it's uh it's kind of like an array it's just they're objects and now they're being tied together because you couldn't do this because an array is stored in a different place in memory so we're going to go down here we're going to go B is equal to next is equal to node C wait a minute no that's yeah that's right okay so we're going to go node D is equal to next and or node C or actually we need to do node C and then we're going to go node D and they are all logically tied together and this is actually what's happening inside of a linked list whenever you actually create like the actual data structure for a linked list we haven't we've just created the node but whenever you create a linked list this is actually kind of like what's going on and I'll show you what this looks like in memory so we're going to go clear we're going to go clear all then we're going to go here and we're just going to look at our we're going to add watches to all of our noes so we're going to go here we're going to go add watch and we just watch okay so it's created an object if you notice this is whenever you see the curly braces this means you've created an object in memory and whenever we looked at the last whenever you have an array an array looks totally different it's an array in memory it's not it's not an object so we're going to go here look down here and then it's hold this data is holding and then it's going to go down to the next one and it's the ex it's literally the exact same thing and we just have a nice little bucket that holds our data and then it points to the next one and now it's going to go through and it's going to hook them all up it's going to form it's going to form that relationship it's going to make that Arrow it's going to hook them all up now we need to actually create the data structure so that we can iterate through this like this is a cool idea but just like every other type of uh like we need to actually create an abstract data structure so we can actually be able to do the representation and we can act on this data and we can have like a logical place to store this remember how I was talking about the abstract data type in the Pokemon we could just have I mean in a crazy Universe we could just have this laying around and we could just have all this out here but what really makes sense is that we put this inside of uh an abstract data type so that we can actually do we can just have a logical place to keep our tool tools remember like my dad's toolbox if I misplaced my dad's tools he would yell at me but here it's the same thing if we just have all our tools strewn about it doesn't even make sense because everything's so disorganized so we're going to go in here we're going to go linked list and we're just going to create this linked list okay so now let's actually go back and we're going to talk about the actual operations and there's so many operations that you could do on a link list it could make your head spin and you could go through every single thing but probably the best place to start for a beginner is to insert to delete and to iterate and if you can just kind of logically if you could just kind of get the visual picture and understand especially what's going on with the head and with the null like keep keep your eye on the head keep your sounds kind of weird keep your eye on the null and that's going to uh make a big differ especially the head so what we want to do pretty simple simple we're going to go in here we're going to let me see here we're going to create a new shape and we want to insert at the beginning we're inserting at the beginning we're not doing an insert inside maybe one day we'll do an insert ins side but let's not get carried away so assign data to the next field okay so we create a new node we assign data let me see and this just kind of logically makes sense so then we'll say this one's going to be seven like it doesn't even doesn't even matter what you put it in here then we're going to assign the head and then we're and then it's going to point to the next one so it's then it's going to assign the new field and that's it and logically that just kind of makes sense so assign data to the next field um make sure that you have the the data that you want and then assign the head move the head over and that's pretty much it and the great thing about this is that's 01 that's like the cat that's the Cadillac that's the Ferrari that's what we want okay so let's go back out here and we will make our insert and we'll also make a couple helper methods as well too so we're going to go prop we're going to go node and you could call this uh head you could call this first I'm going to call this first I think it just logically makes more sense and then we're going to go in here um I don't even think we don't need a Constructor all right and then we need to make a couple Let's do let's do the let's go in here and let's not get carried away I was going to make a couple helper methods but let's let's just stick with what we're doing so insert first you could call it insert head you call it whatever you want then okay create the node what we want to do is create the node so we go in here we're going to go new node is equal to the node because we can't if we don't have a new node like how are we actually going to be able to put data in it so put the data in the node put the data in the node very it's almost just like if you were like if you think about it like how would you actually do it and I know that sounds kind of cheesy and like a what a lot of people say that sometimes you just got to think about it but it's it's actually kind of true so okay so we put the data in the node now we need to make the old node the next so put the old node in next so we're going to go new node. next so we're going to assign the new node as the next node as the first so we're just going to move over that we're going to move over that reference and then make the first or make the head the new node we're GNA go go down here we go first is equal to new node very simple and best part of all this is 01 operation so it's uh very fast all right so let me see here where am I at got to get my little visual thing out here so okay now let's talk about delete so with delete you make a a temporary variable you assign the new head and then you pretty much just blow this away so if we were going to go here and we were actually just going to delete this head basically all that's going to happen is it's just going to assign a new head and you would think that we would clean this up and that we would not leave this here but a lot of time and like 99% of time you're just going to leave this here like I don't think especially in an interview situation I don't think it really makes sense for you to like actually go and delete this what you really want to do and like what we're actually just kind of like what we're doing is we're really just assign that a new head to it and this is just going to kind of exist logically let me see this is still going to exist it's just going to have a different head and it's going to be like it's logically deleted similar to the array assertions that we did in the last array so here we're going to go down here we're going to go public go node delete first then go down here remember assign the temporary Avail temporary variable so we go node we going to go temp we're going go first so the the new temporary V variable is going to be the first one assign the new head and then first is going to equal first.
next so now the um next the next head or the next um node is going to be the head and then we're going to return the temp very very simple and possible n null reference here because in C because the node can be null it's it's it gives that error let me see then we can go down here we go into the node and we should be good to do all right and I'm still do reference a PO possible null reference okay um ever since net 6 happened there's all these null reference errors and to be honest with you I really don't understand them but you can't understand everything so we just kind of got to you know move on I swear I don't I I wish I knew if you know leave a comment down below okay so we're going to go public now probably one of the most important is we need to learn how to iterate iterating is pretty simple you're going to assign you're going to assign the current node because you don't want to use the actual node because you don't want to have the new node as you are iterating through it and you're changing that node you want to assign a new one and then you're going to use that new note or that new reference that you have and this may sound confusing to make a wild Loop and then you're just going to basically check if everything's null so sounds a little confusing but I'll show you what it show you here so we're going to go display list and we're going to go here and we're just going to put like a nice little console right line and we're going to say iterate iterating through list just kind of let us know what's going on so go down here go right here and we're going to go node current is equal to First we're going to assign it because because we don't want to iterate through the first we don't want to actually check the first because we don't want that value to be manipulated then we're going to go here we're going to go is current not equal to null and this is why this is an this is why this is important because we want to check if it's null and once we get to the null that's what's going to trigger the while loot to stop otherwise it will keep going so just be cognizant be aware of that otherwise um you could run into issues so we got current and this is why I created this display node so if if you want to go back in here if you don't know what's going on um this is actually on the Node and the node is going to be passed within a console right line and this is actually why I made this part right here so that we can uh just display this very quickly and not have to and it will actually display it with inside so most important part this right here whenever you see this going on this means that this is iterating or this is actually how you iterate through a nose so whenever you see current. nextt or see a while loop with a current. nextt that is going to be um that's go that's going to mean you're you're iterating within or if you're doing it within some type of for Loop or something and just for uh if you're feeling a little um I don't know I I don't know what the word would be if you're feeling a little adventurous we're going to insert last so we're going to go int data then we're going to go down here then we're going to go node current we're going to assign a current node and you can see how you actually iterate and you can actually insert into the last part and it's kind of like a blend of an insertion to the front and also an iteration and it's going to be I think it's good because it shows how you can actually do both how you can actually combine these so we're going to go current.
next is equal not equal to null we're going go down here we're going to do our iteration then once we get to the very this then once we get to the end what we're going to do is we're going to assign a new node then we're going to populate that node with data so we go in here so node. dat is equal to the data that we want and then current. next is equal to new node let me see and I think that that is right okay so now we've actually built the data structure what we're going to do is we're going to go into our program.
cs file and we're going to actually start using this thing so let me see okay so let's go ahead let's get let's get rid of all this and we're going to go link list and we're going to go just going to call this link list is equal to New Link list and linked we're going to show you guys how to insert so linked list and we will iterate through each and every one piece by piece so in this one we're just going to startt to one we're going to go link list is equal to two we're going to start to two in there link list is equal to three so we're just going to go 1 two three and we'll do a four for just for good measures then we will do the delete me see so we're going to go ahead then we're going to delete them so link list dot delete first linked list.
