Linked List Data Structure | JavaScript

[Music] this video is sponsored by dev Mountain if you're interested in learning web development iOS or UX design dev Mountain is a 12-week design and development boot camp intended to get you a full-time position in the industry to learn more visit dev mountain comm or click the link in the description below hey what's going on guys so I've recently had quite a few requests to do some videos on things like algorithms and data structures and coding challenges and stuff like that deeper programming principles rather than the standard you know practical projects that we build and crash courses so I want to I want to get into that and you guys can let me know what you think about that idea so in this video I want to take a look at a specific data structure called a linked list and linked lists you know you can you can create with any language we're gonna be using javascript we're gonna create a linked list class so that we can add some methods to read from it add to it remove from it and so on now Before we jump in I just want to kind of explain what a linked list is for those of you that don't know what it is or maybe just you know I've heard it before but don't really understand what it is so basically it's a linear data structure and I have down here an image of what a linked list looks like I guess physically and this this diagram here really helps me out helped me out to real to understand how it works now and I'm gonna keep this open throughout the whole project or throughout the whole tutorial so it's a linear data structure it's an ordered collection of data but unlike something like an array the elements are the nodes in a linked list they're not stored in sequential memory locations instead the elements are linked together using a pointer okay so basically we have here different nodes or different elements within the linked list and the first node is called the head and basically the head or I should say each node has two things it has the actual data in this case we're just using numbers and then it has a pointer or reference to the next element in the linked list okay so you can see that this one has 104 data and then it has a reference to the next element which has 200 as its data then it has a reference to this one this one has a reference to this one and then this last element or node in the linked list is known as the tail and the tail is gonna have a reference to null okay so that's how you know that it's the end of the list so they're they're quite literally linked together and what's going to happen is we'll have a class and the only property and our linked list class is going to be the head because everything stems from there all right so I mean if you want to read more about it and look deeper into it there's some great information on the internet articles and stuff like that but we're just gonna create like I said a class a couple classes we're actually going to have a class for a specific node and then have a linked list class but before I do that let's just do a very very simple example so if I say we have a node and it has the data of let's say 100 and then we have node 2 and let's say that has data of 200 so these are two completely separate nodes right and we're using JavaScript so obviously these are these are just object literals but if we want to link no - as if we want to add a reference - no - from node 1 we could say n1 dot and add a next property and set that to n2 okay so if I go over here and I run node index ok of course you have to have no js' installed if you're gonna follow along upseting console.log anything let's console.log n1 and you can see that we have data 100 which is our node 1 and then we have a next property which points to the next node which has the data of 200 so that's kind of a very very minimalistic bare-bones example so let's start to create this we're gonna have a class of node and this is going to represent each individual node when we want to create one of these nodes we'll go ahead and in Stan she ate this class and this is just gonna have a constructor and each node will take in two things it's gonna take in the data and then the pointer which will call next and this is going to be set to null by default because remember the last one is a references null all right and then here we're just gonna take the data that's passed in and set it to the data property like that and same with the next okay and I'm assuming that you have some some knowledge of about classes and object oriented programming so that's it for the node class and we can actually construct a node if we go and 1 equals new node and pass in 100 and if we console.log and 1 is a node index you'll see that we get a node object with the data 100 and next is null so basically we just have this right here it's just one single node so let's now create a class called linked list so linked list let's have a constructor and the only we're gonna have two properties here we're gonna have the head and that's gonna be set to null by default which means that the list is empty if there's no head if there's no first element or first node then and obviously the list is empty and then let's keep track of the size of the list so obviously that's zero by default all right now the different methods that I want to create first one is gonna be to insert the first node then I want to insert the last node I want to insert at an index so basically anywhere in between I want to be able to get get from or else say get that index so basically if I want to get you know this one right here this would be index 2 it's 0 1 2 just like an array and we also want to be able to remove at index and we want to be able to clear the list and we want to be able to print the list data all right so let's start off by inserting the first node okay and and this pertains to you know it doesn't matter how many nodes we have in the list we want to be able to insert the head basically so this is gonna be a pretty simple method I'm gonna say insert first it's gonna take in some data and then all we have to do is set the head so say this dot head equals new node so we're just instantiating a node object passing in the data and then the next value is going to be this dot head so the reason we're putting this in here is if we want to insert the first one here if there's already something in the head then we want to push that to the next because remember when we when we pass the second value in it's this whatever next is and if this dot head is null meaning the ax list is empty then obviously this will just be the first and only node in the list okay now I'm gonna skip down to the to the print because I want to be able to show the actual data well I guess we could just console.log it for now so let's do a Const we'll just call this ll for linked list and we'll say new linked list and then let's do ll dot insert first and let's insert 100 okay and then we'll just do a console log here of the entire linked list so if we run that you can see that we get the head value is node with it's a node with the data 100 next is null because it's the only one so just picture just this right here that's what we have if we want to run this again with 200 and run node index notice that now 200 is the first one 200 has been inserted first so now if you look at this diagram 200 is here 100 was pushed over okay it was pushed over because we set next or yeah we set this dot head to the next value which pushed it over all right so let's do a print of the list so for this let's say print list now we could print out the entire node but I just want to print the data so let's call this print list data okay and what I'm gonna do is just set a variable of current to represent the current node and it's gonna start with this dot head and then what we want to do is loop through all the nodes so we can do while current and then here let's just do a console log of current dot data because I just want the data property alright and then we need to basically move along through all the nodes so what we can do is set current equal to then whatever the next value is okay so we kind of loop through it and we're just outputting each one each piece of data so let's save that and let's just add another one here of 300 and let's see what this looks like so if we run this oops I don't want to do console.log I want to do ll dots print list data and let's run that we get 300 200 100 so basically the reason 300 is first because that's the last insert first that we called all right now you might not want to insert first you might want to insert last so let's take care of that next so this is going to be kind of this is going to be a little more difficult than what we did here so let's say insert last and by the way there's a million ways to do this stuff this is just to kind of get the gears turning in your head if you want to change things around or you want to add new methods afterwards that's that's good that's good exercise for problem solving and we'll just logic so let's say insert last pass in our data and let's construct a new node so we'll pass in data and I'm just going to initialize here current and first we want to take care of the edge case where it's empty if there's nothing here in that case we just need to add the head right because it's going to be the first and last so let's say if empty then make make it the head so say if and the way we can check is if it's empty is we can say if not this dot head or if this dot head equals and all you could do that as well then we'll say this dot head is equal to the node okay else so basically if there's already a head then we need to basically kind of do what we did here and loop through so I'm gonna set currents equal to this dot head because we want to start at the beginning and then let's do while and we want to make sure that there's a next value so we want to say while current dot next and down here let's set current equal to current dot next so so this will allow us to kind of traverse through the list and then under the while loop we're gonna go ahead and add the node to the end by just saying current dot next equals node and then let's increase the size so I'm gonna go let's see I want to go outside of this if statement here and let's say this dot size because we have a size property and let's increment that by one actually let's do that here as well this dot size plus plus okay so now we should be able to insert on to the end right now this is what our list looks like 300 200 100 let's say we want to add 400 to the end or to the last so we'll say ll dot insert last let's say 400 so now if I go ahead and I print this notice that 400 gets put at the end okay so we can now insert first insert last now what I'd like to do is take care of inserts you know anywhere in between so basically add an index and these are indexed as like arrays 0 1 2 3 0 1 2 3 and so on so let's go right here and let's say insert that we want to pass in here we're going to pass in two things data and then the index where we want to insert and there's a couple edge cases we have to take care of if there's basically if there if we try to put an index that doesn't exist like in this case we have our list is 0 1 2 3 if we try to insert into like 20 then we want to just basically return back and not do anything so let's say if you can handle this in different ways so let's say if index is greater than zero and the index is greater than the size so this dot size it's greater than the complete size of the of the linked list then I'm just gonna return okay we're not going to do anything so that's one case and we could probably put a comment here and just say if index is out of range and there might be a couple edge cases that I miss if I do feel free to leave it in the comments if you have any other ideas that's I'm open to that just don't be a dick about it please the next thing we want to do is take care of if it's the first index which is zero so let's say because if it's if that's the case then we just need to set it to the head right because it's the first one so let's say if first index so we can just take index and if you want if you want to pause it at any time and try this try some of this stuff yourself feel free to do it I encourage that so let's say if this is equal to zero if we want to insert at the zero index then we're just gonna take this dot head and set that to new node pass in the data that's that we passed in and say this dot head as our next value because we're gonna push that over and then we're just going to return okay so now let's see we took care of if it's out of range if it's the first so let's let's take care of them the rest so what I'll do here is let's say Const node will initialize a new node with the data and I'm going to initialize two variables current and previous all right and then let's go ahead and whoops what'd I just do current previous and trying to think here let's set currents to first by saying currents equals this dot head and we're gonna be doing a loop so I'm gonna have a counter I'm gonna say let count equals zero okay we're going to start that at zero now let's do a while loop and let's say while the count which starts at zero is less than the index okay so I mean if we pass in one as an index then it's going to say if zero is greater than one that's going to be the first iteration so here we want to take previous and we want to set that equal to current okay so this is basically the node before the index that we want to insert so we want the previous okay because we're looking at if we want to insert right here which is zero one two this is the two index then we want to reference to the previous one here and we're making that equal to whatever the current is which in this case is going to be the head and then we're going to increase the count so we'll just increment the count by one and then we're gonna set the current one to whatever the next is so current dot next so we're just basically making room for for our element or for our new node so this is the node after the index okay so outside of this while loop now we're gonna take the node that we initialized above and set the next value to its current okay so the new node or the new node next I should say should now be whatever the value of current alright and then we're gonna set I don't need a comment here let's set the previous we'll take the previous one which would be if we were inserting here would be two hundred and let's say dot next which would be this one here and that's where we want to put insert the new node so we're gonna set that equal to node okay I know that's that's probably confusing especially if you're kind of new to JavaScript and all this stuff but this should work and then we just want to increase the size because we added a node and let's save and now we can test it out so let's see we have three hundred two hundred one hundred four hundred let's say we want to put five hundred at the zero one two index so it should be in between 200 and 100 so I'm gonna say ll dot insert at so we need the data which is going to be 500 and we want to put that at the two index so let's run that and now you can see that we have zero one two so 500 is at the two index now let's try some other edge cases like if it's the first one let's make sure that works so now if we run that 500 is now the head it's now the first one which is this this or this case right here let's test this out where if it's out of range so if I try to put it in the index of let's say 10 which doesn't exist and we run this it just it's just not there okay it just doesn't get added and if you want to change the logic around maybe you'll want to add it to the end you can do that there's no you know set in stone rule on how how that works as long as you follow the basic principles of the linked list okay so now that we can insert wherever we want let's um well we have next get at index so basically we want to be able to get a value at a certain index so let's say get at and pass in an index and some of this is going to be pretty similar to what we just did so we're gonna set a current variable to the beginning which is this dot head and let's set a count to zero and then we're going to just loop through this we're gonna say while current then we want to test to see if the count which is initialized with zero is equal to the index that's all we're gonna tell which one we need if it is then let's do a console log of current that'll give us the whole node but let's just get the data all right and then down here let's see under the if statement we need to increment so let's say count plus plus and then of course we need to be we need to move along the linked list down the chain so we're gonna say current equals current dot next okay otherwise it'll just be a never-ending loop and then down at the bottom here under the while loop that means it's empty so we can return I'll just return I guess yeah it should should be fine or return null okay so let's save that now I want to be able to get a specific value from an index so let's let's go down here and let's say instead of print list data I'm going to comment that out let's do ll get at and let's see what's at index two ok we'll clear this up and run it that didn't work why didn't that work looks like I have extra for it why did it wait a minute while currents if kau I did a single equals okay so let's try that again and we get 100 so is that correct so we have that's index 2 so 0 1 2 is 100 let's try get at 0 we should get 300 let's try get at 10 which doesn't exist and we get nothing ok and again if you want to change the logic to get the last value or whatever you can do that alright so now we want to be able to remove at a certain ten decks so let's say remove at pass in an index and I'm gonna first check to make sure the index are yeah we'll say if the index is greater than zero and the index is yeah the index is greater than this dot size so basically if it's out of range then let's just return ok and then we're gonna set our marker or our current variable to the first node and then let's initialize previous and let's initialize count as zero okay so if it's the first say remove first so if if the index is equal to zero meaning we want to remove the first one then that's pretty simple we can just set this dot head to current dot next so basically we're just we're just setting the head to whatever the next value is so it would make 200 the first one all right else so if index is not equal to zero then let's do a while loop and let's say while the count is less than the index then let's increase the count and we're gonna set that previous value to the current value and we're gonna set current to whatever the next value is so current dot next okay and then to remove the element will go outside of the while loop and we'll set the previous dot next value to the current dot next value all right and since we removed then we want to decrease the size so underneath the ifs demon let's say this dot size - - okay so let's clear this up and then let's try to remove so right now let's let's print this out okay so if 300 200 100 400 let's say we want to remove 100 which is in the zero one two index so right above the print list let's say ll dots remove was remove at and we want the two index so now let's run this and now 100 is gone which is the two index let's try to remove the zero index which would be the 300 so if we run that now 300 is gone if we want to remove the last one which is zero one two three so if we move the third index that should get rid of 400 and then if we go out of range you'll say 33 then it just gives us you know it doesn't remove anything okay so now we can print the list we can insert at the beginning at the end in the middle we can get values last thing I want to do is to be able to clear the list so it's a clear list and this is pretty simple now remember the the class here it only knows about the head so if we set this dot head equal to null then that should clear everything out because now we have no reference to the rest of the list and then we'll just set the size also equal to zero all right so if I go down here now right between the the inserts and then the print list data and I say ll dot clear lists and I run this we get nothing okay and it might be still stored as stuff stored in memory but that's that's besides the point we just need to have a working linked list all right so it's it's kind of a just a good exercise to work out your mind so if you guys want to continue on maybe create a remove last or remove first you could do that or you know get first get last there's different methods you could add to this to kind of you know work on your your problem solving skills but what we have here is adhering to the principles of a linked list and I know that some of it might not be completely clear I know it's it can be kind of difficult but there's a lot of information out there on linked lists in all types of languages so that's it hopefully you guys enjoyed this if you want more content like this where we do just logic and problem solving and stuff like that let me know of course we're going to still stick to projects and stuff like that but I'd like to get more into this stuff and you can give me some suggestions alright thanks for watching and I'll see you next time

Channel: Traversy Media

Views: 97,170

Rating: 4.964417 out of 5

Keywords: linked list, linked lists, javascript linked list, javascript data structures, data structures

Id: ZBdE8DElQQU

Length: 29min 35sec (1775 seconds)

Published: Wed Jul 03 2019