1
00:00:00,000 --> 00:00:03,381
>> [Přehrávání hudby]

2
00:00:03,381 --> 00:00:04,604

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Dobře.

4
00:00:05,520 --> 00:00:07,860
Takže pokud jste právě dokončili, že
video na singly-provázané seznamy promiňte

5
00:00:07,860 --> 00:00:09,568
Nechal jsem tě pryč na
trochu cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Ale jsem rád, že jsi tady až do konce
Příběh dvojitě spojových seznamů.

7
00:00:12,790 --> 00:00:15,250
>> Takže pokud si vzpomínáte z
že video, jsme si povídali

8
00:00:15,250 --> 00:00:18,500
o tom, jak jednotlivě vázané
Seznamy dělat navštěvovat naši schopnost

9
00:00:18,500 --> 00:00:22,090
se vypořádat s informacemi
kde počet prvků

10
00:00:22,090 --> 00:00:24,442
nebo počet kusů
seznam může růst nebo zmenšit.

11
00:00:24,442 --> 00:00:26,400
Nyní můžeme řešit
něco takového, kde

12
00:00:26,400 --> 00:00:28,310
nemohli jsme se s tím vyrovnat s poli.

13
00:00:28,310 --> 00:00:30,560
>> Ale oni trpí jednoho
kritická omezení, která

14
00:00:30,560 --> 00:00:33,790
se, že s jednotlivě vázané
seznam, můžeme jen někdy pohnout

15
00:00:33,790 --> 00:00:36,200
v jednom směru v seznamu.

16
00:00:36,200 --> 00:00:39,010
A jediný skutečný stav
kde, že se může stát problémem

17
00:00:39,010 --> 00:00:41,250
bylo, když jsme se snažili
Odstranění jednoho prvku.

18
00:00:41,250 --> 00:00:46,000
A my jsme ani diskutovat o tom, jak na to
v singly-Google seznamu v pseudokódu.

19
00:00:46,000 --> 00:00:48,797
To je jistě proveditelné, ale
to může být trochu zmatků.

20
00:00:48,797 --> 00:00:50,630
Takže pokud se ocitnete
v situaci, kdy

21
00:00:50,630 --> 00:00:53,175
se snažíte smazat
jednotlivé prvky ze seznamu

22
00:00:53,175 --> 00:00:55,430
nebo to bude nutné
že budete mazání

23
00:00:55,430 --> 00:00:57,970
jednotlivé prvky z
seznamu, možná budete chtít

24
00:00:57,970 --> 00:01:02,090
zvážit použití dvojnásobně vázaný
Seznam místo singly-provázaný seznam.

25
00:01:02,090 --> 00:01:06,320
Vzhledem k tomu, dvojitě spojové seznamy vám umožňují
do pohybovat oběma dopředu a dozadu

26
00:01:06,320 --> 00:01:09,340
v seznamu namísto
jen dopředu přes list--

27
00:01:09,340 --> 00:01:13,950
jen tím, že přidá jeden navíc prvek
na naší definice struktury

28
00:01:13,950 --> 00:01:16,690
Pro dvojitě Google seznamu uzlu.

29
00:01:16,690 --> 00:01:19,770
>> Opět platí, že pokud se nebudeme
být mazání jednotlivých prvků

30
00:01:19,770 --> 00:01:24,810
od list-- protože jsme přidávání
navíc pole k naší struktuře

31
00:01:24,810 --> 00:01:28,340
definice, samotné uzly
pro dvojitě spojových seznamů

32
00:01:28,340 --> 00:01:29,550
se bude větší.

33
00:01:29,550 --> 00:01:31,600
Chystají se vzít
up více bajtů paměti.

34
00:01:31,600 --> 00:01:34,160
A tak, pokud to není něco,
budete muset udělat,

35
00:01:34,160 --> 00:01:36,300
se můžete rozhodnout, že je to
nestojí za kompromis

36
00:01:36,300 --> 00:01:39,360
muset strávit další
bajtů paměti požadováno

