Explore
For Enterprise
Join for Free
Log In

浏览
搜索
企业版
登录
免费加入

Doubly-Linked Lists

Loading...

数据结构

加州大学圣地亚哥分校

4.7（2,267 个评分） | 97K 名学生已注册

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

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! Do you have technical problems? Write to us: coursera@hse.ru

查看授课大纲

您将学习的技能

Binary Search Tree, Priority Queue, Hash Table, Stack (Abstract Data Type), List

审阅

4.7（2,267 个评分）

5 stars
1,662 ratings
4 stars
489 ratings
3 stars
79 ratings
2 stars
14 ratings
1 star
23 ratings

VK

Jul 16, 2018

Amazing course.\n\nInteresting exercises help with learning and understanding of internal mechanisms basic data structures, how some of them work, the pros and cons of each.\n\nThanks!

SC

Feb 27, 2019

Perfect course for learning more about fundamental data structures, except for presentations on few difficult topics like splay trees, where explanations can be made more elaborate!

从本节课中

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
Michael Levin
Lecturer
Daniel M Kane
Assistant Professor
Neil Rhodes
Adjunct Faculty

脚本

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 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

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

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版
面向校园

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司