Doubly-Linked Lists

Loading...

来自 University of California San Diego 的课程

Data Structures

1516 个评分

University of California San Diego

Data Structures

1516 个评分

课程 2（共 6 门，Specialization 数据结构与算法）

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!

从本节课中

Basic Data Structures

In this module, you will learn about the basic data structures used throughout the rest of this course. We start this module by looking in detail at the fundamental building blocks: arrays and linked lists. From there, we build up two important data structures: stacks and queues. Next, we look at trees: examples of how they’re used in Computer Science, how they’re implemented, and the various ways they can be traversed. Once you’ve completed this module, you will be able to implement any of these data structures, as well as have a solid understanding of the costs of the operations, as well as the tradeoffs involved in using each data structure.

Singly-Linked Lists9:02

Doubly-Linked Lists4:39

与讲师见面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

There is a way to make popping the back and adding before cheap.

Our problem was that although we had a way to get from

a previous element to the next element, we had no way to get back.

And what a doubly-linked list says is, well, let's go ahead and

add a way to get back.

So we'll have two pointers, forward and back pointers.

That's the bidirectional arrow we're showing here conceptually.

And the way we would actually implement this is,

with a node that adds an extra pointer.

So we have not only a next pointer, we have a previous pointer.

So this shows for example that the 10 element has a next

pointer that points to 4 but a previous pointer that points to 7.

So at any node we can either go forward or we can go backwards.

So that means if we're trying to pop the back, that's going to work pretty well.

What we're going to do is update the tail pointer to point to the previous element

because again we ca get there in an O(1) operation.

And then update its next pointer to be nil and then finally remove the node.

So that's O(1).

So if we have a doubly linked list it's slightly more complicated (our code) because

we've got to make sure to manage both prev pointers as well as next pointers.

So if we're pushing something in the back, we'll allocate a new node.

If the tail is nil, which means it's empty, then we just have a single node

whose prev and next pointers are both nil and then head and tail both point to it.

Otherwise, we need to update the tail's next pointer for

this new node, because we're pushing at the end and

then go update the prev pointer of this new node to point to the old tail and

then finally update the tail pointer itself.

Popping the back, also pretty straightforward.

We're going to again check to see whether this is first an empty list,

in which case it's an error.

A list with only one element, in which case it's simple.

Otherwise we're going to go ahead and

update our tail to be the prev tail, and the next of that node to be nil.

Adding after, fairly simple again we just need to maintain the prev pointer but

adding before also now works in the sense that we can allocate our node,

our new node and

its prev pointer will be the prev pointer of the existing node we're adding before.

We splice it in that way and

then we'll update the next pointer of that previous node to point to our new node.

And finally, just in case we're adding before the head,

we need to update the head.

So in a singly-linked list, we saw the cost of things.

Working with the front of the list was cheap,

working with the back of the list with no tail, was all linear time.

If we added a tail, it was easy to push something at the end,

easy to retrieve something at the end, but hard to remove something at the end.

By switching to a doubly linked list,

removing from the end (a PopBack) becomes now an O(1) operation,

as does adding before which used to be a linear time operation.

One thing to point out as we contrast arrays versus linked lists.

So in arrays, we have random access,

in a sense that it's constant time to access any element.

That makes things like a binary search very simple,

where we start searching in the middle, and then tell (if we have a sorted array),

and then can decide which side of the array we're on.

And then, go to one side or the other.

For a linked list, that doesn't work.

Finding the middle element is an expensive operation.

because you've got to start either at the head or the tail and

work your way into the middle.

So that's an O(n) operation to get to any particular element.

Big difference in between that and an array.

However, linked lists are constant time to insert at or remove from the front,

unlike arrays.

What we saw in arrays, if you want to insert from the front, or

remove from the front, it's going to take you O(n) time because you're going to have to move

a bunch of elements.

If you have a tail and doubly-linked,

it is also constant time to work at the end of the list.

So you can get at or remove from there.

It's linear time to find an arbitrary element.

The list element are not contiguous as they are in an array.

You have separately allocated locations of memory and

then there are pointers between them.

And then, with a doubly-linked list it's also constant time to insert

between nodes or to remove a node.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取