37
00:01:39,360 --> 00:01:43,940
pro dvojitě Google seznamu, pokud si nejste
bude mazání jednotlivých prvků.

38
00:01:43,940 --> 00:01:46,760
Ale jsou také v pohodě
pro jiné věci.

39
00:01:46,760 --> 00:01:51,260
>> Tak jak jsem řekl, budeme muset přidat
jedno jediné pole do naší struktuře

40
00:01:51,260 --> 00:01:55,360
definition-- tento pojem
z předchozí ukazatel.

41
00:01:55,360 --> 00:01:58,620
Takže s singly-provázaném seznamu, my
mít hodnotu A další ukazatel,

42
00:01:58,620 --> 00:02:02,850
takže dvojitě provázaný seznam prostě musí
způsob, jak se pohybovat zpět stejně.

43
00:02:02,850 --> 00:02:04,960
>> Nyní v singly-spojený
Seznam video, mluvili jsme

44
00:02:04,960 --> 00:02:07,210
o nich je pět
hlavní věci, které je třeba

45
00:02:07,210 --> 00:02:09,449
schopný dělat práci s spojových seznamů.

46
00:02:09,449 --> 00:02:12,880
A pro většinu z nich je skutečnost,
že je to dvojnásob vázaný seznam

47
00:02:12,880 --> 00:02:14,130
není opravdu velký skok.

48
00:02:14,130 --> 00:02:17,936
Stále můžeme prohledávat pouhým
kupředu od začátku až do konce.

49
00:02:17,936 --> 00:02:20,810
Stále můžeme vytvořit uzel ven
řídký vzduch, skoro stejným způsobem.

50
00:02:20,810 --> 00:02:23,591
Můžeme smazat seznamy dost
hodně stejný cesta taky.

51
00:02:23,591 --> 00:02:25,340
Jediné věci, které
jsou nepatrně odlišné,

52
00:02:25,340 --> 00:02:28,970
Opravdu, vkládáte
nové uzly do seznamu,

53
00:02:28,970 --> 00:02:33,722
a budeme konečně hovořit o odstraňování
jeden prvek ze seznamu stejně.

54
00:02:33,722 --> 00:02:35,430
Opět platí, že do značné míry
další tři, my jsme

55
00:02:35,430 --> 00:02:37,888
nebude mluvit o nich
hned teď, protože jsou to jen

56
00:02:37,888 --> 00:02:43,920
velmi malé vylepší se k myšlenkám diskutovaným
V singly-provázaný seznam video.

57
00:02:43,920 --> 00:02:46,292
>> Takže pojďme vložit nový uzel
do dvojitě Google seznamu.

58
00:02:46,292 --> 00:02:48,750
Mluvili jsme o tom to pro
jednotlivě vázané seznamy také,

59
00:02:48,750 --> 00:02:52,020
ale je tu pár navíc
chytí s dvojitě spojových seznamů.

60
00:02:52,020 --> 00:02:55,280
Jsme [? absolvování?] v hlavě
seznam zde a někteří libovolná hodnota,

61
00:02:55,280 --> 00:02:58,600
a chceme získat nové hlavy
seznamu z této funkce.

62
00:02:58,600 --> 00:03:01,414
To je důvod, proč vrátí dllnode hvězdu.

63
00:03:01,414 --> 00:03:02,330
Takže jaké jsou kroky?

64
00:03:02,330 --> 00:03:04,496
Jsou opět velmi podobný
se jednotlivě vázané seznamy

65
00:03:04,496 --> 00:03:05,670
s jednou přistýlkou ​​navíc.

66
00:03:05,670 --> 00:03:08,900
Chceme přidělí místo pro nový
uzel a kontrola, aby se ujistil, že je platný.

67
00:03:08,900 --> 00:03:11,510
Chceme naplnit tento uzel nahoru
s tím, co informace, které

68
00:03:11,510 --> 00:03:12,564
chtít dát v něm.

69
00:03:12,564 --> 00:03:15,480
Poslední věc, kterou musíme do--
další věc, kterou musíme udělat, rather--

