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