1
00:00:00,000 --> 00:00:03,381
>> [Prehrávanie hudby]

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

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Dobre.

4
00:00:05,520 --> 00:00:07,860
Takže ak ste práve dokončili, že
video na single-previazané zoznamy prepáčte

5
00:00:07,860 --> 00:00:09,568
Nechal som ťa preč na
trochu Cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Ale som rád, že si tu až do konca
Príbeh dvojito spojových zoznamov.

7
00:00:12,790 --> 00:00:15,250
>> Takže ak si spomínate z
že video, sme sa rozprávali

8
00:00:15,250 --> 00:00:18,500
o tom, ako jednotlivo viazané
Zoznamy robiť navštevovať našu schopnosť

9
00:00:18,500 --> 00:00:22,090
sa vysporiadať s informáciami
kde počet prvkov

10
00:00:22,090 --> 00:00:24,442
alebo počet kusov
zoznam môže rásť alebo zmenšiť.

11
00:00:24,442 --> 00:00:26,400
Teraz môžeme riešiť
niečo také, kde

12
00:00:26,400 --> 00:00:28,310
nemohli sme sa s tým vyrovnať s poli.

13
00:00:28,310 --> 00:00:30,560
>> Ale oni trpia jedného
kritická obmedzenia, ktoré

14
00:00:30,560 --> 00:00:33,790
sa, že s jednotlivo viazané
zoznam, môžeme len niekedy pohnúť

15
00:00:33,790 --> 00:00:36,200
v jednom smere v zozname.

16
00:00:36,200 --> 00:00:39,010
A jediný skutočný stav
kde, že sa môže stať problémom

17
00:00:39,010 --> 00:00:41,250
bolo, keď sme sa snažili
Odstránenie jedného prvku.

18
00:00:41,250 --> 00:00:46,000
A my sme ani diskutovať o tom, ako na to
v single-Google zoznamu v pseudokódu.

19
00:00:46,000 --> 00:00:48,797
To je určite možné, ale
to môže byť trochu zmätkov.

20
00:00:48,797 --> 00:00:50,630
Takže ak sa ocitnete
v situácii, keď

21
00:00:50,630 --> 00:00:53,175
sa snažíte zmazať
jednotlivé prvky zo zoznamu

22
00:00:53,175 --> 00:00:55,430
alebo to bude potrebné
že budete mazanie

23
00:00:55,430 --> 00:00:57,970
jednotlivé prvky z
zoznamu, možno budete chcieť

24
00:00:57,970 --> 00:01:02,090
zvážiť použitie dvojnásobne viazaný
Zoznam miesto single-previazaný zoznam.

25
00:01:02,090 --> 00:01:06,320
Vzhľadom k tomu, dvojito spojové zoznamy vám umožňujú
do pohybovať oboma dopredu a dozadu

26
00:01:06,320 --> 00:01:09,340
v zozname namiesto
len dopredu cez list--

27
00:01:09,340 --> 00:01:13,950
len tým, že pridá jeden navyše prvok
na našej definície štruktúry

28
00:01:13,950 --> 00:01:16,690
Pre dvojito Google zoznamu uzla.

29
00:01:16,690 --> 00:01:19,770
>> Opäť platí, že ak sa nebudeme
byť mazanie jednotlivých prvkov

30
00:01:19,770 --> 00:01:24,810
od list-- pretože sme pridávanie
navyše pole k našej štruktúre

31
00:01:24,810 --> 00:01:28,340
definície, samotné uzly
pre dvojito spojových zoznamov

32
00:01:28,340 --> 00:01:29,550
sa bude väčšia.

33
00:01:29,550 --> 00:01:31,600
Chystajú sa vziať
up viac bajtov pamäte.

34
00:01:31,600 --> 00:01:34,160
A tak, ak to nie je niečo,
budete musieť urobiť,

35
00:01:34,160 --> 00:01:36,300
sa môžete rozhodnúť, že je to
nestojí za kompromis

36
00:01:36,300 --> 00:01:39,360
musieť stráviť ďalšie
bajtov pamäte požadované

