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
>> しかし、彼らは1苦しむん
クリティカル制限します

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
代わりのリストを
ちょうど前方list--を通じて

27
00:01:09,340 --> 00:01:13,950
ただ1つの余分な要素を追加することにより、
私たちの構造定義へ

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
list--から、私たちは追加しているので、
私たちの構造への追加フィールド

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
>> 私が言ったように、私たちは追加する必要があります
私たちの構造への1つのフィールド

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
これらについての5です
あなたがする必要があります主なもの

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
ここでも、かなり
私たちがしている他の3、

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
1つの余分な追加されています。

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
各ノードは、実際に指すことを意味し
他の2つのノードへの代わりに一つだけ。

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
各ノードは3 fields--が含まれています
データ、および赤の次のポインタ、

82
00:03:47,710 --> 00:03:50,170
青の前のポインタ。

83
00:03:50,170 --> 00:03:54,059
何も、15ノードの前に来ることはありません
ため、その前のポインタはNULLです。

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ノードの後に​​来ることはありませんし、
ので、次のポインタだとしてもnullです。

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
バック12から15ポイントを持つことができます。

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
そして再び、私は何です
way--によってhere--やっ

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
>> だから、これは、任意のノードを削除するために働きます
そのlist-- 1の途中で

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
9にポイントの代わりに13を指します。

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ポイントの横には、
9ではなくそこに指すようにしたいです。

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
だからsingly-両方と二重リンク
リスト、我々が見てきたように、

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--は3つの操作をした解放されました。

177
00:08:07,915 --> 00:08:14,500
それは、常に3つの操作にかかります
ノードを解放すること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
singly-または二重リンク
リストは、3つが必要になることがあります

183
00:08:24,380 --> 00:08:26,824
または4つの操作を最大。

184
00:08:26,824 --> 00:08:28,365
しかし、再び、それは常に3つまたは​​4つのます。

185
00:08:28,365 --> 00:08:30,531
それはどのように多くの問題ではありません。
要素は、私たちのリストにあり

186
00:08:30,531 --> 00:08:33,549
それは、常に3つまたは​​4つのoperations--です
削除は常に同じように

187
00:08:33,549 --> 00:08:35,320
3つまたは​​4つの操作。

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
私たちは、私は要素番号4をしたい、と言うことはできません
リンクされたリストまたは要素番号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
>> そしてそう見つけるしようとし
リンクlist--の要素

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
プロのビットがあります
ここでコン要素。

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