[MUSIC PLAYING] DOUG LLOYD: All right. So if you just finished that video on singly-linked lists sorry I left you off on a bit of a cliffhanger. But I'm glad you're here to finish the story of doubly-linked lists. 

So if you recall from that video, we talked about how singly-linked lists do attend our ability to deal with information where the number of elements or the number of items in a list can grow or shrink. We can now deal with something like that, where we couldn't deal with it with arrays. 

But they do suffer from one critical limitation which is that with a singly-linked list, we can only ever move in a single direction through the list. And the only real situation where that can become a problem was when we were trying to delete a single element. And we didn't even discuss how to do it in a singly-linked list in pseudocode. It is certainly doable, but it can be a bit of a hassle. 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. 

Again, if you're not going to be deleting single elements from the list-- because we're adding an extra field to our structure definition, the nodes themselves for doubly-linked lists are going to be larger. They're going to take up more bytes of memory. And so if this is not something you're going to need to do, 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 [INAUDIBLE] 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. 

So again, this was the diagram to start with. This was our chain. We need to skip over 13, but we need to also preserve the integrity of the list. We don't want to lose any information in either direction. So we need to rearrange the pointers carefully so we don't break the chain at all. 

So we can say 9's Next pointer points to the same place that thirteen's Next pointer points right now. Because we're eventually going to want to skip over 13. So wherever 13 points next, you want nine to point there instead. So that's that. And then wherever 13 points back to, whatever comes before 13, we want 10 to point to that instead of 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 both singly- and doubly-linked lists, as we've seen, support really efficient insertion and deletion of elements. You can pretty much do it in constant time. What did we have to do to delete an element just a second ago? We moved one pointer. We moved another pointer. We freed X-- took three operations. It always takes three operations to delete that node-- to free a node. 

How do we insert? Well, we're just always tacking on the beginning if we're inserting efficiently. So we need to rearrange-- depending on if it's a singly- or doubly-linked list, we might need to do three or four operations max. But again, it's always three or four. It doesn't matter how many elements are in our list, it's always three or four operations-- just like deletion is always three or four operations. It's constant time. So that's really great. 

With arrays, we were doing something like insertion sort. You probably recall that insertion sort is not a constant time algorithm. It's actually pretty expensive. So this is a lot better for inserting. But as I mentioned in the singly-linked list video, we've got a downside here too, right? We've lost the ability to randomly access elements. We can't say, I want element number four or element number 10 of a linked list the same way that we can do that with an array or we can just directly index into our array's element. 

And so trying to find an element in a linked list-- if searching is important-- may now take linear time. As the list gets longer, it might take one additional step for every single element in the list in order to find what we're looking for. 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. But more on that in another video. 

I'm Doug Lloyd. This is CS50.