37
00:01:39,360 --> 00:01:43,940
pre dvojito Google zoznamu, ak si nie ste
bude mazanie jednotlivých prvkov.

38
00:01:43,940 --> 00:01:46,760
Ale sú tiež v pohode
pre iné veci.

39
00:01:46,760 --> 00:01:51,260
>> Tak ako som povedal, budeme musieť pridať
jediné pole do našej štruktúre

40
00:01:51,260 --> 00:01:55,360
definition-- tento pojem
z predchádzajúcej ukazovateľ.

41
00:01:55,360 --> 00:01:58,620
Takže s single-prepojenom zoznamu, my
mať hodnotu A ďalší ukazovateľ,

42
00:01:58,620 --> 00:02:02,850
takže dvojito previazaný zoznam jednoducho musí
spôsob, ako sa pohybovať späť rovnako.

43
00:02:02,850 --> 00:02:04,960
>> Teraz v single-spojený
Zoznam video, hovorili sme

44
00:02:04,960 --> 00:02:07,210
o nich je päť
hlavné veci, ktoré je potrebné

45
00:02:07,210 --> 00:02:09,449
schopný robiť prácu s spojových zoznamov.

46
00:02:09,449 --> 00:02:12,880
A pre väčšinu z nich je skutočnosť,
že je to dvojnásobne viazaný zoznam

47
00:02:12,880 --> 00:02:14,130
nie je naozaj veľký skok.

48
00:02:14,130 --> 00:02:17,936
Stále môžeme prehľadávať obyčajným
dopredu od začiatku až do konca.

49
00:02:17,936 --> 00:02:20,810
Stále môžeme vytvoriť uzol von
riedky vzduch, skoro rovnakým spôsobom.

50
00:02:20,810 --> 00:02:23,591
Môžeme zmazať zoznamy dosť
veľa rovnaký cesta taky.

51
00:02:23,591 --> 00:02:25,340
Jediné veci, ktoré
sú nepatrne odlišné,

52
00:02:25,340 --> 00:02:28,970
Naozaj, vkladáte
nové uzly do zoznamu,

53
00:02:28,970 --> 00:02:33,722
a budeme konečne hovoriť o odstraňovaní
jeden prvok zo zoznamu rovnako.

54
00:02:33,722 --> 00:02:35,430
Opäť platí, že do značnej miery
ďalšie tri, my sme

55
00:02:35,430 --> 00:02:37,888
nebude hovoriť o nich
hneď teraz, pretože sú to len

56
00:02:37,888 --> 00:02:43,920
veľmi malé vylepší sa k myšlienkam diskutovaným
V single-previazaný zoznam video.

57
00:02:43,920 --> 00:02:46,292
>> Takže poďme vložiť nový uzol
do dvojito Google zoznamu.

58
00:02:46,292 --> 00:02:48,750
Hovorili sme o tom to pre
jednotlivo viazané zoznamy tiež,

59
00:02:48,750 --> 00:02:52,020
ale je tu pár naviac
chytí s dvojito spojových zoznamov.

60
00:02:52,020 --> 00:02:55,280
Sme [? absolvovaní?] v hlave
zoznam tu a niektorí ľubovoľná hodnota,

61
00:02:55,280 --> 00:02:58,600
a chceme získať nové hlavy
zoznamu z tejto funkcie.

62
00:02:58,600 --> 00:03:01,414
To je dôvod, prečo vráti dllnode hviezdu.

63
00:03:01,414 --> 00:03:02,330
Takže aké sú kroky?

64
00:03:02,330 --> 00:03:04,496
Sú opäť veľmi podobný
sa jednotlivo viazané zoznamy

65
00:03:04,496 --> 00:03:05,670
s jednou prístelkou navyše.

66
00:03:05,670 --> 00:03:08,900
Chceme pridelí miesto pre nový
uzol a kontrola, aby sa uistil, že je platný.

67
00:03:08,900 --> 00:03:11,510
Chceme naplniť tento uzol hore
s tým, čo informácie, ktoré

68
00:03:11,510 --> 00:03:12,564
chcieť dať v ňom.

