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