>> [音乐播放]
DOUG LLOYD：好吧。
所以，如果你刚刚完成的 视频单链表遗憾
我离开你关上一 悬念位。
不过，我很高兴你在这里完成 双链表的故事。
>> 所以，如果你还记得 该视频中，我们谈到
有关如何单链接 名单做参加我们的能力
处理信息 其中的元素数
或项目中的数 清单可以扩大或缩小。
现在，我们可以处理 类似的东西，在这里
我们不能处理它使用数组。
>> 但他们从一个人受 严格的限制这
的是，与单链接 列表中，我们永远只能移动
在通过列表中的单个方向。
而唯一的真实情况 在这里，可以成为一个问题
是当我们试图 删除单个元件。
而我们甚至没有讨论该怎么办呢 在一个单链表在伪代码。
这当然是可行的，但 它可以是一个有点麻烦。
所以，如果你发现自己 在一个情况下
你想删除 从列表中单个元素
或者它会被要求 你会被删除
从单要素 列表中，您可能希望
考虑使用双联 列出代替单链接列表。
由于双链表让你 移动向前和向后
通过列表，而不是 通过列表中 - 只是前进
只需通过添加一个额外的元素 我们的结构定义
对于双链表节点。
>> 同样，如果你不打算 被删除单个元素
从列表中 - 因为我们增加 一个额外的领域我们的结构
定义，节点本身 对于双链表
将要大一些。
他们将采取 最多的内存多个字节。
所以，如果这是不是 你将需要做的，
你可能会决定它的 不值得的权衡
不得不花费额外的 所需的内存字节
对于一个双向链表，如果你不 要被删除的单元素。
但他们也很酷 对于其他的一些东西。
>> 因此，正如我所说的，我们只需要添加 一个单一的领域到我们的结构
definition--这个概念 对以前的指针。
因此，与一个单链表，我们 具有值和下一步指针，
因此，双向链表只是有 一种方式向后移动为好。
>> 现在，在单链接 名单视频中，我们谈到
关于这些是五个 你需要主要的东西
能够做到链表来工作。
对于大多数的这些，但事实上 这是一个双向链表
是不是一个真正的大跳跃。
我们仍然可以通过搜索，只需 前进，从开始到结束。
我们仍然可以创建一个节点出 空气稀薄，几乎以同样的方式。
我们几乎可以删除列表 大致相同的方式得。
唯一的事情， 有微妙的不同，
确实，在插入 新节点进入榜单，
我们将最后说说删除 从列表中的单个元素为好。
此外，相当多 其他三，我们
不打算谈论他们 现在，因为他们只是
在思想非常小的调整讨论 在单链表视频。
>> 因此，让我们插入一个新节点 成双向链表。
我们谈到这样做的 单链表为好，
但有一对夫妇的额外 捕获与双链表。
我们[？在的头上传球？] 在这里列出一些任意值，
而我们想要得到的新掌门人 名单出这个功能。
这就是为什么它返回一个dllnode明星。
那么哪些步骤？
它们是，再次，非常相似 以单链表
有一个额外的补充。
我们要分配空间用于新的 节点和检查，以确保它是有效的。
我们要填补这个节点了 与任何信息，我们
希望把它。
过去的事情，我们需要do--的 我们需要做额外的事，rather--
是修复上的指针 老人头列表中。
请记住，因为 的双链表，
我们可以继续前进 和backwards--这
意味着每个节点实际上指向 其他两个节点，而不是只是一个。
因此，我们需要解决 老人头列表
向后指向的新负责人 链表，这是一件
我们没有做到过。
和以前一样，我们只返回一个 指针到列表中的新掌门人。
>> 所以这里有一个列表。
我们要插入12到列表中。
注意，图 略有不同。
每个节点包含三个fields-- 数据，和一个下一指针在红，
和以前的指针为蓝色。
没有一样是在15点之前， 所以以前的指针为空。
这是列表的开头。
没有什么之前。
而没有一样是在10点之后，以及 所以它的下一个指针为空也是如此。
>> 因此，让我们添加12到这个列表。
我们需要[听不清]为节点的空间。
我们把它的12内。
再然后，我们需要的是真正的 注意不要打破链。
我们要重新排列的 指针以正确的顺序。
有时可能mean-- 正如我们将看到特别
与delete--，我们确实有一些 多余的三分球，不过没关系。
>> 那我们首先要干什么？
我会建议 你或许应该的事情
这样做是填补了12的指针 节点之前你接触其​​他人。
那么，什么是12将指向下一个？
15。
什么来12前？
什么也没有。
现在我们已经填补了 在12额外的信息
因此它具有上，下，和价值。
>> 现在，我们可以有15--这种额外 一步，我们正在谈论about--我们
可以有15点回12。
现在，我们可以将头 该链接的表也为12。
所以这是非常类似于我们 在做与单链表，
除了额外的步骤 连接老脸名单
返回列表的新掌门人。
>> 现在，让我们终于删除 从链表中的节点。
所以我们可以说，我们有 其他一些功能
是找到我们要删除一个节点 并给了我们一个指针准确
我们要删除的节点。
我们甚至不need--说 头仍然是全球范围内宣布。
我们并不需要在这里头。
所有这些功能做的是我们已经 发现了一个指针完全节点我们
想摆脱的。
让我们摆脱它。
这是一个很大，使用更加简单 双链表。
First--它实际上 只是一对夫妇的事情。
我们只需要修复周围 节点的指针，让他们跳过
节点，我们想删除。
然后我们就可以删除该节点。
所以，再一次，我们只是经过这里。
我们显然已经决定， 我们要删除的节点X.
再次，就是我 由方式 - 这里 - 做
是一般的情况下为一个 节点是在中间。
有一对夫妇的 额外的警告，你
需要当你删除考虑 列表的一开始
或列表的最后。
有一组特殊的 角落的情况下，处理那里。
>> 因此，这适用于删除任何节点 在列表中 - 一个中间那
有一个合法的指针向前 和一个合法的指针向后，
正当一个和下一个指针。
再次，如果你的工作 与结束，你
需要处理的 略有不同，
而且我们不打算 谈论这件事情。
但你也许可以 找出什么需要
要通过观看这部影片刚刚做。
>> 因此，我们已经分离出X，X是节点 我们想从列表中删除。
我们做什么？
首先，我们需要重新安排 外面的指针。
我们需要重新安排 9的下一个跳过13
并指向10--这 就是我们刚才所做的事情。
而且，我们还需要 重新安排10的前
指向而不是指向13到9。
>> 如此反复，这是 图开始。
这是我们的产业链。
我们需要跳过13， 但我们也需要维护
列表的完整性。
我们不希望失去任何 在任一方向的信息。
因此，我们需要重新安排 指针仔细
所以我们不打破链上的所有。
>> 所以我们可以说9的下一个指针 指向同一个地方
那个13的下 指针指向现在。
因为我们是最后 会想跳过13。
所以，在13点旁边，你 希望朝九晚指向同去。
不过就是这样。
然后只要13分回 到，无坚不摧13日之​​前，
我们希望10点 到，而不是13。
现在请注意，如果你遵循 箭头，我们可以下降13
实际上不丢失任何信息。
我们已经把名单的完整性， 向前和向后移动两者。
然后我们就可以只排序 对清理一点点
通过拉动名单在一起。
因此，我们重新安排了 指针在任一侧。
然后我们释放的X 节点包含13，
我们没有打破链。
因此，我们做得很好。
>> 最后要注意这里链表。
因此，无论单电荷和双联 单，因为我们已经看到，
支持真正有效插入 和删除元素。
你几乎可以做 它在固定的时间。
我们有什么做删除 一个元素就在一秒钟前？
我们移动一个指针。
我们搬到另一个指针。
我们释放X--了三次手术。
它总是需要三个操作 删除node--释放一个节点。
>> 我们如何插入？
好了，我们只是一直 套结的开始
如果我们要插入效率。
因此，我们需要rearrange-- 这取决于它是否在
一个单电荷或双联 列表中，我们可能需要做三
或四则运算最大。
但同样，它总是三个或四个。
不要紧，有多少 元素在我们的名单，
它总是三四operations-- 就像缺失始终是
三个或四个操作。
这是恒定的时间。
所以，这真的很棒。
>> 数组，我们正在做 像插入排序。
你可能还记得，插入 排序不是一个常数时间算法。
它实际上是相当昂贵的。
所以这是一个很大的插好。
但正如我所提到的 单链表视频，
我们已经有了一个缺点也在这里，对不对？
我们已经失去了能力， 随机访问元素。
我们不能说，我想元数四 或元件的一个链表10号
同样的方式，我们可以 做到这一点与数组
或者我们可以直接索引 到我们的数组中的元素。
>> 所以试图找到一个 在链接列表中 - 元素
如果搜索important-- 现在可能需要线性时间。
由于名单很长，它 可能需要一个额外的步骤
对于列表中的每一个元件在 为了找到我们所要寻找的。
因此，有权衡。
有一点亲 这里CON元素。
>> 和双链表是不 最后一种数据结构组合
我们将谈论， 把所有的基本构建
的C块的放在一起。
因为事实上，我们可以 甚至做的比这更好
创建一个数据结构，它 你也许可以通过搜索
在固定的时间了。
但更多的，在另一个视频。
>> 我是道格·劳埃德。
这是CS50。