1 00:00:00,000 --> 00:00:03,381 >> [音乐播放] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD:好吧。 4 00:00:05,520 --> 00:00:07,860 所以,如果你刚刚完成的 视频单链表遗憾 5 00:00:07,860 --> 00:00:09,568 我离开你关上一 悬念位。 6 00:00:09,568 --> 00:00:12,790 不过,我很高兴你在这里完成 双链表的故事。 7 00:00:12,790 --> 00:00:15,250 >> 所以,如果你还记得 该视频中,我们谈到 8 00:00:15,250 --> 00:00:18,500 有关如何单链接 名单做参加我们的能力 9 00:00:18,500 --> 00:00:22,090 处理信息 其中的元素数 10 00:00:22,090 --> 00:00:24,442 或项目中的数 清单可以扩大或缩小。 11 00:00:24,442 --> 00:00:26,400 现在,我们可以处理 类似的东西,在这里 12 00:00:26,400 --> 00:00:28,310 我们不能处理它使用数组。 13 00:00:28,310 --> 00:00:30,560 >> 但他们从一个人受 严格的限制这 14 00:00:30,560 --> 00:00:33,790 的是,与单链接 列表中,我们永远只能移动 15 00:00:33,790 --> 00:00:36,200 在通过列表中的单个方向。 16 00:00:36,200 --> 00:00:39,010 而唯一的真实情况 在这里,可以成为一个问题 17 00:00:39,010 --> 00:00:41,250 是当我们试图 删除单个元件。 18 00:00:41,250 --> 00:00:46,000 而我们甚至没有讨论该怎么办呢 在一个单链表在伪代码。 19 00:00:46,000 --> 00:00:48,797 这当然是可行的,但 它可以是一个有点麻烦。 20 00:00:48,797 --> 00:00:50,630 所以,如果你发现自己 在一个情况下 21 00:00:50,630 --> 00:00:53,175 你想删除 从列表中单个元素 22 00:00:53,175 --> 00:00:55,430 或者它会被要求 你会被删除 23 00:00:55,430 --> 00:00:57,970 从单要素 列表中,您可能希望 24 00:00:57,970 --> 00:01:02,090 考虑使用双联 列出代替单链接列表。 25 00:01:02,090 --> 00:01:06,320 由于双链表让你 移动向前和向后 26 00:01:06,320 --> 00:01:09,340 通过列表,而不是 通过列表中 - 只是前进 27 00:01:09,340 --> 00:01:13,950 只需通过添加一个额外的元素 我们的结构定义 28 00:01:13,950 --> 00:01:16,690 对于双链表节点。 29 00:01:16,690 --> 00:01:19,770 >> 同样,如果你不打算 被删除单个元素 30 00:01:19,770 --> 00:01:24,810 从列表中 - 因为我们增加 一个额外的领域我们的结构 31 00:01:24,810 --> 00:01:28,340 定义,节点本身 对于双链表 32 00:01:28,340 --> 00:01:29,550 将要大一些。 33 00:01:29,550 --> 00:01:31,600 他们将采取 最多的内存多个字节。 34 00:01:31,600 --> 00:01:34,160 所以,如果这是不是 你将需要做的, 35 00:01:34,160 --> 00:01:36,300 你可能会决定它的 不值得的权衡 36 00:01:36,300 --> 00:01:39,360 不得不花费额外的 所需的内存字节 37 00:01:39,360 --> 00:01:43,940 对于一个双向链表,如果你不 要被删除的单元素。 38 00:01:43,940 --> 00:01:46,760 但他们也很酷 对于其他的一些东西。 39 00:01:46,760 --> 00:01:51,260 >> 因此,正如我所说的,我们只需要添加 一个单一的领域到我们的结构 40 00:01:51,260 --> 00:01:55,360 definition--这个概念 对以前的指针。 41 00:01:55,360 --> 00:01:58,620 因此,与一个单链表,我们 具有值和下一步指针, 42 00:01:58,620 --> 00:02:02,850 因此,双向链表只是有 一种方式向后移动为好。 43 00:02:02,850 --> 00:02:04,960 >> 现在,在单链接 名单视频中,我们谈到 44 00:02:04,960 --> 00:02:07,210 关于这些是五个 你需要主要的东西 45 00:02:07,210 --> 00:02:09,449 能够做到链表来工作。 46 00:02:09,449 --> 00:02:12,880 对于大多数的这些,但事实上 这是一个双向链表 47 00:02:12,880 --> 00:02:14,130 是不是一个真正的大跳跃。 48 00:02:14,130 --> 00:02:17,936 我们仍然可以通过搜索,只需 前进,从开始到结束。 49 00:02:17,936 --> 00:02:20,810 我们仍然可以创建一个节点出 空气稀薄,几乎以同样的方式。 50 00:02:20,810 --> 00:02:23,591 我们几乎可以删除列表 大致相同的方式得。 51 00:02:23,591 --> 00:02:25,340 唯一的事情, 有微妙的不同, 52 00:02:25,340 --> 00:02:28,970 确实,在插入 新节点进入榜单, 53 00:02:28,970 --> 00:02:33,722 我们将最后说说删除 从列表中的单个元素为好。 54 00:02:33,722 --> 00:02:35,430 此外,相当多 其他三,我们 55 00:02:35,430 --> 00:02:37,888 不打算谈论他们 现在,因为他们只是 56 00:02:37,888 --> 00:02:43,920 在思想非常小的调整讨论 在单链表视频。 57 00:02:43,920 --> 00:02:46,292 >> 因此,让我们插入一个新节点 成双向链表。 58 00:02:46,292 --> 00:02:48,750 我们谈到这样做的 单链表为好, 59 00:02:48,750 --> 00:02:52,020 但有一对夫妇的额外 捕获与双链表。 60 00:02:52,020 --> 00:02:55,280 我们[?在的头上传球?] 在这里列出一些任意值, 61 00:02:55,280 --> 00:02:58,600 而我们想要得到的新掌门人 名单出这个功能。 62 00:02:58,600 --> 00:03:01,414 这就是为什么它返回一个dllnode明星。 63 00:03:01,414 --> 00:03:02,330 那么哪些步骤? 64 00:03:02,330 --> 00:03:04,496 它们是,再次,非常相似 以单链表 65 00:03:04,496 --> 00:03:05,670 有一个额外的补充。 66 00:03:05,670 --> 00:03:08,900 我们要分配空间用于新的 节点和检查,以确保它是有效的。 67 00:03:08,900 --> 00:03:11,510 我们要填补这个节点了 与任何信息,我们 68 00:03:11,510 --> 00:03:12,564 希望把它。 69 00:03:12,564 --> 00:03:15,480 过去的事情,我们需要do--的 我们需要做额外的事,rather-- 70 00:03:15,480 --> 00:03:19,435 是修复上的指针 老人头列表中。 71 00:03:19,435 --> 00:03:21,310 请记住,因为 的双链表, 72 00:03:21,310 --> 00:03:23,110 我们可以继续前进 和backwards--这 73 00:03:23,110 --> 00:03:27,080 意味着每个节点实际上指向 其他两个节点,而不是只是一个。 74 00:03:27,080 --> 00:03:29,110 因此,我们需要解决 老人头列表 75 00:03:29,110 --> 00:03:32,151 向后指向的新负责人 链表,这是一件 76 00:03:32,151 --> 00:03:33,990 我们没有做到过。 77 00:03:33,990 --> 00:03:37,420 和以前一样,我们只返回一个 指针到列表中的新掌门人。 78 00:03:37,420 --> 00:03:38,220 >> 所以这里有一个列表。 79 00:03:38,220 --> 00:03:40,144 我们要插入12到列表中。 80 00:03:40,144 --> 00:03:42,060 注意,图 略有不同。 81 00:03:42,060 --> 00:03:47,710 每个节点包含三个fields-- 数据,和一个下一指针在红, 82 00:03:47,710 --> 00:03:50,170 和以前的指针为蓝色。 83 00:03:50,170 --> 00:03:54,059 没有一样是在15点之前, 所以以前的指针为空。 84 00:03:54,059 --> 00:03:55,350 这是列表的开头。 85 00:03:55,350 --> 00:03:56,560 没有什么之前。 86 00:03:56,560 --> 00:04:03,350 而没有一样是在10点之后,以及 所以它的下一个指针为空也是如此。 87 00:04:03,350 --> 00:04:05,616 >> 因此,让我们添加12到这个列表。 88 00:04:05,616 --> 00:04:08,070 我们需要[听不清]为节点的空间。 89 00:04:08,070 --> 00:04:11,480 我们把它的12内。 90 00:04:11,480 --> 00:04:14,840 再然后,我们需要的是真正的 注意不要打破链。 91 00:04:14,840 --> 00:04:17,144 我们要重新排列的 指针以正确的顺序。 92 00:04:17,144 --> 00:04:19,519 有时可能mean-- 正如我们将看到特别 93 00:04:19,519 --> 00:04:24,120 与delete--,我们确实有一些 多余的三分球,不过没关系。 94 00:04:24,120 --> 00:04:25,750 >> 那我们首先要干什么? 95 00:04:25,750 --> 00:04:28,290 我会建议 你或许应该的事情 96 00:04:28,290 --> 00:04:35,350 这样做是填补了12的指针 节点之前你接触其​​他人。 97 00:04:35,350 --> 00:04:38,640 那么,什么是12将指向下一个? 98 00:04:38,640 --> 00:04:39,860 15。 99 00:04:39,860 --> 00:04:42,430 什么来12前? 100 00:04:42,430 --> 00:04:43,640 什么也没有。 101 00:04:43,640 --> 00:04:46,280 现在我们已经填补了 在12额外的信息 102 00:04:46,280 --> 00:04:49,320 因此它具有上,下,和价值。 103 00:04:49,320 --> 00:04:53,505 >> 现在,我们可以有15--这种额外 一步,我们正在谈论about--我们 104 00:04:53,505 --> 00:04:56,590 可以有15点回12。 105 00:04:56,590 --> 00:04:59,634 现在,我们可以将头 该链接的表也为12。 106 00:04:59,634 --> 00:05:02,550 所以这是非常类似于我们 在做与单链表, 107 00:05:02,550 --> 00:05:06,940 除了额外的步骤 连接老脸名单 108 00:05:06,940 --> 00:05:09,810 返回列表的新掌门人。 109 00:05:09,810 --> 00:05:12,170 >> 现在,让我们终于删除 从链表中的节点。 110 00:05:12,170 --> 00:05:14,350 所以我们可以说,我们有 其他一些功能 111 00:05:14,350 --> 00:05:18,080 是找到我们要删除一个节点 并给了我们一个指针准确 112 00:05:18,080 --> 00:05:19,710 我们要删除的节点。 113 00:05:19,710 --> 00:05:22,360 我们甚至不need--说 头仍然是全球范围内宣布。 114 00:05:22,360 --> 00:05:23,590 我们并不需要在这里头。 115 00:05:23,590 --> 00:05:26,830 所有这些功能做的是我们已经 发现了一个指针完全节点我们 116 00:05:26,830 --> 00:05:28,090 想摆脱的。 117 00:05:28,090 --> 00:05:28,940 让我们摆脱它。 118 00:05:28,940 --> 00:05:31,859 这是一个很大,使用更加简单 双链表。 119 00:05:31,859 --> 00:05:33,650 First--它实际上 只是一对夫妇的事情。 120 00:05:33,650 --> 00:05:38,760 我们只需要修复周围 节点的指针,让他们跳过 121 00:05:38,760 --> 00:05:40,240 节点,我们想删除。 122 00:05:40,240 --> 00:05:43,484 然后我们就可以删除该节点。 123 00:05:43,484 --> 00:05:45,150 所以,再一次,我们只是经过这里。 124 00:05:45,150 --> 00:05:49,625 我们显然已经决定, 我们要删除的节点X. 125 00:05:49,625 --> 00:05:51,500 再次,就是我 由方式 - 这里 - 做 126 00:05:51,500 --> 00:05:54,580 是一般的情况下为一个 节点是在中间。 127 00:05:54,580 --> 00:05:56,547 有一对夫妇的 额外的警告,你 128 00:05:56,547 --> 00:05:59,380 需要当你删除考虑 列表的一开始 129 00:05:59,380 --> 00:06:01,040 或列表的最后。 130 00:06:01,040 --> 00:06:03,730 有一组特殊的 角落的情况下,处理那里。 131 00:06:03,730 --> 00:06:07,960 >> 因此,这适用于删除任何节点 在列表中 - 一个中间那 132 00:06:07,960 --> 00:06:11,550 有一个合法的指针向前 和一个合法的指针向后, 133 00:06:11,550 --> 00:06:14,460 正当一个和下一个指针。 134 00:06:14,460 --> 00:06:16,530 再次,如果你的工作 与结束,你 135 00:06:16,530 --> 00:06:18,500 需要处理的 略有不同, 136 00:06:18,500 --> 00:06:19,570 而且我们不打算 谈论这件事情。 137 00:06:19,570 --> 00:06:21,319 但你也许可以 找出什么需要 138 00:06:21,319 --> 00:06:24,610 要通过观看这部影片刚刚做。 139 00:06:24,610 --> 00:06:28,910 >> 因此,我们已经分离出X,X是节点 我们想从列表中删除。 140 00:06:28,910 --> 00:06:30,140 我们做什么? 141 00:06:30,140 --> 00:06:32,800 首先,我们需要重新安排 外面的指针。 142 00:06:32,800 --> 00:06:35,815 我们需要重新安排 9的下一个跳过13 143 00:06:35,815 --> 00:06:38,030 并指向10--这 就是我们刚才所做的事情。 144 00:06:38,030 --> 00:06:41,180 而且,我们还需要 重新安排10的前 145 00:06:41,180 --> 00:06:44,610 指向而不是指向13到9。 146 00:06:44,610 --> 00:06:46,490 >> 如此反复,这是 图开始。 147 00:06:46,490 --> 00:06:47,730 这是我们的产业链。 148 00:06:47,730 --> 00:06:51,027 我们需要跳过13, 但我们也需要维护 149 00:06:51,027 --> 00:06:52,110 列表的完整性。 150 00:06:52,110 --> 00:06:54,680 我们不希望失去任何 在任一方向的信息。 151 00:06:54,680 --> 00:06:59,620 因此,我们需要重新安排 指针仔细 152 00:06:59,620 --> 00:07:02,240 所以我们不打破链上的所有。 153 00:07:02,240 --> 00:07:05,710 >> 所以我们可以说9的下一个指针 指向同一个地方 154 00:07:05,710 --> 00:07:08,040 那个13的下 指针指向现在。 155 00:07:08,040 --> 00:07:10,331 因为我们是最后 会想跳过13。 156 00:07:10,331 --> 00:07:13,750 所以,在13点旁边,你 希望朝九晚指向同去。 157 00:07:13,750 --> 00:07:15,200 不过就是这样。 158 00:07:15,200 --> 00:07:20,370 然后只要13分回 到,无坚不摧13日之​​前, 159 00:07:20,370 --> 00:07:24,800 我们希望10点 到,而不是13。 160 00:07:24,800 --> 00:07:29,290 现在请注意,如果你遵循 箭头,我们可以下降13 161 00:07:29,290 --> 00:07:32,380 实际上不丢失任何信息。 162 00:07:32,380 --> 00:07:36,002 我们已经把名单的完整性, 向前和向后移动两者。 163 00:07:36,002 --> 00:07:38,210 然后我们就可以只排序 对清理一点点 164 00:07:38,210 --> 00:07:40,930 通过拉动名单在一起。 165 00:07:40,930 --> 00:07:43,270 因此,我们重新安排了 指针在任一侧。 166 00:07:43,270 --> 00:07:46,231 然后我们释放的X 节点包含13, 167 00:07:46,231 --> 00:07:47,480 我们没有打破链。 168 00:07:47,480 --> 00:07:50,980 因此,我们做得很好。 169 00:07:50,980 --> 00:07:53,000 >> 最后要注意这里链表。 170 00:07:53,000 --> 00:07:55,990 因此,无论单电荷和双联 单,因为我们已经看到, 171 00:07:55,990 --> 00:07:58,959 支持真正有效插入 和删除元素。 172 00:07:58,959 --> 00:08:00,750 你几乎可以做 它在固定的时间。 173 00:08:00,750 --> 00:08:03,333 我们有什么做删除 一个元素就在一秒钟前? 174 00:08:03,333 --> 00:08:04,440 我们移动一个指针。 175 00:08:04,440 --> 00:08:05,920 我们搬到另一个指针。 176 00:08:05,920 --> 00:08:07,915 我们释放X--了三次手术。 177 00:08:07,915 --> 00:08:14,500 它总是需要三个操作 删除node--释放一个节点。 178 00:08:14,500 --> 00:08:15,280 >> 我们如何插入? 179 00:08:15,280 --> 00:08:17,280 好了,我们只是一直 套结的开始 180 00:08:17,280 --> 00:08:19,400 如果我们要插入效率。 181 00:08:19,400 --> 00:08:21,964 因此,我们需要rearrange-- 这取决于它是否在 182 00:08:21,964 --> 00:08:24,380 一个单电荷或双联 列表中,我们可能需要做三 183 00:08:24,380 --> 00:08:26,824 或四则运算最大。 184 00:08:26,824 --> 00:08:28,365 但同样,它总是三个或四个。 185 00:08:28,365 --> 00:08:30,531 不要紧,有多少 元素在我们的名单, 186 00:08:30,531 --> 00:08:33,549 它总是三四operations-- 就像缺失始终是 187 00:08:33,549 --> 00:08:35,320 三个或四个操作。 188 00:08:35,320 --> 00:08:36,919 这是恒定的时间。 189 00:08:36,919 --> 00:08:38,169 所以,这真的很棒。 190 00:08:38,169 --> 00:08:40,620 >> 数组,我们正在做 像插入排序。 191 00:08:40,620 --> 00:08:44,739 你可能还记得,插入 排序不是一个常数时间算法。 192 00:08:44,739 --> 00:08:46,030 它实际上是相当昂贵的。 193 00:08:46,030 --> 00:08:48,840 所以这是一个很大的插好。 194 00:08:48,840 --> 00:08:51,840 但正如我所提到的 单链表视频, 195 00:08:51,840 --> 00:08:54,030 我们已经有了一个缺点也在这里,对不对? 196 00:08:54,030 --> 00:08:57,580 我们已经失去了能力, 随机访问元素。 197 00:08:57,580 --> 00:09:02,310 我们不能说,我想元数四 或元件的一个链表10号 198 00:09:02,310 --> 00:09:04,990 同样的方式,我们可以 做到这一点与数组 199 00:09:04,990 --> 00:09:08,630 或者我们可以直接索引 到我们的数组中的元素。 200 00:09:08,630 --> 00:09:10,930 >> 所以试图找到一个 在链接列表中 - 元素 201 00:09:10,930 --> 00:09:15,880 如果搜索important-- 现在可能需要线性时间。 202 00:09:15,880 --> 00:09:18,330 由于名单很长,它 可能需要一个额外的步骤 203 00:09:18,330 --> 00:09:22,644 对于列表中的每一个元件在 为了找到我们所要寻找的。 204 00:09:22,644 --> 00:09:23,560 因此,有权衡。 205 00:09:23,560 --> 00:09:25,780 有一点亲 这里CON元素。 206 00:09:25,780 --> 00:09:29,110 >> 和双链表是不 最后一种数据结构组合 207 00:09:29,110 --> 00:09:32,840 我们将谈论, 把所有的基本构建 208 00:09:32,840 --> 00:09:34,865 的C块的放在一起。 209 00:09:34,865 --> 00:09:37,900 因为事实上,我们可以 甚至做的比这更好 210 00:09:37,900 --> 00:09:41,970 创建一个数据结构,它 你也许可以通过搜索 211 00:09:41,970 --> 00:09:43,360 在固定的时间了。 212 00:09:43,360 --> 00:09:46,080 但更多的,在另一个视频。 213 00:09:46,080 --> 00:09:47,150 >> 我是道格·劳埃德。 214 00:09:47,150 --> 00:09:49,050 这是CS50。 215 00:09:49,050 --> 00:09:50,877