Original subtitles

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