69
00:03:12,564 --> 00:03:15,480
Posledná vec, ktorú musíme do--
ďalšia vec, ktorú musíme urobiť, rather--

70
00:03:15,480 --> 00:03:19,435
je opraviť Predchádzajúci ukazovateľ
starého hlavy zoznamu.

71
00:03:19,435 --> 00:03:21,310
Pamätajte si, že preto,
z dvojito spojové zoznamy,

72
00:03:21,310 --> 00:03:23,110
sa môžeme pohnúť dopredu
a ktorý backwards--

73
00:03:23,110 --> 00:03:27,080
Znamená to, že každý uzol v skutočnosti poukazuje
ďalšími dvoma uzlami namiesto len jeden.

74
00:03:27,080 --> 00:03:29,110
A preto je treba opraviť
stará hlava zoznamu

75
00:03:29,110 --> 00:03:32,151
prejdite späť do nového šéfa
prepojený zoznam, čo bolo niečo,

76
00:03:32,151 --> 00:03:33,990
sme nemuseli robiť skôr.

77
00:03:33,990 --> 00:03:37,420
A rovnako ako predtým, len sme Vrátiť
Ukazovateľ na nového šéfa zozname.

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

79
00:03:38,220 --> 00:03:40,144
Chceme vložiť 12 do tohto zoznamu.

80
00:03:40,144 --> 00:03:42,060
Všimnite si, že diagram
sa mierne líšia.

81
00:03:42,060 --> 00:03:47,710
Každý uzol obsahuje tri fields--
dát, a ďalší ukazovateľ v červenej farbe,

82
00:03:47,710 --> 00:03:50,170
a predchádzajúce ukazovateľ v modrej farbe.

83
00:03:50,170 --> 00:03:54,059
Nič príde pred uzol 15,
tak jeho predchádzajúci ukazovateľ je null.

84
00:03:54,059 --> 00:03:55,350
Je to začiatok zoznamu.

85
00:03:55,350 --> 00:03:56,560
Je tu pred ním nič nie je.

86
00:03:56,560 --> 00:04:03,350
A nič po uzla 10 prichádza a
tak to je ďalší ukazovateľ null rovnako.

87
00:04:03,350 --> 00:04:05,616
>> Takže poďme sa pridať 12 do tohto zoznamu.

88
00:04:05,616 --> 00:04:08,070
Potrebujeme [nepočuteľný] priestor pre uzol.

89
00:04:08,070 --> 00:04:11,480
My sme dali 12 vnútri nej.

90
00:04:11,480 --> 00:04:14,840
A potom znova, musíme byť naozaj
Dajte pozor, aby ste prerušiť reťaz.

91
00:04:14,840 --> 00:04:17,144
Chceme zmeniť usporiadanie
ukazovatele v správnom poradí.

92
00:04:17,144 --> 00:04:19,519
A niekedy, že by mohli mean--
ako uvidíme obzvlášť

93
00:04:19,519 --> 00:04:24,120
s delete--, že máme nejaké
redundantné ukazovatele, ale to je v poriadku.

94
00:04:24,120 --> 00:04:25,750
>> Takže to, čo chceme urobiť ako prvé?

95
00:04:25,750 --> 00:04:28,290
Chcel by som odporučiť
veci, ktoré by pravdepodobne

96
00:04:28,290 --> 00:04:35,350
cieľov, sa naplniť ukazovatele z 12
uzol, než sa dotknete niekto iný.

97
00:04:35,350 --> 00:04:38,640
Takže to, čo sa 12 bude ukazovať na ďalší?

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

99
00:04:39,860 --> 00:04:42,430
To, čo je pred 12?

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

101
00:04:43,640 --> 00:04:46,280
Teraz sme už obsadené
ďalšie informácie v 12

102
00:04:46,280 --> 00:04:49,320
tak to má predchádzajúce, budúci, a hodnotu.

103
00:04:49,320 --> 00:04:53,505
>> Teraz môžeme mať 15-- to navyše
krokom, ktorý sme hovorili about-- my

