[音乐播放] 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。