Welcome back. Today we're going to talk about singly and doubly linked lists one of the most useful data structures out there. This is part one of two and 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 doubly linked lists, namely, what are they and where are they used. Next, we'll cover some terminology concerning the linked list so everyone knows what I mean when I say the head linked list versus the tail of the weight class. 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 a loop linked lists as well as some source code so stay tuned. Alright, discussion. So what is the link list? linkless 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 linked list containing some arbitrary data. Notice that every node has a pointer to the next node.

Also notice that the last node points to no 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 linkless use? One of the places that get used the most is actually in the abstract data type implementation of lists, stacks and queues because of their great time complexity for adding and removing elements. You'll also see linked lists and things like circular lists.

Making the pointer of the last node points to the first node. So circular linked lists are used to model repeating events cycles, maybe like having a round robin ordering on a bunch of elements or representing corners with polygon. So definitely a lot of uses there. linked lists 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 linked lists and hash table separate chaining, and for adjacency, lists and graphs.

We'll get to those in a later video. Okay, a bit of terminology surrounding linked lists. First thing to know when creating a linked list is that we always maintain a reference to the head of the linked list. This is because we need somewhere to start when traversing our list. We give a name to the last element Think less also this is called a 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 structs or classes when actually implemented. We'll get to this when we look at the source code. Okay, singly versus doubly linked lists. So concerning the kinds of linked lists that there are, there are two types, singly linked and doubly linked.

Singly linked lists only contain a pointer to the next node, while doubly linked lists not only contain a pointer 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 the length list. I just wouldn't know where to place it. pointers, pros and cons of doubly linked lists. So there are trade offs. Between picking singly and a doubly linked list.

What are they? If we look at the singly linked list, we observe that it uses less memory. Why? Well, pointers to nose can actually take up a lot of memory. If you're running on a 64 bit machine references use eight bytes on a 32 bit machine four bytes each. So having a singly linked 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. Who would need to traverse from the head of the link lists all the way up to the previous node to find it. Now concerning doubly linked lists, well agreed Pro is that having access to the tail we can easily traverse the list backwards, something we can't do with a singly linked 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 notes. This is something you cannot do with a singly linked list you would leave the list separate into to a downside however, to the doubly linked list is it does use up twice as much memory.

Okay, let's go into some implementation details of how we can create link less than or remove elements from linked lists. Starting with a singly linked list. So here is a singly linked 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 linkless 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 traversal pointers, setting it equal to five 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 we make 11 elevens, next pointer, point to seven.

And the next steps that change 20 threes next pointer to be 11. Remember, we have access to 23 is next pointer because we have a reference to it with the traverser. Okay, and now we've flattened 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 within a doubly linked list. This is much trickier because of all the pointers flying around, but it's the exact same concept. Notice that a dump doubly linked list not only has pointers to the next node, but also to the previous note, we also have to change those in the insertion phase.

Okay, create a traversal pointer, which points to where the head is and advance it until you are just before the insertion position. So we advanced the traversal 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 elevens. Next pointer equal seven also point Clapton's previous pointer to be 23 which we have a head And along because of the traverser. Now, we make sevens previous points are equal to 11.

So we can go backwards from seven to 11. And the last step, make 20 threes next pointer equal to 11. This is so that we can go forwards from 23 to 11. So in total remarked that we changed exactly four pointers. So if we flatten out the list 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 use one But for visual effects, it's easier to show you how it is done by using two. So we create pointers, travel one and track two for traverser one and traverser two respectively. So traverser one points to the head traversal two points to the heads next node. Now we're going to do is advanced trap two until we find the node we want to remove, while also advancing trap one.

Okay, we have found node nine. 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 to have advanced traffic to to the next node node nine has turned red. I've done this to indicate that this will that at this point, node nine is ready to be removed. I'm just keeping it around for the visual effect.

Okay, so now that tribe one's next pointer to be equal to trap two. And now is an appropriate time to remove the temporary pointer because doing nothing with it and their temp has been de allocated. 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 linked list is shorter. Okay, now for the last bit of implementation.

Let's look at how to remove nodes from a doubly linked list. Which is actually easier in my opinion to removing from singly linked lists. The idea is the same, we sync up to the node we wish to remove, but this time we only need one pointer. I mean one traverser pointer. Because each node is a singly linked list has a reference the last node so we don't need to manually maintain it like we did with the singly linked 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 force pointer to be equal to 15 with access to four and 15 because they are tribes, previous and next pointer respectively. Similarly set 15th 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 doubly linked list, we see that it no longer contains nine.

Let's do a bit of complexity analysis on linked lists how good actually are linked lists. On the left column, we have singly linked lists and on the right doubly linked lists, the complexity for searching in a linked list is linear in the worst case, because if the element that 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 linked list and hence we can add it in constant time, similarly for the tail to remove the head of a singly linked list and a doubly linked list is also constant time. Again because we have a reference to it so we can just remove it and advanced the head by one. However, removing from the tail is another story. It takes linear time to remove elements from a singly linked list.

Can you think of Why? Well, even if we do have a reference to the tail in a singly linked lists, we can remove it but only once because we can't reset the value of what the tail is. So we had to seek to the end of the list and find out what the new tail is equal to. W linked list however, do not have this problem, since they have a pre a pointer to the previous node. So we can continuingly remove nodes 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 minus one 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 linked 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.