70
00:03:15,480 --> 00:03:19,435
je opravit Předchozí ukazatel
starého hlavy seznamu.

71
00:03:19,435 --> 00:03:21,310
Pamatujte si, že proto,
z dvojitě spojové seznamy,

72
00:03:21,310 --> 00:03:23,110
se můžeme pohnout kupředu
a který backwards--

73
00:03:23,110 --> 00:03:27,080
Znamená to, že každý uzel ve skutečnosti poukazuje
dalšími dvěma uzly namísto jen jeden.

74
00:03:27,080 --> 00:03:29,110
A proto je třeba opravit
stará hlava seznamu

75
00:03:29,110 --> 00:03:32,151
přejděte zpět do nového šéfa
propojený seznam, což bylo něco,

76
00:03:32,151 --> 00:03:33,990
jsme nemuseli dělat dřív.

77
00:03:33,990 --> 00:03:37,420
A stejně jako předtím, jen jsme Vrátit
Ukazatel na nového šéfa seznamu.

78
00:03:37,420 --> 00:03:38,220
>> Takže tady je seznam.

79
00:03:38,220 --> 00:03:40,144
Chceme vložit 12 do tohoto seznamu.

80
00:03:40,144 --> 00:03:42,060
Všimněte si, že diagram
se mírně liší.

81
00:03:42,060 --> 00:03:47,710
Každý uzel obsahuje tři fields--
dat, a další ukazatel v červené barvě,

82
00:03:47,710 --> 00:03:50,170
a předchozí ukazatel v modré barvě.

83
00:03:50,170 --> 00:03:54,059
Nic přijde před uzel 15,
tak jeho předchozí ukazatel je null.

84
00:03:54,059 --> 00:03:55,350
Je to začátek seznamu.

85
00:03:55,350 --> 00:03:56,560
Je tu před ním nic není.

86
00:03:56,560 --> 00:04:03,350
A nic po uzlu 10 přichází a
tak to je další ukazatel null stejně.

87
00:04:03,350 --> 00:04:05,616
>> Takže pojďme se přidat 12 do tohoto seznamu.

88
00:04:05,616 --> 00:04:08,070
Potřebujeme [neslyšitelný] prostor pro uzel.

89
00:04:08,070 --> 00:04:11,480
My jsme dali 12 uvnitř ní.

90
00:04:11,480 --> 00:04:14,840
A pak znovu, musíme být opravdu
Dejte pozor, abyste přerušit řetěz.

91
00:04:14,840 --> 00:04:17,144
Chceme změnit uspořádání
ukazatele ve správném pořadí.

92
00:04:17,144 --> 00:04:19,519
A někdy, že by mohly mean--
jak uvidíme zvláště

93
00:04:19,519 --> 00:04:24,120
s delete--, že máme nějaké
redundantní ukazatele, ale to je v pořádku.

94
00:04:24,120 --> 00:04:25,750
>> Takže to, co chceme udělat jako první?

95
00:04:25,750 --> 00:04:28,290
Chtěl bych doporučit
věci, které by pravděpodobně

96
00:04:28,290 --> 00:04:35,350
cílů, se naplnit ukazatele z 12
uzel, než se dotknete někdo jiný.

97
00:04:35,350 --> 00:04:38,640
Takže to, co se 12 bude ukazovat na další?

98
00:04:38,640 --> 00:04:39,860
15.

99
00:04:39,860 --> 00:04:42,430
To, co je před 12?

100
00:04:42,430 --> 00:04:43,640
Nic.

101
00:04:43,640 --> 00:04:46,280
Nyní jsme již obsazeno
další informace ve 12

102
00:04:46,280 --> 00:04:49,320
tak to má předchozí, příští, a hodnotu.

103
00:04:49,320 --> 00:04:53,505
>> Nyní můžeme mít 15-- to navíc
krokem, který jsme mluvili about-- my

104
00:04:53,505 --> 00:04:56,590
může mít 15 bodů zpět na 12 let.

105
00:04:56,590 --> 00:04:59,634
A teď se můžeme přesunout hlavu
propojený seznam také bude 12.

