Circular Linked List Tutorial - Why Use a Circular List?

Key Takeaways

alright so in the previous video we talked about singly linked list now these are great and we just talked about the advantages of them over arrays and other types of data structures now I want to introduce the concept here of circular lists and this is going to apply to doubly linked lists which we'll talk about in the next video as well now I want you to think why we would use a circular list and what a circular list even is now what I mean by circular is that this last node here rather than pointing to null which it's been doing before because there's no next note after it it actually points back to the head node of our list so what actually happens here is that this next node is always pointing back to the head now before you continue on with this video I seriously urge you to just take a second and think why we would even want to do this can this offer speed be a thing can it make it easier to access things why would we do this and what way we need to modify even in the node or in the SSL clasp to make this worthwhile and then I'm gonna explain the answer in just a second all right so I hope you guys have thought about this now what I'm gonna do is just modify this sll class here and hopefully what I start doing will make sense to you guys but I want you to kind of figure it out on your own so this here is called the head of our list right and this is the node that right now we're storing in sll all we need is access to this head node and we can successfully traverse all of the different nodes until we reach the end node now immediately some of you might have started thinking well if we have this last node our traversal from the previous video isn't gonna work because in that traversal we had a while loop and we said something like wow current dot next doesn't equal no or while current so if you get rid of that dog next doesn't equal no but now we're never gonna have a null value because this last point here is always gonna be pointing to the head so this is why I'm gonna make a modification to my class and hopefully you guys can understand why in just a second and then I will we'll see how we can change this while loop to do a proper traversal of a circular list so what I'm gonna do now is rather than keeping track of what we called the head node I'm actually gonna keep track of the tail node in my SS l-class so what I want to do is I'm actually gonna have this tail node being pointed to by this tail attribute and rather than carrying it with the head which I don't care about anymore I'm just gonna carry with the tail now the reason I'm gonna do this is because if I have reference to the tail node that means that I actually have reference to the head node so by having reference to this this one here I also have reference to this now why is that good why wouldn't I just have reference to the head node well if I have reference to the front and the back of the list or the beginning or the end of the list that means I can perform operations on the beginning and the end of the list very quickly and that is something that is awesome to be able to do because previously if we wanted to say add something to the end of our list here well we we need to reverse the entire list to be able to do that and that would take o of n time but now if we have reference to this tail node since it points back to the head node if I want to add something at the beginning all I need to do and I'm just gonna erase a few things here to make this a little bit cleaner while I do this all I need to do if I want to add a new node at the beginning is make this pointer here I'm just going to erase it point to that new node so let's say I want to add a new node I'm just gonna draw it small so we can actually see it here say that's five and this is its next property well what I do is I set this node to be equal to tail dot next which is actually going to be equal to the head node so I pointed here so the next property points to there and then I change what we originally was pointing from there to point to this new node so I say you know what this next property here we're gonna point that to this new node and now I've successfully added something at the beginning of the list but now what if I want to add something to the end of the list so let's reverse all this and let's change and now see how you add something to the end so let's pretend this is circular right now and I want to add something to the end well I have reference this tail node I know where this tail node is so all I need to do is add a new node let's say we'll add it down here we'll call this one maybe value nine and I set its next property to the first node in my list so I set it to the head node or in this case the tail dot next right so tail dot next that's what I set it equal to the next property so this points over here to this and now all I do is I change this pointer on the end node to point to this new node which is gonna be the end node in our list so I know this looks kind of confusing now but anyways that goes to there so now this one here is now our new tail reference and we now point tail to here this new node and now since this one points to the head node it works the exact same and if I want to add something after it that's how I do it I simply just repeat that process if I want to add something before well I have access to this head node so I can add a new node pointing to that and then point the new node to this head node right and that's how we do it with a circular list now this offers a ton of advantages because that means that whenever we want to add something to the end of the list we no longer need to traverse the entire list and that is the reason that we use a circular lists are simply adding that one extra pointer that goes from the tail to the head and keeping reference of the tail instead of our head we're able to get that massive speed advantage while still using a singly linked list and not using a ton of memory in our computer which is one of the disadvantages of a doubly linked list which we'll talk about later so anyways now that we've done that let's kind of talk about how we can implement some of these methods with a little bit of pseudocode in case anyone's confused so I realized in the last video I was kind of cutting off some of the code on my webcam in the bottom right hand corner so I'll try to make sure it doesn't cut off here but if you haven't noticed my handwriting is absolutely horrible so anyways let's now try to write a method that could add something to the beginning of our list so let's say we want to add first that's the method we want to write now for our sll class well we have this tail node so what should we start by doing well we don't need to traverse the list because all we need to do is just change around a few pointers so what we're gonna start by doing is creating a new node so we'll say like N equals node and we'll say n dot value equals I don't know let's set it equal to a value of five and then all we can do is say n dot next is equal to in this case it's gonna be tail dot next right and I'll talk about that in a second but tail dot next because tail dot next is this head node and we're adding to the beginning we the next property of our new head node to be the the current head node right the first thing that's actually in our list right now so we said this next property of this node to go to here my name is hope that makes sense all right so now that we've done that what we can do is change this last node so this next property here on this one to point to our new node and then that's actually all we need to do and we don't even need to mess with the tail so now we're gonna say is tail dot next equals n and now what we've successfully done is we've slotted in a new node value v we pointed it over here to seven and that we've changed this pointer so scratch that off to go to this new node and this now will be our head node and since we keep track of the tail and tail dot next as this makes sense everything works as planned and that is how we write the pseudocode to add something to the beginning of the list all right so now what about the end and this is the advantage that we're gaining because we already knew kind of how to do that before but now we're gonna have to just change a little bit different things to add to the end here to make it all make sense so let me get this eraser out here and get rid of everything all right so let's erase I didn't want to do that let's get the stroke eraser okay let's remove actually now let's go back to the pointer okay so what we want to do now sorry about that is add a new node to the end so how do we do that well what we need to do is we need to change a few pointers around so firstly we need to make sure that we don't lose this head node so that's an important thing when we add this new node in and we point to it or we don't point to it we got to make sure we don't lose this head node so what I'm going to start by doing is creating a new node so I'm gonna say N equals node and then we'll say n dot value and maybe this time it equals negative one all right now the first thing we do so we've just created this new node I'll try to draw it so you guys can actually see it as a value of negative one and it has this next player we're gonna set its next pointer equal to the head node to start so that we don't lose this head node so we're gonna say n dot next equals tail dot next so that means now we have a pointer going here to the head node because tail dot next is that so this is pointing there now what we can do is well we can change the pointer of tail tail dot next to go to this new node so now we'll say tail dot next equals n all right so now let's go here let's go to stroke eraser and we'll erase this pointer and now what we've successfully done is we've changed the tail to point two here as our next node which is gonna be the last node in our list all right awesome and now what's the last step we need to do what we need to say that this is now gonna be the new tail because this has the pointer to the head and it's gonna be the last element so what we do for that is we say tail equals n and that's all we need to do to set this and add that to the end of the list and that is the massive advantage of circle circular lists is that you're able to access both the front and the back element which means you can apply operations at the front and end of the list in the same time complexity of constant time now the only thing to note here is that if removing an element from the end of the list it still takes o n time now the reason that happens is because if you think about this say we want to remove this last element here which is actually the tail element right this is our tail so I'll just write tail if I want to remove this what I need to do is I need to find the node before it that points to it and change its pointer to go to the head node so to do that I actually need to traverse the entire list and that's because we only have this linked forwards which means that I can't by having the tail element access the element before it which means I can't access that pointer so if I want to remove an element I don't know why that's happening anyways if I want to remove an element from the end of the list or I want to remove the tail element that still takes o n time but if I want to remove an element from the beginning of the list that isn't going to take Oh n time because all I need to do to remove that is change the pointer here to be the element that it's pointing to which we can do because we have access to that front element as well as this tail so anyways that has been it for circular lists I hope you guys learned a little bit in the next video we will talk about doubly linked lists which are more complex and they have their own advantages over singly linked lists you guys have any other data structures you'd like to hear below please let me know and with that being said make sure to hit the like button and subscribe to the channel for more videos