Linked Lists Introduction

Key Takeaways

welcome back today we're going to talk about singly and doubly link lists one of the most useful data structures out there this is part one of two in the second part we will be looking at some source code on how to implement a doubly linked list so for today's outline in the first section we're going to answer some basic questions concerning singly and dou Link lists namely what are they and where are they used next we're cover some terminology concerning link list so everyone knows what I mean when I say the headed link list versus the tail of the link list then last in the discussion we'll talk about the pros and cons of using singly and doubly linked lists then how to insert and remove elements from both singly and dou Link list as well as some source code so stay tuned all right discussion so what is a link list link list is a sequential list of nodes that hold data which point to other nodes also containing data so below is an example of a singly link list containing some arbitrary data notice that every node has a pointer to the next node also notice that the last node points to null meaning that there are no more nodes at this point the last node always has a null reference to the next node for Simplicity I will omit this in the following slides okay so where are link lists used one of the places that get used the most is actually in the uh abstract data type implementation of lists stacks and cues because of their great time complexity for adding and removing elements you also see link lists and things like circular lists making the pointer of the last node point to the first node so circular link lists are used to model uh repeating event Cycles maybe like having a round robin ordering on a bunch of elements or representing corners of a polygon so definitely a lot of uses there link list can also be used to model Real World objects such as a line of train carts that could be useful and moving on to some more advanced examples we also heavily use use Link lists in uh hashtable separate chaining and for adjacency lists in graphs we'll get to those in a later video okay A bit of terminology surrounding link list first thing you need to know when creating link list is we always maintain a reference to the head of the link list this is because we need somewhere to start when traversing our list we give a name to the last element of the blink list also this is called the tail of the list then there are also the nodes themselves which contain pointers pointers are also sometimes called references and these pointers always point the next node you should also know that the nodes themselves are usually represented as structs or classes when actually implemented we'll get to this when we look at the source code okay singly versus dou lengthly so concerning the kinds of Link lists that there are there are two types singly linked and doubly linked singly link lists only contain a pointer to the next node while doubly link lists not only contain a poter to the next node but also to the previous node which makes it quite useful sometimes this is not to say we cannot have triple or quadruple length lists I just would to know where to place additional pointers pros and cons of dou Link list so there are tradeoffs between picking a singly and a doubly link list what are they if we look at the singly link list we observe that it uses less memory why well pointers to nodes can actually take up a lot of memory if you're running on a 64-bit machine references use 8 bytes on a 32-bit machine four bytes each so having a singly link list means you only need one pointer for each node hence twice as much memory is saved a downside however is that you cannot access previous elements because you don't have access to them we need to Traverse from the head of a link list all the way up to the previous node to find it now concerning doubly link list well a great Pro is that having access to the tail we can easily Traverse the list backwards something we can't do with a singly link list also having a reference to a node you want to remove you can remove it in constant time and patch the hole you just created because you have again access to both the previous and the next nodes this is something you cannot do with a singly link list you would leave the list severed in two a downside however to the doubly link list is it does use up twice as much memory okay let's go into some implement ation details on how we can create link list and remove elements from link lists starting with singly link list so here is a singly link list I've outlined where the head and the tail is now we want to insert 11 at the third position where seven is currently let's walk through an example so the first thing we do is we create a new pointer which points to the Head this is almost always the first step in all link list operations now what we're going to do is seek up to but not including the node we want to remove so if we seek ahead we advance our traverser pointer setting it equal to five's next node which is now 23 and now we're actually ready already where we need to be to insert the next node so we create the next node that's the green node 11 and and we make 11 11's next pointer 7 and the next steps that change 23's next pointer to be 11 remember we have access to 23's next pointer because we have a reference to it with the traverser okay and now we flatten out the list we can see that we've correctly inserted 11 at the right position and we're done okay all right time to insert with a doubly link list this is much trickier because of all the pointer flying around but it's the exact same concept notice that the dump doubly linked list not only has pointers to the next node but also to the previous node we also have to change those in the insertion phase okay create a traverser pointer which points to where the head is and Advance it until you are just before the insertion position so we Advanced the traverser by one and now we're just before the node so we stop traversing let's create the new node which is node 11 Point 11's next pointer to equal 7 also Point 11's previous pointer to be 23 which we have a handle on because of the traverser now we make Seven's previous pointer equal to 11 so we can go backwards from 7 to 11 and the last step make 23's next pointer equal to 11 this is so that we can go forwards from 23 to 11 so in total remark that we changed exactly four pointers so if we flatten out the list we can see that 11 has been inserted in the correct position all right now how to remove elements from a singly linked list so suppose we want to remove the node with a value nine how do we do this well the trick we're going to use is not to use one pointer but two you can can use one but for visual effects it's easier to show you how it is done by using two so we create pointers Trav 1 and Trav two for traverser one and traverser 2 respectively so traverser one points to the head traverser two points to the head's next note now we're going to do is Advance Trav 2 until till we find the node we want to remove while also advancing Trav 1 okay we have found node 9 so this is the stopping point I'm going to create another pointer to the node we wish to remove so we can deallocate its memory later okay so now I had have advanced Trav 2 to the next node and node 9 has turned red I've done this to indicate that this will at this point node 9 is ready to be removed I'm just keeping it around for the visual effect okay so now set Trav 1's next pointer to be equal to Trav 2 and now it is an appropriate time to remove uh the temporary pointer because we're doing nothing with it and there temp has been deallocated make sure you always clean up your memory to avoid memory leaks this is especially important in C and C++ and other programming languages where you manage your memory now you can see that nine is gone and our singly link list is shorter okay now for the last bit of implementation let's look at how to remove nodes from a dou linked list which is actually easier in my opinion to removing from singly link lists the idea is the same we seek up to the node we wish to remove but this time we only need one pointer uh I mean one traverser pointer because each node the singly linked list has a reference the last node so we don't need to manually maintain it like we did with the singly link list so let's start Trav at the very beginning and seek until we hit nine okay we've reached nine and we want to remove it from the list to do this set Four's pointer to be equal to 15 we have access to four and 15 because they are travs previous and next pointer respectively same similarly set 15's previous pointer to equal four notice that Trav is now red meaning it is ready to be removed so we get rid of Trav and now if we flatten out the dou length list we see that it no longer contains nine let's do a bit of complexity analysis on length lists how good actually are length lists on the left column we have singly length lists and on the right doubly length lists the complexity for searching in a length list is linear in the worst case because if the element we're looking for is not there we have to Traverse all of the N elements inserting at the head though is constant time because we always maintain a pointer to the head for a length list and hence we can add it in constant time similarly for the tail to remove the head of a singly linkless and a doubly length L is also constant time again because we have a reference to it so we can just remove it and Advance the head by one however removing from the tail is another story it takes linear time to remove elements from a singly link list can you think of why well even if we do have a reference to the tail in a singly linked list we can remove it but only once because we can't reset the value of what the tail is so we have to seek to the end of the list and find out what the new tail is equal to double link lists however do not have this problem since they have a pre a pointer to the previous node so we can continually remove noes from the tail and finally removing somewhere in the middle is also linear time because in the worst case we would need to seek through n minus1 Elements which is linear all right time to have a look at some source code I have implemented a doubly linked list we can have a look at in some detail also if you want the source code for the doubly length lists in the next video have a look at the code repo provided below it contains all the data structures I will be covering in this series guys thanks for watching I will see you in the next video