Golang Linked List - Golang Data Structures

[Music] yo what's up ninja so welcome back to the golang dojo today is an exciting day because we are kickstarting our brand new series on the golang dojo on this channel and that is golang he data structures and more specifically in today's video we are gonna going to dive right into linked lists initial but before that let me tell you that this channel is all about the go programming language if that's something that you fancy make sure to give that subscribe button a nice little poke now before we dive right into today's video we need to answer the question of why should we even care why should we care about data structures and more specifically why should we care about linkedlist in a guild now the fact of the matter is that when we are programming we are constantly using different data structures in our previous videos or in our previous series we talked about the basics of at the go programming language and with a part of some data structures already such as waves slides and maps and so on when we are trying to organize a scatter data pieces into a collection inevitably we would have to use these data structures if we want to have a array of integers obviously we are going to create some sort of arrays in a go and the same thing for slices and maps and sets and so on now these built-in data structures are awesome in fact they are extremely powerful especially in the go programming language and how go implements them however as we develop more and more different use cases in our various programs that we work on there's often a need for us to build some slightly more complex even more complex data structures on our own in order to satisfy some of these new use cases and most importantly we need to learn some of these data structures not because we need to use it all the time in our day-to-day tasks but because the fact that we need these data structures so we need to know these data structures like our the back of our hand in order to pass these goddamn coding interviews so that we can actually start making money and don't have to environment every single day and a linked list is one of the most uncommon if not the most uncommon data structure that come up during these occurring interviews that we inevitably have to encounter that said in today's video we are going to start with talking about what is a link list how it really works and why exactly do we want to use a linked list compared to all the other different data structures including the built-in data structures in go and then we are going to move on to the actual implementation how to implement a linked list in guild especially if you consider the fact that there are definitely some quirks that when you are programming in go compared to your one of the male computer science type of a language unlike java and this is definitely going to come in handy not only for beginners in general but also for golang beginners specifically now first of all what is a linked list by definition a lingulis is a linear collection of a data element whose order is not given by the physical placement in memory now this might not make any sense at all for a lot of people so let's move on to an actual example to figure out what a linked list is now here in front of us and we have a four different elements that we want to store in a linked list and they are integer values from a 1 to 4. now if we want to store each one of these elements into a linked list so we need to create a data piece for one of the integer values and this data piece and it needs to consist of a two different elements and one is going to be the actual container for the integer value that is going to store the integer value of one and the next element is going to be the pointer pointing to the next data piece and this next data piece is going to have the exact same data structure as the previous one so if we go ahead and occupy all of these data pieces here it is going to look something like this and now notice that the very last pointer is not going to point to anything and in the case of go it would just point to like a new indicating that hey this is going to be the last element in this data structure of a linked list on top of that there are three common operations that you typically would make onto this data structure of a linked list and they are add remove and get now for the operation of adding an element all you need to do is creating a new data piece like we did before that is a going to store the whatever integer value or whatever value that you have and that you want to store and be able to point these elements at this last element onto this newly created elements and then scratch this and have this last element are pointing it to to no now the second operation is going to be the remove operation now we've already had demonstrated the operation of add what we need to do is creating these last elements of 4 and be able to point the previously last element into this newly created element of 4 here and also making sure that this newly created element is pointing to nil now for the second operation of remove this is where it gets slightly more complicated uh because it is a linked list instead of something like an away now let's say that we are trying to delete the element of a three here because this is a linked list it is not an indexed data structure meaning that we don't have instant access to every single element in this data structure what we need to do is it traverse through each and every single one of these elements and checking if let's say that you're trying to move a three here checking if for each iteration if this element is a three when we are added there's a first element here we can see that it is not a three so we go to the next one in this case it's not so another three we go to the next one and once we find this element that is when we will get this one out of this linked list we go into the actual implementation in just a little bit here but the gist of it is that we need to iterate through potentially every single one of these elements in order to find the one that we actually will remove out of this data structure so hence the big goal of n here n being the number of elements in this data structure now the last common operation on a linked list a data structure is going to be the get operation now the get operation is a pretty similar to the remove operation that we just talked about in a sense that we do need to iterate through every single one of these data structures potentially in order to gather the elements that we are trying to find so let's say that we want to find this element of three or at a position three we only have axes of the very first element here so we do need to iterate through potentially each and every single one of these available elements in this data structure in order to find the elements that we are trying to get so the one time is also a linear time uh big off and this ended being the number of available elements in this linked list now if you are watching this video there's a pretty good chance that you don't know what a big old notations are what they really mean or you haven't learned about it but you never really grasped uh how it actually works so let's in the next slide let's talk about what a big old notations are and how they really work since we are talking about linked lists today so we will talk about two of the big old notations and the first one is going to be a big o of a one aka concern one time the second one is a bagel of n and it being the number of elements in the data structure or as known as a linear runtime so the bigger notation is all about the number of elements in the data structure versus or in relation to the number of computations that you have to perform according to the increasing number of elements in the data structure now bigger of a one or bigger of two bigger three big o of any constant number well the graph will look at something like this and now as you can see there's an increase in terms of a number of elements for that data structure but the number of computations and needed for a particular operation on that data structure will stay constant as you can see there's no increase or decrease in terms of the number of computations and needed and a number uh the big o of n n is stands for the number of elements in the data structure the graph is going to look at something like this as you can see there's a linear progression in terms of a number of computations while we have a proportional increase of a number of elements in that data structure now if we go back to the previous slide here for the linked list as you can remember for the remove and again both of these operations on a linked list will require a run time of a big o of n and if you have watched my video on a raze indigo lang you will you can remember that also both remove and get our constant operations on an array now so why would we even use a linked list as opposed to a and a way if in a way is much faster than a linked list and that's what we're going to talk about in our next slide we're going to have a more cohesive comparison uh between linked lists and a way so that you have you would have a better idea better understanding of why we would use a linked list and what are the advantages of a linked list it all just comes down to the add operation differences between the two data structures between a linked list and an array now for linglist the add operation is pretty straightforward as we have already demonstrated all you need to do is creating new elements and append it to the end of this linked list however for a raise is slightly more complicated if you want to store one element into an array first of all you would need to pre-allocate a certain number of slots in the memory let's say that we are pre-allocating four different slots in order to store one element and that element is of a value of one so we put one here now we are trying to append another value another actual element which is going to be two then we will we will just put two in to one of the four allocated slots here no problem however as we are appending more and more elements into this array there comes a time where all of these slides are being perfectly occupied and if we want to add another element that will exceed the number of pre-allocated slots in this data structure now we need to find a way to grab additional slots however the problem is that there is no guarantee that we can just go ahead and allocate the next i don't know four more slots immediately after the pre-allocated four slots like the next four slides that could very well be occupied by some other data pieces instead of having the option to allocate the slots immediately afterwards what you need to do is allocate eight slots in a different spot in the memory and what you need to do is move all of these elements to this newly newly allocated slot and then add this a brand new five at the fifth element towards the end of these newly allocated slots now as you can probably already guess moving all of these elements into these newly allocated slots is going to be a bigger of n or linear operation the cap value is that though because how celebrated and we would need to perform this action the actual run time for each spread out to each one of these elements is actually constant now we're not going to go ahead and prove this in today's video because today's video is more about linked list rather than a raise but i said just give me the benefit of the thousand for the sake of this video even with this in mind we still have a problem of not fully utilizing all of the memory in our possession and on top of that what's more important is that if we are trying to store maybe hundreds of thousands of elements into one single data structure we are going to have a massive problem of finding there's a continuous memory that will allow us to store hundreds of thousands of elements because for eraser we need to find a continuous memory in order to store all of these elements in contrast to linked lists we can just put these newly created elements in random spaces spread out in any random spot in the memory and then all we need to do is making sure that the next pointer is pointing to this newly uh created element and this goes back into full circle to the definition of a what a linked list is a linked list is a linear collection of data elements whose order is not given by the physical placement in the memory as supposed to arrays where we need to find a continuous assignment in the memory in order to do the job all right finally the fun part of this video we are diving right into the implementation of a linked list in hindi golang so what you can expect is that we are going to introduce a node which is the individual elements that we are appending to the linked list data structure and then we are going to have a wrapper for the linked list to make everything look prettier and then we are going to have a four different methods the very first one is adding the elements removing the elements and then we are going to get the elements from the data structure and we are going to have a two string method that will traverse through each and every single element and print them out and when we call this method coming right up all right so here we have a clean slate and we're going to get started the first thing that we need to do is declare a type no which is a struct there's a no struct is going to contain the two things the very first one is the actual value for the node if everything there's ever a particular video we are going to create a linked list of type integers so the value is going to be of a type integer the second thing for the node is a next pointer that is a no pointer and that's it no struct the second thing we need to do need to create is a type linked list itself that is also a struct there's a linked list struct is going to consist of two things the very first one is at the head of the linked list so that we can actually grab this no pointer and be able to traverse it through every single element afterwards the second element is going to be the length of this linked list indicating that how many elements we have in this linked list so the no and the linked list structs are created now we need to take care of these four different methods for that i've filled in the signature for all of these four different methods the very first one is add we are going to take in a value that is an integer and then we're going to perform some sort of operations or instructions in order to add an element to the linked list now notice that this linked list is a linked list a pointer meaning that anything that we added to the linked list will be reflected back into the linked list object itself with the caveat that the last two methods will not have this star operator here because when we are getting we are now trying to modify the internal structure of other linked lists and same thing for when we are implementing the string method we are not trying to make any sort of modification to the linked list structure that said the added method has a integer value passed in same thing for the remove method and same thing for the get method and the string method is not going to have any value being passed in all you need to do is getting what the original the already existing headlink list and it traverses through all of the elements and print out the different elements so let's talk about the added method first first of all we have a header pointer in our linked list this is right now pointing nowhere it's appointing to nil because we don't have anything that is worthy of pointing to for the head because no element has it created but when we are calling the adder method we are trying to maybe add one into the data structure so first of all we would need to create this node that consists of two things the first thing is going to be the element itself and the value itself and the second thing is going to be the next a pointer the next pointer is going to be point to no or you don't have to specify it but it is appointing to nil and we need to make sure that if the head is new which it is because right now is point not pointing anything aka is pointing to nil we need to make sure that if head is new then we need to make the head to point to this newly created element all right so that is what we are going to do first of all we need to create a new node by using the new keyword passing the struct that is going to be the type that we are that the nuno is going to be of the second thing is assigning the value for there's a new node the value that we are assigning is going to be the value integer value being passed in into this method the third thing would be it's optional and that is assigning the next pointer to a new now pointers in go are the zero value for pointers are already new so this part is a redundant so we don't have to have this line here and that's what we're going to do we are going to delete this line because it is redundant the next thing is uh making sure that for checking if the head of the linked list is equal to new if it is then we are going to assign this a new node to the head of the linked list now notice that the code that we just wrote is literally step by step what the graph that we drew is about and i know some people might think that implementing these data structures are kind of difficult and that is because not because we can't write the code itself but we don't have a thorough understanding of how to implement and how the data structure actually works and as you can see if you have a through understanding of how to implement a specific method by drawing some graph then the implementation or the part to write the code itself it should be relatively simple because all you are really doing is putting all of the logics that you already understand in a form i don't know it may be in the form of a drawing into the literal code itself so if you have a difficulty implementing some of these data structures the first thing that i would recommend personally is to try to have a better understanding of the data structure itself beforehand moving into the implementation alright so now we've run through the case when the head is equal to nil what if we want to continue adding elements into the linked list let's say that we want to add two into the linked list so what we're going to do is we are going to again create this no that is it consists of a two things the first thing is assigning the value to this element the second thing is making sure that the next pointer is appointing to neil and the third step is going to be iterating through all of the elements in that the head is connected to and taking the very last element and point that into this newly created element and the way that you can make sure that it is the last element you are iterating to the last element is to check if this pointer that you're pointing at if it's next a pointer is a new if it's new then you know this is going to be the last element in this linked list and just point that to the newly created elements which is the second element in this case so if the head is not neo we have a else here then we will have some sort of iterator pointer that is according to the head of the linked list and we want to iterate through all of the elements that the head is connected to and grab the very last element for that we are going to use a for loop while the next pointer is not equal to nil we will continue iterating through the linked list in order to grab the last element once we graph the the last element and the last element next pointer is equal to new then we can go ahead and point that next pointer to the newly created no like this and this is how you would implement the add method in a linked list all right so we have the ling list struct and we have the atom method so let's go ahead and use these into things the first thing is going to be we will create a linked list like this and second is adding elements into this linked list now if we go ahead and run this program it's not going to do anything because we are merely adding elements into the linked list so if we maybe like try to print out the linked list for example it's not going to show us much of anything because it doesn't know what to print out that is why we want to implement this a string method next so that we have a some way of debugging all of the code that we just wrote or just inspecting the internal structure of this linked list in general so this string method is essentially a iterating method so let's say that we have these elements in the array or in the linked list say that we have a three elements and the last element is pointing to neo we also have this header in the language according to the very first element the thing is that we don't want to mess around with this head pointer the reason being that if we somehow make a mistake and point this header to some other elements in the linked list and there's no way that we can again access the first element in this linked list so we are not going to mess with pointer what we want to do is to have some sort of a temporary header pointer in order to iterate through all of these elements while temporary iterator pointer is not new we want to print out or put the elements into a maybe like a string builder and then at the end and be able to return this string stringbuilder.string as the result of this tooth string method and in order to iterate through the next element we would use a simple instruction of iterator equals to iterator dot next as long as this iterator is not equal to new and that is the condition for the iteration so that's how you would write a iterating method for a linked list all right so let's go ahead and put this into code first of all we need to declare a string builder to capture all of the values as we are iterating through the linked list second is creating a for loop in order to iterate through each and every single element first we need to create the iterator have that point to the same element that the header pointer of the linked list is pointing to secondly we need to have a condition for this a full loop while the iterator is not equal to nil and then at the end we will move on into the next element in the linked list in each of these iterations we will go ahead and start building our string builder using fonts dot as a printf we're saying d because the value for the iterator for each element is a integer it's a digit at the end we will return what the string builder has so far so if we go ahead and run this program we should be able to see that hey we have and one element in this linked list and that is one which makes sense now one extra thing that we can potentially do to make our code slightly nicer is get rid of this value and actually have a string here but if we go ahead and run this program again as you can see it is not really putting out anything that really makes sense because the iterator right now which is the element which is the no struct it doesn't have a string a method to make when we are putting out the element itself we don't have a nice way to represent the element which leads us to create a tostring method for the no struct as well and how we would do that is we would use the exact same format as how we implemented the tostring method for the linked list struct as well we will go ahead and return find as a printf here we use a digit dot value when we are putting out the note itself it would know to bring the notes a value instead of anything else so let's go ahead and run this program again as you can see we are getting one again on top of that we can call this add method multiple times we can do i think one two three four five and then we print out the linked list go ahead and run this program again as you can see it is putting out all of the elements in the linked list that we have added all right so the next method that we are going to implement is the get method now this one is pretty simple uh in the sense that we are going to pick it back right on the iterating logic so to speak what we need to pay additional attention to is if we are trying to get maybe the second element or the element that has a value of a two then we need to maybe have a condition of if iterator data value is equal to two then we want to return the width iterator that we are on right now if we can never find any value that is the same as the value that we're looking for then at the end we will just return a new so let's go ahead and move to the code so we are going to have the exact same for loop we will instantiate the elevator to point to where the element that the headed point of the linked list is appointing to second while iterator is not equal to nil we will continue with the iteration or the continue with the next iteration now we have a condition here if iterator data value is equal to the value that we are looking for we will go ahead and return this iterator otherwise at the very end if we go through the entire linked list and could not find any elements that satisfy this condition then we will go ahead and return neo like this so let's go ahead and go to the main method and i try to print out l dot again maybe we are trying to get five we will just go ahead and print out the fifth element i'm just making sure that we are taking the pointer but we are trying to get the content of that pointer so let's go ahead and print this out we should be able to print out the five because the node as we remember when we are printing out the node we will go ahead and print out the node's value let's go ahead and run this program again as you can see after iterating through all of the elements in the linked list we are also getting this one single element that we are looking for all right so we are on our last method that we need to implement out of the four different methods that we need to implement today in today's video for linked lists this is probably the least straightforward method that we are implementing and i'll explain why so we are still going to have the exact same innovators and we are going to again let's say that we are trying to remove the second element out of the linked list we will continue iterating through each and every single one of these elements in the linked list and check if the value of the element is equal to the value that we are looking to remove and when we are iterating through the different elements let's say that we are on the second halo element this will be not element relevant anymore the problem is though when we are at this second element what we want is actually the previous element and have its next opponent pointing to the current elements as next element however we don't have access to this previous element anymore not only do we want this current excuse me that is my pomodoro let me go ahead and pause that not only do we want there's a current pointer pointing to the each and every single elements and that we are iterating we also want an additional pointer called a previous pointer pointing to the previous element to the current element which is the iterator element only in this way we will be putting the next pointer of the previous element and have it point to the next element of the current element with that of course we need to put that into little code again first of all we need to introduce a new pointer that is the previous no pointer next we will go ahead and have our usual for loop iterating through each and every single one of the elements except that at this time we will call the iterating pointer current pointer instead but it's the same exact same thing inside of these different iterations we want to have a if condition if the current value is equal to the value that we are looking for then we need to remove this element and in order to remove this element we need to take the previous node and have its next pointer pointing to the current node is next element and after that we need to make sure that we are returning because we no longer need to keep on iterating through the following elements in the link listed because we've already found the node that we're trying to remove and also we need to advance or increment the previous a pointer to point to the current pointer before the current pointer gets advanced as well now let's go ahead and try out this method we will try to remove maybe the third element we will try to also remove maybe the last element and then we will go ahead and print out the list again and let's go ahead and run this program and see if the method that we just wrote is working fine as you can see the original link list is one two three four five and we removed the third element and we removed the fifth element and it it is indeed the case as we can see with putting out our linked list and it is saying that the remaining elements are one two four with three and five and nowhere to be seen now don't be so happy yet we're actually not done unfortunately there is a bug with the code that we just wrote let's say that we are trying to remove the first element instead and we will try to print out the linked list again after removing the first element let's see how the program is going to react go ahead and run this program again as you can see unfortunately there is a no pointer exception so we need to go back and debug all the code again now the reason that it doesn't work is because we are trying to remove the very first element in the linked list now let's just say that there's multiple problems here the first problem is that the previous pointer is near white now so news.net is going to give us a no pointer and even if we is instantiate the previous pointer so that it has a placeholder this function is still not going to work because with our existing logic we will set the previous next pointer to point to the next element of the current element and that's all we are doing with all the existing logic and this is still not going to work even though we've solved there's no point of exception the first and no point of exception no point of exception what we want to do is actually have a condition to check if the current know that we are on it to check if it's equal to the head of the entire linked list if that is the case we want to set it so that the head will be equal to the current dot next again as you can remember we have a head here pointing to the first element of the linked list what we want to do is have this head get rid of this next point pointing to the first element of the linked list instead we will have the head point to the next element of the current element that said let's go ahead and fix the problem that we are having right now go back to the remove method so again we will need to add an additional if a condition here to check if the head of the linked list is equal to the current node that we are on right now if that is the case if we want to have the head to point to the current elements next element otherwise we will continue as usual with the logic that we've written before so this would be how we would fix the bug that we had so far so let's go ahead and run this program again hopefully this time yes as you can see we are removing three and five leaving one two four in the linked list and then we are removing the first element in the linked list and as you can see we've removed the first element of the linked list successfully a small review of what we've covered in today's video we've talked about the what how and why of a linked list and then we move on to the implementation of a linked list in yo the four different methods as well as the node and the linkedlist wrapper itself alright so that's it for today's video if you found this video helpful make sure to leave this video a thumbs up this type of video takes a lot to produce it actually took me quite a few days to come up with the script to come up with the code and come up with the slides for this video and then filming this video actually takes a really long time too as you can probably tell from the window here it took me an entire day to film this one single video so if you don't mind make sure to leave this video a thumbs up i would really really appreciate it and also in the future videos right after this one i will have more interesting uh data structures that are not a built-in data structures in go coming up so make sure to subscribe to this channel and turn on that notification bell also i want to bring up the caveat that the implementations for the methods on the linked list that i've talked about in today's video aren't the only implementations that you can have for example for the remover method instead of passing in a value you can pass in for example you can pass in a no pointer so that you can reduce your runtime from a bigger off n to big o of one can't sit one time that said i'll see you in ninjas in the next one you

Channel: Golang Dojo

Views: 2,233

Keywords: golang, golang 2021, learn golang, go lang, golang in 2021, go language, golang tutorial, go tutorial, go programming language, golang tutorial for beginners, golang crash course, golang for beginners, Golang Linked List - Golang Data Structures, golang linked list, golang data structures, golang linked list tutorial, linked list in go/golang, data structures in go, linked list in go, data structures in golang, linked list tutorial in go, linked list in golang, linked list

Id: I8n71J0wdBg

Length: 40min 55sec (2455 seconds)

Published: Tue Jul 06 2021