hey guys Greg here let's talk about linked lists today and there's two types of them there's singly linked lists as well as doubly linked lists now in picture form a singly linked list might look something like this which is basically circles with values in them and then they point to other circles with the values so we have one pointing to two which points to three and the three actually points over to nothing and that's important because that kind of signifies here that this is the end of the list okay so we'd call this a singly linked list basically because there's this single connection here between the nodes later on we'll see a doubly link list that would basically just be this where we have the backwards link as well but this is called a singly linked list where basically each of these things generally you call them a linked list node or in short form you generally just call them a node so a node is like an object and it has a couple different features to it one it has some sort of memory address as to where it's located in the computer so this is not like an array where an array is like a contiguous sequence of computer memory this is not the case here we actually have this as some sort of address which is going to be some hex code it doesn't really matter what this is here just know that it's some memory address and I'll just kind of short form this to be a so it's the memory address of a and this one would have a completely different memory address likely even very far away in the computer memory of B and this one might be called C and this last thing here what it's pointing over to is generally in a programming language something like null so you might see it be called null in Python we generally have that called none whatever it is it's just some programming language specific that says a special marker saying this is the end of the list okay so what actually is a linked list node well in a computer programming language we have these things called classes okay and classes create these things called objects so basically you would have some sort of thing called like a class node object it would have a value as you can see here it clearly has a node. value we'll write it like that and it also has a node. next so node. next is basically a reference to a different object if we were talking about this guy here well then it would have a next of basically the address of B saying that its next address is pointing over to B and what that allows us to do if you have a its next is pointing over to B and its next is C and its next is none well then this forms a chain because we can basically start here generally you would have some sort of a reference to the head of the linked list which is going to be the front of it so given this reference to the head here well then we can basically go through the list here until we hit none now this is basically an alternative way to store data compared to say an array where an array has certain elements like if you were to ask what is the array at maybe an index of five well in O of one time that array would tell you what is at position five but that's not a thing for a linked list here you can't say what is at the index these things don't have indices generally what we're given is the head to the linked list and to find any of the different elements in here you'd actually have to Traverse the list to do that now by the way here we're storing just the values of 1 2 and three but you can pretty much store any type of data you want in one of those linked list nodes but for lead code style problems they generally just kind of have the numbers there okay so there's a few different things you might want to do with a linked list for example if you wanted to add a new node at an arbitrary positions so maybe add a node at the position of two for example well we don't really have positions here like an array but you could still think of it as this is say the first spot this is the second spot and the third spot and we'll say that we're adding the Noe of a value of five you'd have to start at your head because that's generally all that you're given you're not actually generally given a b and c here and so to add the node at position two you would have to Traverse the list from the start until you got to that position and then you could put that Noe in there you would want one to point over to the five so you'd have to change one to point that over to five and then you'd have to point the five over to the two a general and O of n operation because you have to start at the head of the linked list Traverse to get to that position and then you can adjust it now similarly if you wanted to instead delete a node at position 2 well then you'd have to start at the beginning pretty much like always and then you'd have to go through until you you get to that position and basically just remove it which would involve pointing the previous one over to the next one like that and then you could think of your positions as adjusted like this so 1 2 and three okay so again that's going to be an oent operation cuz you start at the beginning and go up until that position now even more simply if you wanted to just say access a node at a certain position so you didn't want to remove or add it you just wanted to kind of look what's there well again you'd kind of have to start at the beginning and go up until that position to kind of read that element so again an oent thing to do now an operation we generally perform on pretty much every single data structure that we have is lookup so in this case it would be seeing if a certain value is in the linked list okay so you could probably guess that's going to be an oent operation because in the worst case you would have to go through the entire list and have not found it or if you were looking up say something like two well then you would go through and see that two is there but still that's going to be an O of n thing to do now there is a couple things that are o of One op operations so one thing that linked lists are really good at is if you are talking about the beginning of the list so if you wanted to basically remove the thing at the beginning well then that is going to be an O of one operation because basically you would just kind of Point your head element over to this second position here so that would effectively just remove this and then you could think of your positions as one and two although I'm going to stop kind of writing the positions because they don't really exist if you wanted to add a new head so if all you wanted to do is kind of put some something at the very beginning well then yeah that's also going to be o of one you'd basically Point your head over to that new element and then you would Point your new element over to that one so that's also going to be o of one and if you particularly happen to have the reference to say the node here so maybe you happen to have node C over here and you wanted to say remove that what's kind of tricky about this is that if you just kind of remove this given access to node C well then how do you actually change where this node points to because it's sing linked list and so just given C you don't actually have the ability to adjust this one here you want to adjust this next pointer except you don't have that because you just have this node so that's why in practice a lot of the time we actually switch over to doubly link lists which is basically going to be the exact same thing here except we have the reverse connection and our head would actually Point reverse Direction over to none as well so basically saying we have a head element so we still have a head which I'm just going to Mark as h and we also kind of have access immediately to this tail so generally now instead of just access to the front you also have access to the back via the tail and we can kind of go both directions here you could Traverse through this way or you could Traverse backwards so this is a doubly linked list and by the way how this might look in a programming language is you might have a class node which is basically going to have three things now it would have basically a node do value so what it's storing it would have a no. next these are the exact same things as before but then you also might have a node. previous basically saying that each node here they all have a next pointer and they also have a previous pointer and sometimes I might say pointer sometimes I might say reference if you really truly want to understand the whole pointer thing then you'd want to take a class in C but from a python perspective it's basically just that node. nextext is like a reference to a node object and node. preve would be a reference to a node object as well now one thing the W link list does help with is if you had say a reference to this node here you had that if you wanted to delete that so basically if you wanted to delete node B well then you actually only need access to this node here because from this node you could actually access this one because you have the connection to it and you could also access this one so you could actually remove it because basically what you'd have to do is point this previous thing over to the next one and you'd have to point its next one basically back over to the previous one so this does allow basically deleting an element at a particular reference that would actually be constant although we often don't have that ability because generally you only have access to the head and the tail sometimes you have access to kind of the middle node references okay so let's see how we can work with singly and doubly linked lists in Python okay let's start with singly linked lists here so we need a class that makes a node we'll call it singly node and so for the Constructor here now they're going to take a value and they're going to take a next pointer so what it's pointing over to and by default this is just none or null okay and all the Constructor is going to do is just set that its value is the value passed in and the next pointer is the next passed in okay then we'll just give it a simple print method so we can print one of these that is the string method so underscore string like that and this just returns some sort of a string representation so this is going to be the string of the self. Val so we take whatever the V is we just convert that to a string and that's how this thing is going to print okay then to make a linked list you generally have reference only to the head so we'll call it head that's going to be a singly node which just has a value of one now by default this will make the next pointer just none but we'll set those explicitly in a moment we'll get three other nodes I'll call it a is the singly node of three and B is the singly node of four and C is the singly node of seven so we now have four different nodes where the head is one okay now to actually join these things up here by default we kind of just have these floating around in space we want to connect them up so head. next is equal to a points head over to a then a do next is equal to B and b. nextt is equal to C so now we have the connection of head points over to a which points over to B which points over to C and then C is still pointing over to nothing and for now we can just print the head of the list although that's not going to show the full list it's just going to show the value of the first node okay now one thing we usually want to do this is the most common pattern with length lists is some sort of Travers veral so in general just to Traverse the list print the values to Traverse the list this is going to be of course an O of n operation cuz we're visiting all the nodes then you generally get a variable called something like cerr and we'll point that at the head and we keep moving cerr over so while we have Curr so basically until cerr turns into none we will print the current node and then we are going to just move cerr over so we set cerr equal to c. next this effectively traverses cerr throughout the entire linked list until cerr hits the node of C then it's going to point to c. next which is null it'll end the while loop and so if we're just to run this here we'll see 1 3 47 so most linked list problems will be some sort of pattern where you Traverse the list now something that's going to prove very useful is being able to display it well so just basically displaying the linked list and this is going to take definitely o of n time we're going to call that a function display which takes a head so again we'll get a pointer or variable Curr is equal to the Head we'll build up a list of elements so elements is going to be a dynamic array or a list and then while we have Curr well we have one more element so we'd elements. append add that to the array we'll give it the string of the current Dov value and then we would just move C over so C is equal to c. next now after this Loop concludes we'd eventually have Curr is none and so what we want to do is print the string of the arrow like this and note the spaces so that it looks good do join up the elements so if you haven't seen join before basically what that would do do is given a list of strings so something like this A and B and C well join is going to move them into the string of just ABC but this thing here is what you kind of call a glue it's how it glues them together then when you join them it's going to kind of move them like this so it'll glue them together so it ends up looking like this so that's exactly what this does here if you display so display the original head that's going to show the link list very pretty like that okay now something you might want to do is search for a node so search sech for a node value and that's going to take o of n time so to do that we'll Define a function called search which again takes a head and it's also going to take a value to look for this pattern comes up all the time C is equal to head and then while we have C if the Val we're looking for is equal to the current value well then that means we found it and so we would return true if that wasn't the case then we need to keep looking so we set Cur equal to c. next and if this Loop ever concludes it means that we didn't find it and so we would return false at this level so let's just search for a few things here if we search for the value of two sorry you have to give that the head so search for head and two that is going to show up false we don't have that if you have nine that is also not the case if you have something that is in there like the head of one or the tail of seven clearly our search function works okay there's lots of exciting algorithms to learn about linked lists but you can learn those in the leak code problems okay now we're going to do doubly linked lists so for that again we'd have a class which is called doubly node so we have the forward and backward connection it takes a value that the node is going to be it takes a next pointer by default it's going to be none and it also has a previous which by default is going to be set to none okay then all it's going to do is just set the self. fou equal to the Past in fou and the next is going to be the next and the prieve is going to be the preve and we'll just give it a simple printing function so we'll Define underscore uncore string it's just going to return the string of the self. value the exact same as the previous okay then how we can work with this thing is you need access to both the head and the tail so we'll get head is equal to tail which is equal to a dou node and will give that the value of one if you print the head that should show you that the value is one and if you print the tail they're pointing to the same thing so this is also one so we'll Define a function call it display that takes just the head of the linked list you don't need the tail for this so we'll get Cur is equal to the head our elements is our list and again while we have cerr we want to elements. append the string of the C.V so exactly the same thing and we'd set c equal to c. next and then after we get out of here we just want to print with a different glue so we would print with the double connection like this implying we have forwards and backwards because we do so do join that up with the elements and if we were to run display just on our original head display the head we can see it's just one and that's totally accurate for now we just have one node so we want a function that inserts inserts at the beginning basically meaning getting a new head and that's going to be o of one so we'll Define a function called insert at beginning and that's going to take the head it's also going to take the tail and it's going to take the value that you want the new head to be so you would get a new node which is equal to a doubly node reference so we make a new node if you remember how our class looks here it is the value then next then previous so we want the value to be the value and we want to specifically specify that the next is equal to the head because it's saying that we're making a new node and we want that to be the value that we have we want this to point over to the Head the only thing we'd have to do here is set head. preve so our old head equal to the new node so before the head was basically pointing over to null because it was the head but now we want it to put in the middle pointing it to the new node we just made okay so we would return new node and the tail because this is our new head and the tail stay the same and then you would call this like with head and tail is equal to insert at beginning you'd give it the current head the current Tail as well as a new value and we'll give it the value of three so if we do that and then display our head well this is going to show that we have three at the beginning that made a new head and it points over to the one as the tail now if understanding this function was a little bit tricky that's the whole point of the lead code linked list problems is to get comfortable with drawing and then coding this idea okay similarly we could also do insert at end and I'm just kind of going to copy that and explain that for you we can insert at the end in O of one time where you give the head the tail and a new value you'd make a new node which is going to take that new value and you'd point that new node back over to the tail so that would point it left over to the old tail and then you would just need to update that your old tail is then going to point right over to your new node so this basically makes a new tail and so we'd return the head and the new tail and so if we were to run this with a value of seven we're going to see we have a new tail of seven okay as always you can get this code in the video description deson if you'd like to see it I hope this was helpful guys drop a like if it was and have a great day bye-bye