>> [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.