106
00:04:59,634 --> 00:05:02,550
Takže je to dost podobné tomu, co jsme
dělali s singly-provázané seznamy,

107
00:05:02,550 --> 00:05:06,940
s výjimkou pro další krok
spojující starou hlavu seznamu

108
00:05:06,940 --> 00:05:09,810
zpět na nového šéfa seznamu.

109
00:05:09,810 --> 00:05:12,170
>> Nyní pojďme konečně smazat
uzel z propojeného seznamu.

110
00:05:12,170 --> 00:05:14,350
Takže řekněme, že máme
některé další funkce, která

111
00:05:14,350 --> 00:05:18,080
je najít uzel chceme smazat
a dal nám ukazatel přesně

112
00:05:18,080 --> 00:05:19,710
uzel, který chceme odstranit.

113
00:05:19,710 --> 00:05:22,360
Nemáme ani need-- říkají
Hlava je stále globálně deklarován.

114
00:05:22,360 --> 00:05:23,590
My to tady není třeba hlavu.

115
00:05:23,590 --> 00:05:26,830
Všechna tato funkce dělá, je máme
našel ukazatel přesně na uzlu my

116
00:05:26,830 --> 00:05:28,090
chtějí zbavit.

117
00:05:28,090 --> 00:05:28,940
Pojďme se zbavit toho.

118
00:05:28,940 --> 00:05:31,859
Je to mnohem jednodušší s
dvojitě spojený seznamy.

119
00:05:31,859 --> 00:05:33,650
First-- je to vlastně
Jen pár věcí.

120
00:05:33,650 --> 00:05:38,760
Potřebujeme jen opravit okolí
ukazatele uzlů, "tak, aby přeskočit

121
00:05:38,760 --> 00:05:40,240
uzel chceme odstranit.

122
00:05:40,240 --> 00:05:43,484
A pak můžeme smazat tento uzel.

123
00:05:43,484 --> 00:05:45,150
Takže znovu, my jsme jen tak tudy.

124
00:05:45,150 --> 00:05:49,625
Zřejmě jsme se rozhodli, že
chceme smazat uzlu X.

125
00:05:49,625 --> 00:05:51,500
A opět, to, co jsem si
dělá here-- podle way--

126
00:05:51,500 --> 00:05:54,580
je obecný případě takového
uzel, který je uprostřed.

127
00:05:54,580 --> 00:05:56,547
Existuje pár
další výhrady, které jste

128
00:05:56,547 --> 00:05:59,380
je třeba vzít v úvahu, když jste mazání
samého začátku seznamu

129
00:05:59,380 --> 00:06:01,040
nebo velmi konec seznamu.

130
00:06:01,040 --> 00:06:03,730
K dispozici je několik speciálních
rohové případy zabývat se tam.

131
00:06:03,730 --> 00:06:07,960
>> Tak to funguje pro vymazání libovolný uzel
ve středu list-- ten, který

132
00:06:07,960 --> 00:06:11,550
má oprávněný ukazatel vpřed
a legitimní ukazatel zpět,

133
00:06:11,550 --> 00:06:14,460
legitimní Předchozí a Další ukazatel.

134
00:06:14,460 --> 00:06:16,530
Opět platí, že pokud pracujete
s konci, budete

135
00:06:16,530 --> 00:06:18,500
muset zvládnout ty,
trochu jinak,

136
00:06:18,500 --> 00:06:19,570
a my nebudeme
o tom mluvit teď.

137
00:06:19,570 --> 00:06:21,319
Ale můžete nejspíš
přijít na to, co je potřeba

138
00:06:21,319 --> 00:06:24,610
je třeba udělat jen tím, že sledování tohoto videa.

139
00:06:24,610 --> 00:06:28,910
>> Proto jsme izolované X. X je uzel
chceme vymazat ze seznamu.

140
00:06:28,910 --> 00:06:30,140
Co děláme?

141
00:06:30,140 --> 00:06:32,800
Za prvé, musíme přeskupit
vnější ukazatele.

