Data Structures in Golang - Linked List (1/2)

hello today I want to talk about link lists because I think it's one of the most basic data structures and I think everybody needs to know about it so that's why I want to talk about that today so let's let's look into it so when data is stored in a linked list it's stored in a sequence of nodes and it's it's often compared to an array but instead of putting the values in these boxes here a linked list will put the values in in nodes that are linked with each other and when I say linked it means that each node let's call these boxes nodes contain an address indicating where the next node is okay so let's compare this to an array so each box in an array is indexed and they're physically next to each other this means if you want to change a value of an array for example let's say you want to change the fourth element 15 to 16 you can simply say go to the fourth box and which is index 3 and change 15 to 16 so it's gonna be very simple but when it comes to linked lists we first need to go to the head and then follow along the linked list after we come to the fourth fourth node then we'll be able to change that value so it would be much slower for example if the linked list consists of like 1,000 nodes then we'll have to do that process a thousand times if you want to change the third the last node so you might want to question then why would we use a linked list so if you use a linked list adding or deleting an element at the beginning of the the list would be quite simple so like in that case it's we say it's gonna take it takes constant time so the time for adding something at the beginning wouldn't matter would be the same whether we're dealing with one or two nodes or a thousand nodes so in that case it's going to vary it's going to be very fast and in some applications that can be very useful when I was mentioning arrays remember how I said that in an array the the locations are physically next to each other and the addresses are fixed so in that case when we want to add something at the beginning of an array all the values will have to shift and that can be a bit more complicated than than a linked list so that's an example of why a linked list would would be better than an array and here you can see this is a linked list called a doubly linked list so what we saw here at like before was a singly linked list each node only contained the address of the next but in a doubly linked list each node will contain the address of the next and also the previous and in this case adding an element at the end of the linked list would be easier than a singly linked list okay so I think that's that's enough for the basics of linked lists let's we're going to try to implement a linked list in go first will we need to describe a node so tight and a node needs a data and we're just going to use a single number and it also needs to hold next which is the address of the next node and so that needs to be a pointer okay next we need to describe the list quotient list and here it needs to hold a head and this just has to be an address of the note the pointer of the node which is the head so a good thing about link list is you don't need to contain the whole list you just need to contain the head of the list and length okay that's going to indicate how long the linked list is right now we can't do much because we're not able to put in the the nodes inside the linked list yet so let's make a method that can do that so funk and the receiver is going to be a linked list and we'll call it prepend and it'll gonna take a node to be added at the front okay so if you're new to go this is how you define a method this is called a method receiver and in ingo like unlike other object-oriented programming languages in go you define the method outside of the struct and this is how you indicate it that it's for linked lists you put a receiver this is called a receiver and here you can see that the receiver is a pointer this means you want to actually make modifications to this receiver if you just put it as a value just a value receiver then we're just going to be working on a copy of it so we want to actually work on the actual receiver like change the the values and stuff and whatnot so we need to put it as a pointer and in most cases you'll see a pointer point to receive and more often than a value receiver I think inside the method we'll make a temporary place called second and put the current head in a second then set the new node as the head which is M N and let the new head point to the old head which is second so and we need to increase the length because we added something all right now we can do a short test because we can add noise to the linked list we're gonna need a function me and I'm going to make a new list called my list so I just created a new list and now I need to create some notes okay we need to pass in a pointer and that is what this that is what this is for it needs to be a pointer and then we are able to prepend it my list and I do maybe and after that I'm just gonna print out the my list just put the whole thing okay I think it's all good I'm gonna run it okay so this is we just printed out my list and this you can see that that's the address of node 3 because we added that at the last so that would will be the head and three would be the length of my list okay this is just a test I'm gonna go back you

Channel: Junmin Lee

Views: 14,738

Keywords: linked list, data structures, golang, linked list in go, leetcode, singly linked list, doubly linked list, golang tutorial, golang for beginners, linked list in golang, linked list go, linked list golang

Id: 1S0_-VxPLJo

Length: 8min 45sec (525 seconds)

Published: Mon Jun 15 2020