104
00:04:53,505 --> 00:04:56,590
môže mať 15 bodov späť na 12 rokov.

105
00:04:56,590 --> 00:04:59,634
A teraz sa môžeme presunúť hlavu
prepojený zoznam tiež bude 12.

106
00:04:59,634 --> 00:05:02,550
Takže je to dosť podobné tomu, čo sme
robili s single-previazané zoznamy,

107
00:05:02,550 --> 00:05:06,940
s výnimkou pre ďalší krok
spájajúci starú hlavu zoznamu

108
00:05:06,940 --> 00:05:09,810
späť na nového šéfa zozname.

109
00:05:09,810 --> 00:05:12,170
>> Teraz poďme konečne zmazať
uzol z prepojeného zoznamu.

110
00:05:12,170 --> 00:05:14,350
Takže povedzme, že máme
niektoré ďalšie funkcie, ktorá

111
00:05:14,350 --> 00:05:18,080
je nájsť uzol chceme zmazať
a dal nám ukazovateľ presne

112
00:05:18,080 --> 00:05:19,710
uzol, ktorý chceme odstrániť.

113
00:05:19,710 --> 00:05:22,360
Nemáme ani need-- hovoria
Hlava je stále globálne deklarovaný.

114
00:05:22,360 --> 00:05:23,590
My to tu nie je treba hlavu.

115
00:05:23,590 --> 00:05:26,830
Všetky tieto funkcie robí, je máme
našiel ukazovateľ presne na uzle my

116
00:05:26,830 --> 00:05:28,090
chcú zbaviť.

117
00:05:28,090 --> 00:05:28,940
Poďme sa zbaviť toho.

118
00:05:28,940 --> 00:05:31,859
Je to oveľa jednoduchšie s
dvojito spojený zoznamy.

119
00:05:31,859 --> 00:05:33,650
First-- je to vlastne
Len pár vecí.

120
00:05:33,650 --> 00:05:38,760
Potrebujeme len opraviť okolí
ukazovatele uzlov, "tak, aby preskočiť

121
00:05:38,760 --> 00:05:40,240
uzol chceme odstrániť.

122
00:05:40,240 --> 00:05:43,484
A potom môžeme zmazať tento uzol.

123
00:05:43,484 --> 00:05:45,150
Takže znovu, my sme len tak tadiaľ.

124
00:05:45,150 --> 00:05:49,625
Zrejme sme sa rozhodli, že
chceme zmazať uzla X.

125
00:05:49,625 --> 00:05:51,500
A opäť, to, čo som si
robí here-- podľa way--

126
00:05:51,500 --> 00:05:54,580
je všeobecný prípade takéhoto
uzol, ktorý je uprostred.

127
00:05:54,580 --> 00:05:56,547
Existuje pár
ďalšie výhrady, ktoré ste

128
00:05:56,547 --> 00:05:59,380
je potrebné vziať do úvahy, keď ste mazanie
samého začiatku zoznamu

129
00:05:59,380 --> 00:06:01,040
alebo veľmi koniec zoznamu.

130
00:06:01,040 --> 00:06:03,730
K dispozícii je niekoľko špeciálnych
rohové prípady zaoberať sa tam.

131
00:06:03,730 --> 00:06:07,960
>> Tak to funguje pre vymazanie ľubovoľný uzol
v stredu list-- ten, ktorý

132
00:06:07,960 --> 00:06:11,550
má oprávnený ukazovateľ vpred
a legitímne ukazovateľ späť,

133
00:06:11,550 --> 00:06:14,460
legitímne Predchádzajúce a Ďalšie ukazovateľ.

134
00:06:14,460 --> 00:06:16,530
Opäť platí, že ak pracujete
s konci, budete

135
00:06:16,530 --> 00:06:18,500
musieť zvládnuť tie,
trochu inak,

136
00:06:18,500 --> 00:06:19,570
a my nebudeme
o tom hovoriť teraz.

137
00:06:19,570 --> 00:06:21,319
Ale môžete nejspíš
prísť na to, čo je potrebné

138
00:06:21,319 --> 00:06:24,610
je potrebné urobiť len tým, že sledovanie tohto videa.