142
00:06:32,800 --> 00:06:35,815
Musíme změnit uspořádání
9 je vedle přeskočit 13

143
00:06:35,815 --> 00:06:38,030
a bod, který 10--
je to, co jsme právě udělali.

144
00:06:38,030 --> 00:06:41,180
A musíme také
přeskupit 10 je Předchozí

145
00:06:41,180 --> 00:06:44,610
poukázat na 9. místo a ukázal na 13.

146
00:06:44,610 --> 00:06:46,490
>> Takže znovu, to bylo
diagram začít.

147
00:06:46,490 --> 00:06:47,730
To byl náš řetězec.

148
00:06:47,730 --> 00:06:51,027
Musíme přeskočit 13,
ale musíme také zachovat

149
00:06:51,027 --> 00:06:52,110
celistvost seznamu.

150
00:06:52,110 --> 00:06:54,680
Nechceme ztratit jakýkoli
Informace v obou směrech.

151
00:06:54,680 --> 00:06:59,620
Proto musíme přeskupit
Ukazatele pečlivě

152
00:06:59,620 --> 00:07:02,240
takže neporušují řetěz vůbec.

153
00:07:02,240 --> 00:07:05,710
>> Takže můžeme říci 9 Next ukazatel
poukazuje na stejné místo

154
00:07:05,710 --> 00:07:08,040
že třináct Příští
Ukazatel poukazuje právě teď.

155
00:07:08,040 --> 00:07:10,331
Vzhledem k tomu, že jsme se nakonec
bude chtít přeskočit 13.

156
00:07:10,331 --> 00:07:13,750
Takže tam, kde 13 bodů další, vám
Chcete-nine tam bodu místo.

157
00:07:13,750 --> 00:07:15,200
Tak to je to.

158
00:07:15,200 --> 00:07:20,370
A pak tam, kde 13 bodů zpět
se, co nastane dříve 13,

159
00:07:20,370 --> 00:07:24,800
Chceme 10 bodu
se, že místo 13.

160
00:07:24,800 --> 00:07:29,290
A teď si všimnout, pokud budete postupovat
šipky, můžeme klesnout 13

161
00:07:29,290 --> 00:07:32,380
aniž by ve skutečnosti ztráty jakékoli informace.

162
00:07:32,380 --> 00:07:36,002
Jsme stále integrity seznamu
Posunutím obou dopředu a dozadu.

163
00:07:36,002 --> 00:07:38,210
A pak můžeme prostě tak nějak
z uklidit trochu

164
00:07:38,210 --> 00:07:40,930
zatažením seznamu dohromady.

165
00:07:40,930 --> 00:07:43,270
Takže jsme přeskupila
ukazatele na obou stranách.

166
00:07:43,270 --> 00:07:46,231
A pak jsme osvobodil x
Uzel, který obsahoval 13,

167
00:07:46,231 --> 00:07:47,480
a neměli přerušit řetěz.

168
00:07:47,480 --> 00:07:50,980
Tak jsme udělali dobře.

169
00:07:50,980 --> 00:07:53,000
>> Závěrečná poznámka tady na spojových seznamů.

170
00:07:53,000 --> 00:07:55,990
Tak jak singly- a dvojnásobně vázané
seznamy, jak jsme viděli,

171
00:07:55,990 --> 00:07:58,959
Podpora skutečně efektivní vkládání
a vymazání prvků.

172
00:07:58,959 --> 00:08:00,750
Můžete si skoro dělat
to v konstantním čase.

173
00:08:00,750 --> 00:08:03,333
Co musíme udělat vymazat
prvek jen sekunda?

174
00:08:03,333 --> 00:08:04,440
Přestěhovali jsme se jeden ukazatel.

175
00:08:04,440 --> 00:08:05,920
Přestěhovali jsme další ukazatel.

176
00:08:05,920 --> 00:08:07,915
Osvobodil jsme X-- trvalo tři operace.

177
00:08:07,915 --> 00:08:14,500
Vždy trvá tři operace na
odstranit, node-- uvolnit uzel.

