So if you find yourself in a situation where you're trying to delete single elements from the list or it's going to be required that you'll be deleting single elements from the list, you might want to consider using a doubly-linked list instead of a singly-linked list.
Because doubly-linked lists allow you to move both forwards and backwards through the list instead of just forward through the list -- just by adding one extra element to our structure definition for the doubly-linked list node.
you might decide it's not worth the trade off to have to spend the extra bytes of memory required for a doubly-linked list if you're not going to be deleting single elements. But they're also cool for other things too.
So as I said, we just have to add one single field to our structure definition -- this notion of a Previous pointer.
So with a singly-linked list, we have the value and the Next pointer, so the doubly-linked list just has a way to move backwards as well.
Now in the singly-linked list video, we talked about these are five of the main things you need to be able to do to work with linked lists. And for most of these, the fact that it's a doubly-linked list isn't really a big jump.
We can still search through by just moving forward from start to end.
We can still create a node out of thin air, pretty much the same way.
We can delete lists pretty much the same way too.
The only things that are subtly different, really, are inserting new nodes into the list, and we'll finally talk about deleting a single element from the list as well.
Again, pretty much the other three, we're not going to talk about them right now because they're just very minor tweaks on the ideas discussed in the singly-linked list video.
So let's insert a new node into a doubly-linked list. We talked about doing this for singly-linked lists as well, but there's a couple of extra catches with doubly-linked lists. We're passing in the head of the list here and some arbitrary value, and we want to get the new head of the list out of this function. That's why it returns a dllnode star.
So what are the steps?
They are, again, very similar to singly-linked lists with one extra addition.
We want to allocates space for a new node and check to make sure it's valid. We want to fill that node up with whatever information we want to put in it. The last thing we need to do-- the extra thing we need to do, rather -- is to fix the Previous pointer of the old head of the list.
Remember that because of doubly-linked lists, we can move forward and backwards-- which means that each node actually points to two other nodes instead of just one.
And so we need to fix the old head of the list to point backward to the new head of the linked list, which was something we didn't have to do before. And as before, we just return a pointer to the new head of the list.
So here's a list. We want to insert 12 into this list. Notice that the diagram is slightly different.
Each node contains three fields -- data, and a Next pointer in red, and a Previous pointer in blue.
Nothing comes before the 15 node, so its Previous pointer is null. It's the beginning of the list. There's nothing before it. And nothing comes after the 10 node, and so it's Next pointer is null as well.
So let's add 12 to this list. We need malloc space for the node. We put 12 inside of it.
And then again, we need to be really careful not to break the chain. We want to rearrange the pointers in the correct order.
And sometimes that might mean -- as we'll see particularly with delete --that we do have some redundant pointers, but that's OK.
So what do we want to do first? I would recommend the things you should probably do are to fill the pointers of the 12 node before you touch anybody else. So what is 12 going to point to next? 15.
What comes before 12?
Nothing.
Now we've filled the extra information in 12 so it has Previous, Next, and value.
Now we can have 15-- this extra step we were talking about -- we can have 15 point back to 12.
And now we can move the head of the linked list to also be 12.
So it's pretty similar to what we were doing with singly-linked lists, except for the extra step of connecting the old head of the list back to the new head of the list.
Now let's finally delete a node from a linked list. So let's say we have some other function that is finding a node we want to delete and has given us a pointer to exactly the node that we want to delete. We don't even need-- say the head is still globally declared. We don't need head here. All this function is doing is we've found a pointer to exactly the node we want to get rid of. Let's get rid of it. It's a lot easier with doubly-linked lists.
First-- it's actually just a couple things. We just need to fix the surrounding nodes' pointers so that they skip over the node we want to delete. And then we can delete that node.
So again, we're just going through here. We have apparently decided that we want to delete the node X. And again, what I'm doing here -- by the way -- is a general case for a node that is in the middle.
There are a couple of extra caveats that you need to consider when you're deleting the very beginning of the list or the very end of the list. There's a couple of special corner cases to deal with there.
So this works for deleting any node in the middle of the list-- one that has a legitimate pointer forward and a legitimate pointer backward, legitimate Previous and Next pointer.
Again, if you're working with the ends, you need to handle those slightly differently, and we're not going to talk about that now. But you can probably figure out what needs to be done just by watching this video.
So we've isolated X. X is the node we want to delete from the list.
What do we do?
First, we need to rearrange the outside pointers.
We need to rearrange 9's next to skip over 13 and point to 10-- which is what we've just done. And we also need to rearrange 10's Previous to point to 9 instead of pointing to 13.
Now notice, if you follow the arrows, we can drop 13 without actually losing any information.
We've kept the integrity of the list, moving both forward and backward.
And then we can just sort of clean it up a little bit by pulling the list together.
So we rearranged the pointers on either side. And then we freed X the node that contained 13, and we didn't break the chain. So we did good.
Final note here on linked lists.
So there's trade offs. There's a bit of a pro and con element here.
And doubly-linked lists are not the last kind of data structure combination that we'll talk about, taking all the basic building blocks of C an putting together.
Because in fact, we can even do better than this to create a data structure that you might be able to search through in constant time too.