139
00:06:24,610 --> 00:06:28,910
>> Preto sme izolované X. X je uzol
chceme vymazať zo zoznamu.

140
00:06:28,910 --> 00:06:30,140
Čo budeme robiť?

141
00:06:30,140 --> 00:06:32,800
Po prvé, musíme preskupiť
vonkajšie ukazovatele.

142
00:06:32,800 --> 00:06:35,815
Musíme zmeniť usporiadanie
9 je vedľa preskočiť 13

143
00:06:35,815 --> 00:06:38,030
a bod, ktorý 10--
je to, čo sme práve urobili.

144
00:06:38,030 --> 00:06:41,180
A musíme tiež
preskupiť 10 je Predchádzajúci

145
00:06:41,180 --> 00:06:44,610
poukázať na 9. miesto a ukázal na 13.

146
00:06:44,610 --> 00:06:46,490
>> Takže znovu, to bolo
diagram začať.

147
00:06:46,490 --> 00:06:47,730
To bol náš reťazec.

148
00:06:47,730 --> 00:06:51,027
Musíme preskočiť 13,
ale musíme tiež zachovať

149
00:06:51,027 --> 00:06:52,110
celistvosť zoznamu.

150
00:06:52,110 --> 00:06:54,680
Nechceme stratiť akýkoľvek
Informácie v oboch smeroch.

151
00:06:54,680 --> 00:06:59,620
Preto musíme preskupiť
Ukazovatele starostlivo

152
00:06:59,620 --> 00:07:02,240
takže neporušujú reťaz vôbec.

153
00:07:02,240 --> 00:07:05,710
>> Takže môžeme povedať 9 Next ukazovateľ
poukazuje na rovnaké miesto

154
00:07:05,710 --> 00:07:08,040
že trinásť Budúci
Ukazovateľ poukazuje práve teraz.

155
00:07:08,040 --> 00:07:10,331
Vzhľadom k tomu, že sme sa nakoniec
bude chcieť preskočiť 13.

156
00:07:10,331 --> 00:07:13,750
Takže tam, kde 13 bodov ďalšie, vám
Ak nine tam bodu miesto.

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

158
00:07:15,200 --> 00:07:20,370
A potom tam, kde 13 bodov späť
sa, čo nastane skôr 13,

159
00:07:20,370 --> 00:07:24,800
Chceme 10 bodu
sa, že miesto 13.

160
00:07:24,800 --> 00:07:29,290
A teraz si všimnúť, ak budete postupovať
šípky, môžeme klesnúť 13

161
00:07:29,290 --> 00:07:32,380
bez toho by v skutočnosti straty akejkoľvek informácie.

162
00:07:32,380 --> 00:07:36,002
Sme stále integrity zoznamu
Posunutím oboch dopredu a dozadu.

163
00:07:36,002 --> 00:07:38,210
A potom môžeme jednoducho tak nejako
z upratať trochu

164
00:07:38,210 --> 00:07:40,930
zatiahnutím zoznamu dohromady.

165
00:07:40,930 --> 00:07:43,270
Takže sme preskupí
ukazovatele na oboch stranách.

166
00:07:43,270 --> 00:07:46,231
A potom sme oslobodil x
Uzol, ktorý obsahoval 13,

167
00:07:46,231 --> 00:07:47,480
a nemali prerušiť reťaz.

168
00:07:47,480 --> 00:07:50,980
Tak sme urobili dobre.

169
00:07:50,980 --> 00:07:53,000
>> Záverečná poznámka tu na spojových zoznamov.

170
00:07:53,000 --> 00:07:55,990
Tak ako singly- a dvojnásobne viazané
zoznamy, ako sme videli,

171
00:07:55,990 --> 00:07:58,959
Pomoc skutočne efektívne vkladanie
a vymazanie prvkov.

172
00:07:58,959 --> 00:08:00,750
Môžete si skoro robiť
to v konštantnom čase.

173
00:08:00,750 --> 00:08:03,333
Čo musíme urobiť vymazať
prvok len sekunda?