178
00:08:14,500 --> 00:08:15,280
>> Jak můžeme vložit?

179
00:08:15,280 --> 00:08:17,280
No, my jsme prostě vždycky
připínání na začátku

180
00:08:17,280 --> 00:08:19,400
jestli máme vkládání efektivně.

181
00:08:19,400 --> 00:08:21,964
Proto musíme rearrange--
V závislosti na tom, zda je to

182
00:08:21,964 --> 00:08:24,380
singly- nebo dvojitě-vázané
seznam, možná musíme udělat tři

183
00:08:24,380 --> 00:08:26,824
nebo čtyři operace max.

184
00:08:26,824 --> 00:08:28,365
Ale na druhou stranu, je to vždy tři nebo čtyři.

185
00:08:28,365 --> 00:08:30,531
Nezáleží na tom, kolik
prvky jsou v našem seznamu,

186
00:08:30,531 --> 00:08:33,549
je to vždy tři nebo čtyři operations--
stejně jako vypuštění je vždy

187
00:08:33,549 --> 00:08:35,320
tři nebo čtyři operace.

188
00:08:35,320 --> 00:08:36,919
Je to konstantní čas.

189
00:08:36,919 --> 00:08:38,169
Tak to je opravdu skvělé.

190
00:08:38,169 --> 00:08:40,620
>> S poli, jsme dělali
něco jako vložení druhu.

191
00:08:40,620 --> 00:08:44,739
Pravděpodobně jste připomenout, že vložení
sort není konstantní algoritmus.

192
00:08:44,739 --> 00:08:46,030
Je to vlastně dost drahé.

193
00:08:46,030 --> 00:08:48,840
Tak je to mnohem lepší pro vkládání.

194
00:08:48,840 --> 00:08:51,840
Ale jak jsem se zmínil v
singly-spojený seznam videa,

195
00:08:51,840 --> 00:08:54,030
máme nevýhodu tady taky, že jo?

196
00:08:54,030 --> 00:08:57,580
Ztratili jsme schopnost
náhodně přístup k prvkům.

197
00:08:57,580 --> 00:09:02,310
Nemůžeme říci, chci prvek číslo čtyři
nebo prvek číslo 10 propojeného seznamu

198
00:09:02,310 --> 00:09:04,990
stejným způsobem, že můžeme
tomu, že s řadou

199
00:09:04,990 --> 00:09:08,630
Nebo můžeme jen přímo index
do elementu naší nabídku je.

200
00:09:08,630 --> 00:09:10,930
>> A tak se snaží najít
prvek v Google list--

201
00:09:10,930 --> 00:09:15,880
pokud vyhledávání DŮLEŽITÉ
Nyní může trvat lineární čas.

202
00:09:15,880 --> 00:09:18,330
Jak se seznam dostane delší, to
může trvat další krok

203
00:09:18,330 --> 00:09:22,644
pro každé jednotlivé součásti v seznamu v
s cílem nalézt to, co hledáme.

204
00:09:22,644 --> 00:09:23,560
Takže je tu kompromisy.

205
00:09:23,560 --> 00:09:25,780
Je tu trochu profík
a con prvkem je zde.

206
00:09:25,780 --> 00:09:29,110
>> A dvojnásobně-spojové seznamy nejsou
Poslední druh kombinace datové struktury

207
00:09:29,110 --> 00:09:32,840
že budeme mluvit o,
přičemž všechny základní budovy

208
00:09:32,840 --> 00:09:34,865
bloky C byl dávat dohromady.

209
00:09:34,865 --> 00:09:37,900
Protože ve skutečnosti, můžeme
ještě lépe, než to

210
00:09:37,900 --> 00:09:41,970
vytvořit strukturu dat, která
byste měli být schopni prohledávat

211
00:09:41,970 --> 00:09:43,360
v konstantním čase také.

212
00:09:43,360 --> 00:09:46,080
Ale o tom více v jiném videu.

213
00:09:46,080 --> 00:09:47,150
>> Jsem Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
To je CS50.

215
00:09:49,050 --> 00:09:50,877