Introduction to Linked Lists - Data Structures and Algorithms

hey what's going on everybody this episode we're gonna be talking about linked lists I did just do a video on arrays versus linked lists and some of the differences but it was just an introduction so if you want a little bit more substance that's what this video is going to provide you so hopefully by the end of this you understand what a linked list is and some of the operations you can do on a linked list so where do we even get started a linked list is an example of a data structure if you're in computer science this word either excites you or makes you want to go cry yourself to sleep probably the second one there but pretty much a data structure is just an arrangement of data it's a way to store data a very common one is a linked list so with a linked list you can think of it as a chain where you have some data and I'm just gonna use numbers to begin with but it could be anything it could be a string so it could be people's names or it could be objects custom objects whatever you want to represent here and these are just going to point to the next element now the beautiful thing here is that this arrow it doesn't have to be sequential inside of your computer's memory it can just point to any address in memory so you don't have to set a certain size at the beginning and if you want to add elements you don't have to worry about going beyond that size and either having a memory error or having to create a new array like go watch the arrays video basically if you're working with an array you get a set size of memory if you go over there's two things that can happen the first thing is you can get a memory error or it might just work but it's actually causing issues with other things in your memory so when you when you're writing in C and it just explodes and stops working you're probably doing something like this the other option is the actual storage the content is increased and that's an expensive operation because you actually have to copy the elements over to this new array and that might all happen behind the scenes I mean it's not the end of the world but it's not really ideal a linked list is different because these can all be stored anywhere in memory so if we wanted to add another one we just point somewhere else and add a new value no problem we don't have to worry about going beyond the maximum size because we do not determine that size ahead of time so that is the first benefit of a linked list now here's a big consequence of a linked list it's a chain so if I wanted to grab this element right here I actually have to start at the beginning go to the next element and keep doing that until I get here that's a very slow operation and that is something you don't have to worry about with the race so with an array you know the size of the elements and when you index it just automatically goes to that position so it doesn't matter if you're accessing index 10 or you're accessing index 10,000 it's going to be pretty much the same speed because it just goes to that spot and grabs the data with a linked list it starts at the beginning so this one is going to be a whole lot faster than this one here for an array you could say retrieving data is complexity o of 1 because if you double the length of the array it takes just as long as it did before to grab any particular element when it comes to a linked list its o of n because if you as an example doubled that linked list and you tried to grab that last element it's now going to take twice as long because we doubled the list we doubled the time it takes so it's dependent on the length of the list so if you're wanting to know when you should use a linked list it's definitely not if you need fast retrieval this absolutely horrendous because if you have a very large linked list the process becomes very very slow and that's what we really care about when it comes to data structures is how well they perform as the size increases so as the size increases this becomes very slow arrays are very fast for retrieval but what about inserting data well for a linked list let's say we wanted to insert something right here here's how we would do it if you consider this pointing to the next node all we have to do is tell it to point somewhere else so we can say P oh dude point to this node instead and this node has some other value let's say 12 and we tell it to point to this one here oh oh so although it looks a little funny here that doesn't really matter because again remember that these notes are all scattered throughout your memory and it doesn't matter what location they're at they're not sequential physically so to insert a piece of data into a linked list it's actually very quick yes you might have to find the node to start with here but once you got this all you got to do is tell it to point somewhere else and tell this new thing to point to the next value for raise it's a little bit different because if you add an element in the middle all those other elements have to be shifted over so you pretty much have to go all the way through the end of the array so again just to review what we just said this operation of adding a node is very quick if the location of this one is known otherwise it can take some time because you've got to iterate through the data following the chain until you get to the location you're looking for so it depends but it's not worse than an array now if you want to insert at the very beginning heck this is easy you just create a new box over here and point it to the starting one there you go with an array Oh yuck because you're gonna put one piece of data at the beginning and all of the other ones have to shift over one which is a process that has to go through the entire array I don't know why I keep talking about arrays here because this is not an array versus a linked list comparison video that's what we just did on here anyways this is still very helpful my wife is snoring so that's what's going on back there all right cool cool I think we understand so far all right so enough of that array comparison we're gonna get into how you would actually structure a linked list in code if you were forced to create one from scratch if you're not forced to create one from scratch and your issues in a library where it's already made then heck your life is gonna be easy but oftentimes for a class or for whatever purpose you will want to create one from scratch even if it's just to build the experience so to create a linked list there's two things you need and I'm going to represent these using classes if you're in C you'll probably use Struck's whatever it doesn't matter just some sort of container alright so you're probably going to have a class for a node which contains one piece of data and then you're also going to have a class which will be the actual linked list so consider this as a containing class that will contain a note so here's what it's going to look like inside of the node class I'll draw that out here we're gonna have two main components we're going to have the data and then some way to reference the next node in the chain so that would probably be called next this is a very common way to see this structure a class called node with two attributes data and next four linked lists this is going to be a little bit different we're going to contain the starting node of the list so that way we can always have a reference to where the list starts so you have a start if you're in a type language that's going to be of type node so basically a pointer to the very first node then you're going to have methods or operations to do things with this list so for example add delete maybe a get method whatever you need to do that works with the entire list so anything for one particular node is going to go over here in the node class anything to work with the whole list that's going to go over here so that's what your class structure is going to look like now when you go to create an actual linked list it probably looks something like this you're gonna create a linked list object so you call it whatever the heck you want linked list and heck you will do this by creating a new linked list and maybe you'll pass in the first node so you can pass in a number or you can pass in a node object whatever structure you want to do again I mentioned this but if you want the code implementation for this check out link in the description so you can create that first node so right now this is what our structure looks like we have a node with the value 5 now every single node we create has data that's going to contain the 5 and then it also has a next so we can get a reference to this node here using linked list dot and then grabbing start because remember that's always going to point to that first note so you would define that in this constructor here now to create another node you would say start dot next and assign this some note so it could look like this so we create a new node and assign it to the next attribute of this beginning node so now we're creating that pointer part to another node and we can just keep doing it if we wanted to basically follow down the chain here's what we would do we would say link to list dot start dawn next that gets us a note and then you could actually say dot next again to go to the next node and if it was a long chain let's just say it was like a few more here you could say dawn next and then dot next and then you could create another one and by saying dot next and assigning it a new note so you can see it gets a little funky when you're doing it like this so more than likely you're going to create some methods in the linked list class to make your life a whole lot easier probably this here a get method so in that situation you wanted to grab this node here you would say linked list dot to get that's going to be index 0 1 2 3 so that's gonna get the node for us then all we have to do they say dawn next and we can assign it a new node pass and some value whatever might be so this works although it's it's a little verbose obviously that took us like 10 minutes right I don't want to do all that I don't got enough finger muscles to type all that so let's go through an easier way let's talk about using one of these methods such as add we can define this such that we pass in an index we want to add at and then what value we want to put so we could say we want to add at index 4 so 0 1 2 3 4 we want to create a new node here and we want to put some value let's say 25 so we would just say add pass in 4 comma 25 now what would the method declaration look like so that this works so it's probably going to use this gap method which or just iterate through the elements once we get to here we can assign this to a variable so this is for the Declaration when you say node equal get the position so that positions passed in here and then we need to say -1 because we're trying to get the one before it and then we just say node dot next is a new node and we pass in the value which would be 25 so that is an example of how you would implement a method such as add let's take a moment to think about what this gap method might look like the way we would invoke it would be like so we say get we pass in some index let's say 4 well we always start at the beginning how do we get that beginning node you tell me oh good job we start with start so we'll just get a reference to that we'll say node is self dot start the self thing is because we're defining this within this linked list class so whatever linked list object we're talking about that's going to be referred to here that's for python syntax if you're in java or c sharp i think it'd just be this which is implicit but besides point so we get that first node then we pretty much need to replace this node with the next one a certain number of times and that is how you're going to traverse through a linked lists so you create a loop structure and python it would be something like i in range and then in and then you would pass in the index so this value 4 would go here inside these parentheses i ran out of space but you would create a variable there so 4 would be parameter of our ties to go right there so 4 is that variable and that's gonna be passed into this range so this loop will happen 4 times in this situation and each time through the loop here's what's gonna happen you're just going to grab the next node and replace this variable so you will say node equals node dot next so this part happens first so it grabs that next node so now we're pointing here and assigns it to note replacing the original value so we basically just moved our pointer from here up one to here and we repeat that process three more times the next time a node is no done next we move it here one more time we move it here and then one more time we move it here so now at the end of this loop to outside of the loop node points to this value right here and that's exactly how you get that value so all you have to do is say return you can just return that node and then whoever invokes this method has a shortcut to get a particular spot in that list so that is how you would get a value now I want to talk about how you would add or delete a value at the beginning because that's actually a little bit different let me clean up a little bit because this is disgusting all right so you have add delete get you have two options here the first one you could put some casing inside of the add and delete to check if the index is zero which will be the beginning or you could create another set of methods at beginning and delete beginning then inside of that casing you can just invoke the beginning variations that's just some decision making if you want your code to be more modular into these individual methods so let's say we add those methods in here we'll put add bag because it's long and delete bag so these would be invoked if you want to add or delete at the beginning so how do you get reference to that very first node that's right this here so these methods are going to use this methods so imagine we have this linked list so far it's pretty but I'm probably gonna slaughter in about two seconds but we basically need to add a new node over here on the left all we got to do is create a new node point it's next to that original start position and then replace start to point to this new node we just created and put whatever value you want in there so to invoke it it might look like so you can say add beginning pass in the value zero and let's go through the process we're going to create a new node we're gonna say node nine next is equal to the start and then we're going to replace start to point to this new node so this is what it would look like let's talk about deleting now we can actually keep that list the same let's say we wanted to get rid of that zero at the beginning so we invoke delete beginning and you don't actually have to pass in anything because it already knows the index and you're not adding a value so you're good to go there all you got to do with this is replace start to point to the second element in this list so we're gonna skip that first element at index zero go to index one so just gonna change that pointer and that's it so to do that all you're gonna do is say start is now equal to start dot next so you just move up one and replace that value boom you just deleted an element at the beginning super simple last thing I want to talk about is how to append data so if you wanted to add a node at the very end append and then you just pass in some value like so let's see what this definition might look like you first grab that starting node so node is the start and you're going to continue to replace this node to go through the nodes and you're gonna do this in a loop so while and we'll just say true to make an indefinite loop is just gonna keep going to a break out of it and to check if it's the last node we just to see if next is null or none in Python so while true then we can check if no Don next is null we're going to break because we got that last node then we just define the next of this note so we just say node on next and assign it a new note and we'll pass in whatever this value was parameter tries it that's hard flip set just say Val and that is how you would append and then if this is not met what we're gonna do is just say node is node on next it's kind of sloppy in there but basically that's how we progress to the next node we keep doing that until we get to the end all right so that was a ton of information and lots of drawing lots of explaining and honestly this is probably pretty confusing if you don't have the code sample so what I recommend is go through this and develop a linked list from scratch open up Python I recommend is very simple syntax or Java or whatever language you're using and build a linked list that you can run all these different operations including append and it works do some tests try appending try adding at the beginning and deleting at the beginning and see if you get any weird occurrences so that is my introduction to linked lists again link in the description if you want some help through the code samples explaining all this and be sure to subscribe and I'll see you guys in the next one let me know if this video is helpful if you want to see more of this stuff or if it was just waste of time right and all this crap up on a chalkboard thank you guys and I'll see you in the next one [Music] you

Channel: Caleb Curry

Views: 25,382

Keywords: linked list, introduction to linked lists, linked listed, nodes, linkedlists, linkedlist, python linkedlist, traversal linked list, reverse linked list

Id: HDSszyCM7Tk

Length: 22min 0sec (1320 seconds)

Published: Mon May 25 2020