174
00:08:03,333 --> 00:08:04,440
Presťahovali sme sa jeden ukazovateľ.

175
00:08:04,440 --> 00:08:05,920
Presťahovali sme ďalší ukazovateľ.

176
00:08:05,920 --> 00:08:07,915
Oslobodil sme X-- trvalo tri operácie.

177
00:08:07,915 --> 00:08:14,500
Vždy trvá tri operácie na
odstrániť, node-- uvoľniť uzol.

178
00:08:14,500 --> 00:08:15,280
>> Ako môžeme vložiť?

179
00:08:15,280 --> 00:08:17,280
No, my sme proste vždy
pripínanie na začiatku

180
00:08:17,280 --> 00:08:19,400
či máme vkladanie efektívne.

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

182
00:08:21,964 --> 00:08:24,380
singly- alebo dvojito-viazanej
zoznam, možno musíme urobiť tri

183
00:08:24,380 --> 00:08:26,824
alebo štyri operácie max.

184
00:08:26,824 --> 00:08:28,365
Ale na druhú stranu, je to vždy tri alebo štyri.

185
00:08:28,365 --> 00:08:30,531
Nezáleží na tom, koľko
prvky sú v našom zozname,

186
00:08:30,531 --> 00:08:33,549
je to vždy tri alebo štyri operations--
rovnako ako vypustenie je vždy

187
00:08:33,549 --> 00:08:35,320
tri alebo štyri operácie.

188
00:08:35,320 --> 00:08:36,919
Je to konštantný čas.

189
00:08:36,919 --> 00:08:38,169
Tak to je naozaj skvelé.

190
00:08:38,169 --> 00:08:40,620
>> S poli, sme robili
niečo ako vloženie druhu.

191
00:08:40,620 --> 00:08:44,739
Pravdepodobne ste pripomenúť, že vloženie
sort nie je konštantná algoritmus.

192
00:08:44,739 --> 00:08:46,030
Je to vlastne dosť drahé.

193
00:08:46,030 --> 00:08:48,840
Tak je to oveľa lepšie pre vkladanie.

194
00:08:48,840 --> 00:08:51,840
Ale ako som sa zmienil v
single-spojený zoznam 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
Stratili sme schopnosť
náhodne prístup k prvkom.

197
00:08:57,580 --> 00:09:02,310
Nemôžeme povedať, chcem prvok číslo štyri
alebo prvok číslo 10 prepojeného zoznamu

198
00:09:02,310 --> 00:09:04,990
rovnakým spôsobom, že môžeme
tomu, že s radom

199
00:09:04,990 --> 00:09:08,630
Alebo môžeme len priamo index
do elementu našej ponuku je.

200
00:09:08,630 --> 00:09:10,930
>> A tak sa snaží nájsť
prvok v Google list--

201
00:09:10,930 --> 00:09:15,880
ak vyhľadávanie DÔLEŽITÉ
Teraz môže trvať lineárny čas.

202
00:09:15,880 --> 00:09:18,330
Ako sa zoznam dostane dlhší, to
môže trvať ďalší krok

203
00:09:18,330 --> 00:09:22,644
pre každé jednotlivé súčasti v zozname v
s cieľom nájsť to, čo hľadá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 prvkom je tu.

206
00:09:25,780 --> 00:09:29,110
>> A dvojnásobne-spojové zoznamy nie sú
Posledný druh kombinácia dátové štruktúry

207
00:09:29,110 --> 00:09:32,840
že budeme hovoriť o,
pričom všetky základné budovy

208
00:09:32,840 --> 00:09:34,865
bloky C bol dávať dohromady.

209
00:09:34,865 --> 00:09:37,900
Pretože v skutočnosti, môžeme
ešte lepšie, než to

210
00:09:37,900 --> 00:09:41,970
vytvoriť štruktúru dát, ktorá
by ste mali byť schopní prehľadávať

211
00:09:41,970 --> 00:09:43,360
v konštantnom čase tiež.

212
00:09:43,360 --> 00:09:46,080
Ale o tom viac v inom videu.

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

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

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