Learn
Filter by interest
Teach
Account

## Easy to Advanced Data Structures

00:14:42
Share the link to this class
Copied

## Transcript

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.

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.