Singly Linked Lists Tutorial - What is a Linked List?

Key Takeaways

so now let's talk about singly-linked list now this a very common and honestly commonly confused data structure that is much faster in certain operations than an array now the major differences between this and an array are the way that it's stored in memory as well as the fact that it's dynamically allocated now it can also insert and delete items faster but the major disadvantage is that you can't index items randomly so using like 0 1 like we can't index by numbers and that's gonna take longer to find than an array so it's gonna run an O and time linear time as opposed to constant time like arrays do but anyways what is a singly linked list so it is comprised of what we call nodes now a node has a value which is the actual value of the item so maybe like Tim Joe one true whatever you're storing in the singly linked list and then it has a property which is called next and this is what we call a pointer to the next node in the list and you guys are gonna see how this works in a second now when we actually implement and create our own singly linked list what we typically do is we write a class I'm just gonna stay do SSL for short so singly linked list and this has a few different properties it has a head property which points to the first node in our singly linked list and then what it does is well it can have a like a counter node keeping track of how many nodes are in our list but it also just has a bunch of methods so maybe something like add maybe something like remove and maybe find and then I don't know we'll add another one says add first you can add as many kind of methods this as you want and make them as customizable as you want now when we create this singly linked list it looks something like this I'm gonna start drawing it these squares are nodes ok so each of these squares represents a node in this the first square is what we call our head node and it is what it's going to be stored here in this SSL singly linked list class now when we start our singly linked list we start head pointing to the value null and then when we originally add our first node we will create a new note and point head to that it's just a quick nuance there in case anyone's confused on how we start with that head but these nodes have two properties they have a value and they have a next property so the value is usually will be right in the middle so maybe something like seven is the actual value it's storing and then the next property means what it's doing is it's pointing to another node so what next is actually storing is this next node and this next node is an object just like the previous node and maybe it holds a value something like negative three and it again has a next property this next property points to the next node and then this node has a value maybe say one and then this has a next property and this next property points to you in this case and no because we don't have any more nodes in our list and that is as simple as this is now looking at this maybe you can kind of understand why this is faster in certain operations than an array now first of all this is dynamically allocated which means that whenever you add a new node all you need to do to add a new node to this is simply find the last node here so loop through our list traverse find this last node which is one and then set its next property to a new node that has whatever value in it that we want so now we'll say our next value is maybe eight and then this next property well goes to the next node which is no because there's none left and that's all you need to do to add a new node so it's a lot faster than having to shift every single element now that being said we still need to find this last node in the list to added to so we have to search for that but it is faster than an array to add that now same thing here if we want to insert a node somewhere else so let's say we want to insert a node I'm gonna keep that no there and we want to insert it in between three and one so I want to insert that same node which was eight has that next property well all I need to do to do this rather than shifting every single element in memory like we did with arrays is change the pointers on these nodes so I'm gonna change the pointer on this node to be equal to eight and then I'm going to add a pointer from eight to one in that way now when we loop through a list well we go seven negative three eight and one and it doesn't change the memory location of these nodes which saves us a lot of time so I'll change this pointer so it goes down to eight and then eight now is going to point to one and now that is the new order of our list if we want to insert more things it's as easy as changing the pointers and again I'm calling these pointers but it's just pointing to these nodes and these nodes are these little black boxes that have the value and have next now another very fast operation on these is adding to the beginning of the list and I'll let you kind of guess why that is like say I want to add an item to the very beginning of this list all I need to do to do that is put a node maybe we put one up here I'm just drawing it small because it's kind of hard to put here let's say the value is negative one now all I do is I add a pointer to this head value and I repoint head so now it goes to this and now when I want to access seven all I have to do is traverse through negative one then seven then negative three and so on and now this is the head node and the first note in our list it's very fast to do that because all you need to do is just point to the head and then change head to be this new node that we've added in I'm very fast right and that's why it's really really nice and a lot of people like using it now another massive advantage of the singly linked list is they don't use a lot of memory because they only have these pointers that are going to one on their note and a value as opposed to a doubly linked list which is or not doubly double linked list which is something that we'll talk about in another tutorial but anyways that is kind of how you know you add remove things and add to the front now I'm gonna show you with a little bit of pseudocode how we can actually do these operations so add remove find add first because a lot of people get confused on how that works so let's kind of just make this list a little bit simpler now and get rid of all those insertions I was doing and hopefully you understand how this Poynting works this head is all that we need to keep track of in SS sll since we have accesses head node all we actually need to do is keep going from the neighbors so the next of head and the next of that next and the next of that next of that next to look through all of the different elements that are inside of our linked list so I'm gonna do this with a while loop it's very easy to do and I'm sure you guys can probably figure it out on your own but essentially we're gonna start and use a variable get out of my eraser here that's called current and I say current equals head what I'm gonna do is make the condition on my while loop while current does not equal no so immediately this catches for us the first condition which is we have nothing in our list so if we want to be traversing the list and I'm just showing you a very basic traversal here if there's nothing in our list we won't bother even looking because current is gonna be equal to no right now if it's not and we do have a node then we can repeat the next process so let's say we're looking for a certain value and maybe we want that value to be represented as I don't know Val equals 5 or something we're searching for that value in our list well what we can do is we can say if and in this case current dot value equals equals Val then we can simply break out of this loop because we found what we're looking for and then maybe we print out where it is or whatever we want to do right but that's how we can like search for a value now once we've done that so we've checked this condition we didn't break out of the loop the next step is to simply go to the next node so we say current is gonna be equal to current dot next now I'll walk you through this and kind of run this whole piece of code for you but this is very straightforward all we're gonna do is keep going to the next node until eventually there is no next node to go to and once we hit that no condition we've successfully traversed through our entire list and this is very easy to do so when you want to add something remove something find something you start with a basic traversal like this once you find the node that you want then you can do whatever operation there you need to do and then break out of the while loop but this is how you find whatever node and once you know how to find a node and Traverse this you can do any operation you want so we're gonna say value goes 5 so if we're looking for value equals 5 in here let's walk through how this works so current equals head that means head which is this right now is the first thing that we're looking at now if current value equals equals Val break does it the seventh equal five no it doesn't so what's the next thing we do we say current equals current next which now means current is negative three because the next value of head is three all right so we're actually pointing to this node right like this whole thing is what we're pointing to in same here we're pointing to this whole node now we have this node so what we do is say well current does not equal no well this one isn't no if current value equals Val break does it no it doesn't so now we move to the next node that is the next node from here so now we're looking at one and you guys get the point on how this traversal works we just keep going next next next ex next until eventually we come here we look at no and then we go no and we break and that is how you traverse a singly linked list now knowing this operation we can apply and Cree add/remove find and add first very easily if we want to add first well we don't even need to traverse because we actually know where that first element is so let's write the code to add the first element into our what do you call it singly linked list yeah I'm just gonna get the larger a syrup to get rid of this faster hopefully all right so if we want to write the code to simply add a new node at the beginning of our list and we want to write add first well to do that is very easy all we're gonna do is say in this case I'll say N equals node like this and then maybe we'll set a value for it so we'll say the value is like 10 maybe we pass that into a parameter however this node is working either we're setting the value next we do that or you know to make this more transfer and we say N equals node say n talk value equals whatever value we're adding maybe at 7 or maybe it's 8 okay so we'll change that to 8 all right so now that end up value is 8 all we need to do is point the head to end value and then point n sorry - whatever head is so we can say n dot next equals head right because now we're just gonna say if we have this new node we say eight we'll start by pointing this to here and now that we have that all we need to do is change the pointer of head to 8 so now we say head equals n and now our head node is n which is the new node we added which is up here 8 is now pointing to 7 and we completely have a singly linked list and we've just changed the first element and that very quick there's only four lines of code right can even do this unless if we had it set up Prabhu all right so now that we've done that let's talk about removing a note we're finding and then removing a note so let's say we want to remove the note negative 3 there and I'll leave that aid in there for now so we can understand how this works well we'll start by doing a traversal of our list and we need to do this because we need to have access if we're going to remove 3 to the node before that and the note after that so we need to perform a traversal so that we can stop at the node before it and change the pointers accordingly so that 3 is removed so what we'll do is that same thing that we've done before so we'll say I'll just say cur equals head we'll say wow cur does not equal null and now what we'll say is if cur dot next equals equals and in this case whatever element we're looking to remove so we'll say like R equals negative 3 for what we want to remove then what we will do is start changing the pointers so we're gonna change the pointer of whatever current is so the next value is equal to whatever this is next value is so all we need to do to remove 3 is go like that so now there'll be no pointer to 3 and then 7 we'll have the pointer to 1 so we won't have removed one that's all we need to do because if you get rid of what do you call it if you get rid of this 1 here I don't know why that's doing that no need to change this to that we get rid of this pointer nothing points to 3 even though 3 still points to 1 that doesn't matter because we'll never actually access 3 so what I do is just say cur dot next or not neck sorry yeah actually curved dot next is equal to whatever current dot next dot next now the way that this works is the next value on current is negative 3 right and this negative 3 points to 1 so all I do is say that current dot next which is now pointing to 3 is actually equal to whatever current next on next is which points to 1 so where since we're pointing to 1 there we just change this pointer to 1 and then that's all we need to do and then we can simply break out of this while loop and we have successfully removed the now if we reach a point where we've looped through everything current equals null then that means three did not exist and therefore it did not get removed now that's as easy as it is to remove and add things to a singly linked list