1
00:00:00,000 --> 00:00:03,381
>> [Predvaja glasba]

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

3
00:00:04,604 --> 00:00:05,520
Doug LLOYD: V redu.

4
00:00:05,520 --> 00:00:07,860
Torej, če ste pravkar končali, da
video na posamezno povezanih seznamov Žal

5
00:00:07,860 --> 00:00:09,568
Pustila sem te odpravite na
malo Cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Ampak sem vesela, da si tu, da konča
zgodba dvakrat povezanih seznamov.

7
00:00:12,790 --> 00:00:15,250
>> Torej, če se spomnimo iz
da je video, smo se pogovarjali

8
00:00:15,250 --> 00:00:18,500
o tem, kako posamezno vezan
Seznami storiti udeležijo naše sposobnosti

9
00:00:18,500 --> 00:00:22,090
da se ukvarjajo z informacijami
kjer je število elementov

10
00:00:22,090 --> 00:00:24,442
ali število predmetov v
seznam lahko raste ali skrči.

11
00:00:24,442 --> 00:00:26,400
Mi lahko zdaj ukvarjajo z
nekaj takega, kjer

12
00:00:26,400 --> 00:00:28,310
ne moremo ukvarjati z njo z nizi.

13
00:00:28,310 --> 00:00:30,560
>> Vendar pa ne trpijo zaradi ene
kritična omejitev, ki

14
00:00:30,560 --> 00:00:33,790
se da s posamezno vezan
seznam, bomo lahko samo kdaj premakniti

15
00:00:33,790 --> 00:00:36,200
v eni smeri skozi seznam.

16
00:00:36,200 --> 00:00:39,010
In edini pravi položaj
če se to lahko postane problem

17
00:00:39,010 --> 00:00:41,250
je bilo, ko smo poskušali
Brisanje en element.

18
00:00:41,250 --> 00:00:46,000
In nismo niti razpravljali, kako to storiti
v posamezno povezano-seznama v psevdokoda.

19
00:00:46,000 --> 00:00:48,797
Prav gotovo je izvedljivo, vendar
je lahko malo težav.

20
00:00:48,797 --> 00:00:50,630
Torej, če se znajdete
V situaciji, ko

21
00:00:50,630 --> 00:00:53,175
skušate izbrisati
posameznih elementov iz seznama

22
00:00:53,175 --> 00:00:55,430
ali pa se dogaja, da se zahteva
da boste izbrisali

23
00:00:55,430 --> 00:00:57,970
posamezni elementi iz
seznam, boste morda želeli

24
00:00:57,970 --> 00:01:02,090
da razmisli z uporabo dvojno vezan
Seznam namesto posamezno povezano-seznam.

25
00:01:02,090 --> 00:01:06,320
Ker ti dvojno povezani-seznami omogočajo
premakniti tako naprej in nazaj

26
00:01:06,320 --> 00:01:09,340
po seznamu namesto
samo naprej skozi list--

27
00:01:09,340 --> 00:01:13,950
samo z dodajanjem enega dodatnega elementa
za našo opredelitvijo strukture

28
00:01:13,950 --> 00:01:16,690
za dvojno povezan seznam-vozlišče.

29
00:01:16,690 --> 00:01:19,770
>> Še enkrat, če ne boš šel k
se brisanje posamezne elemente

30
00:01:19,770 --> 00:01:24,810
od list-- ker smo dodajanjem
dodatno polje za našo strukturo

31
00:01:24,810 --> 00:01:28,340
definiciji vozlišča sami
za dvojno povezanih seznamov

32
00:01:28,340 --> 00:01:29,550
se bodo večji.

33
00:01:29,550 --> 00:01:31,600
Ti boš, da sprejmejo
do več bajtov pomnilnika.

34
00:01:31,600 --> 00:01:34,160
In tako, če to ni nekaj,
boste morali storiti,

35
00:01:34,160 --> 00:01:36,300
morda ste se odločili, da je
ni vredno trade off

36
00:01:36,300 --> 00:01:39,360
bi morali porabiti dodatnih
bajtov pomnilnika obvezna

37
00:01:39,360 --> 00:01:43,940
za dvojno povezano-seznam, če niste
dogaja se, da izbrišete posamezne elemente.

38
00:01:43,940 --> 00:01:46,760
Ampak oni so tudi kul
za preveč drugih stvari.

39
00:01:46,760 --> 00:01:51,260
>> Torej, kot sem že dejal, bomo morali dodati
eno samo polje za našo strukturo

40
00:01:51,260 --> 00:01:55,360
definition-- ta pojem
prejšnje kazalca.

41
00:01:55,360 --> 00:01:58,620
Torej s posamezno povezano-seznama, smo
imajo vrednost in Next kazalec,

42
00:01:58,620 --> 00:02:02,850
zato je še toliko bolj povezani-seznam ima samo
način, da se umakne nazaj, kot tudi.

43
00:02:02,850 --> 00:02:04,960
>> Zdaj v posamezno povezana,
seznam video, smo se pogovarjali

44
00:02:04,960 --> 00:02:07,210
o teh pet izmed
Glavne stvari, ki jih potrebujejo, da bi

45
00:02:07,210 --> 00:02:09,449
sposobni narediti za delo s povezanimi seznamov.

46
00:02:09,449 --> 00:02:12,880
In za večino od njih je dejstvo,
da je to dvojno vezan seznam

47
00:02:12,880 --> 00:02:14,130
ni res velik skok.

48
00:02:14,130 --> 00:02:17,936
Še vedno lahko poiščete s pomočjo, ki ga pravkar
napreduje od začetka do konca.

49
00:02:17,936 --> 00:02:20,810
Še vedno lahko ustvarite vozlišče izven
tanek zrak, precej na enak način.

50
00:02:20,810 --> 00:02:23,591
Lahko izbrisati sezname precej
skoraj enak način preveč.

51
00:02:23,591 --> 00:02:25,340
Edine stvari, ki
so nekoliko drugačna,

52
00:02:25,340 --> 00:02:28,970
Res, vstavljate
nova vozlišča v seznamu,

53
00:02:28,970 --> 00:02:33,722
in bomo končno govorimo o brisanju
en sam element, s seznama, kot tudi.

54
00:02:33,722 --> 00:02:35,430
Again, precej
ostali trije, smo

55
00:02:35,430 --> 00:02:37,888
Ne bom govoril o njih
prav zdaj, ker oni so samo

56
00:02:37,888 --> 00:02:43,920
zelo majhnim poteg na idejah razpravljali
v posamezno povezano-seznam video.

57
00:02:43,920 --> 00:02:46,292
>> Torej, kaj je vstaviti novo vozlišče
v dvojno povezanih seznamu.

58
00:02:46,292 --> 00:02:48,750
Pogovarjali smo se o tem, za
posamič-vezan seznamov, kot tudi,

59
00:02:48,750 --> 00:02:52,020
vendar pa je nekaj ekstra
ujame z dvakrat povezanih seznamov.

60
00:02:52,020 --> 00:02:55,280
Mi smo [? poteka?] v glavi izmed
seznam tukaj in nekaj arbitrarna vrednost,

61
00:02:55,280 --> 00:02:58,600
in želimo, da bi dobili novo glavo
seznama iz te funkcije.

62
00:02:58,600 --> 00:03:01,414
Zato je vrne dllnode zvezdo.

63
00:03:01,414 --> 00:03:02,330
Torej, kaj so koraki?

64
00:03:02,330 --> 00:03:04,496
So spet zelo podobni
za posamezno povezane sezname

65
00:03:04,496 --> 00:03:05,670
z enim dodatnim dodatkom.

66
00:03:05,670 --> 00:03:08,900
Želimo, da namenja prostor za novo
vozlišče in preverite, da se prepričajte, da je veljavna.

67
00:03:08,900 --> 00:03:11,510
Želimo, da zapolni to vozlišče up
vse podatke, ki smo

68
00:03:11,510 --> 00:03:12,564
želijo dati v njem.

69
00:03:12,564 --> 00:03:15,480
Zadnja stvar, moramo do--
extra stvar, moramo storiti, rather--

70
00:03:15,480 --> 00:03:19,435
je, da se določi Prejšnji kazalec
starega glavo seznama.

71
00:03:19,435 --> 00:03:21,310
Ne pozabite, da zato, ker
dvakrat povezani, seznami,

72
00:03:21,310 --> 00:03:23,110
lahko gremo naprej
in backwards-- ki

73
00:03:23,110 --> 00:03:27,080
pomeni, da je vsako vozlišče dejansko poudarja
na dveh drugih vozlišč namesto samo enega.

74
00:03:27,080 --> 00:03:29,110
In zato moramo popraviti
stara glava seznama

75
00:03:29,110 --> 00:03:32,151
za nazaj kaže na novo vodjo
povezano seznam, ki je bil nekaj

76
00:03:32,151 --> 00:03:33,990
mi ni bilo treba storiti, preden.

77
00:03:33,990 --> 00:03:37,420
In tako kot prej, samo se vrnete
kazalec na novi vodja seznama.

78
00:03:37,420 --> 00:03:38,220
>> Torej, tukaj je seznam.

79
00:03:38,220 --> 00:03:40,144
Želimo, da vstavite 12 v tem seznamu.

80
00:03:40,144 --> 00:03:42,060
Opazimo, da je diagram
je nekoliko drugačna.

81
00:03:42,060 --> 00:03:47,710
Vsako vozlišče vsebuje tri fields--
podatkov, in Next kazalec v rdeči barvi,

82
00:03:47,710 --> 00:03:50,170
ter Prejšnja kazalec v modri barvi.

83
00:03:50,170 --> 00:03:54,059
Nič ne pride pred 15. vozlišča,
zato njeno Prejšnja kazalec je nična.

84
00:03:54,059 --> 00:03:55,350
To je začetek seznama.

85
00:03:55,350 --> 00:03:56,560
Nič ni pred njim.

86
00:03:56,560 --> 00:04:03,350
In nič ne pride po 10 vozlišča, in
tako da je naslednji kazalec je nična, kot dobro.

87
00:04:03,350 --> 00:04:05,616
>> Torej, kaj je dodati 12 na tem seznamu.

88
00:04:05,616 --> 00:04:08,070
Potrebujemo [neslišno] prostor za vozlišče.

89
00:04:08,070 --> 00:04:11,480
Mi je dal 12 notranjost nje.

90
00:04:11,480 --> 00:04:14,840
In potem spet, moramo biti res
Pazite, da ne bi prekinil verigo.

91
00:04:14,840 --> 00:04:17,144
Želimo, da preurediti
kazalci v pravilnem vrstnem redu.

92
00:04:17,144 --> 00:04:19,519
In včasih, da bi mean--
kot bomo videli, zlasti

93
00:04:19,519 --> 00:04:24,120
z delete-- da imamo nekaj
odveč kazalci, ampak to je v redu.

94
00:04:24,120 --> 00:04:25,750
>> Torej, kaj želimo storiti najprej?

95
00:04:25,750 --> 00:04:28,290
Jaz bi priporočal
Stvari morate verjetno

96
00:04:28,290 --> 00:04:35,350
storiti je, da izpolnite kazalce od 12
vozlišče preden se boste dotaknili kdo drug.

97
00:04:35,350 --> 00:04:38,640
Torej, kaj je 12 dogaja, da kaže na naslednji?

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

99
00:04:39,860 --> 00:04:42,430
Kaj pride pred 12.?

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

101
00:04:43,640 --> 00:04:46,280
Zdaj smo zasedena
dodatne informacije v 12

102
00:04:46,280 --> 00:04:49,320
tako da ima Prejšnja, Naslednja, in vrednost.

103
00:04:49,320 --> 00:04:53,505
>> Zdaj imamo lahko 15-- to dodatno
korak smo govorili about-- mi

104
00:04:53,505 --> 00:04:56,590
ima lahko 15 pik nazaj do 12.

105
00:04:56,590 --> 00:04:59,634
In zdaj lahko gremo glavo
povezano seznam, da tudi 12.

106
00:04:59,634 --> 00:05:02,550
Torej, to je precej podoben temu, kar smo
počeli s posamezno povezanih seznamov,

107
00:05:02,550 --> 00:05:06,940
razen dodatnim korakom
vezni staro glavo seznamu

108
00:05:06,940 --> 00:05:09,810
nazaj na novo glavo seznama.

109
00:05:09,810 --> 00:05:12,170
>> Zdaj pa končno brisanje
vozlišče iz povezanega seznama.

110
00:05:12,170 --> 00:05:14,350
Torej, recimo, da imamo
nekatere druge funkcije, ki

111
00:05:14,350 --> 00:05:18,080
je najti vozlišče želimo izbrisati
in nam je dal kazalec za točno

112
00:05:18,080 --> 00:05:19,710
vozlišče, ki ga želimo izbrisati.

113
00:05:19,710 --> 00:05:22,360
Mi sploh ne need-- reči
Glava je še vedno globalno razglašena.

114
00:05:22,360 --> 00:05:23,590
Mi ne potrebujemo glavo tukaj.

115
00:05:23,590 --> 00:05:26,830
Vse to funkcija počne, je, ki smo jih
Najdenih kazalec ravno mi vozlišča

116
00:05:26,830 --> 00:05:28,090
želijo znebiti.

117
00:05:28,090 --> 00:05:28,940
Oglejmo znebiti tega.

118
00:05:28,940 --> 00:05:31,859
To je veliko lažje z
dvojno povezani seznam.

119
00:05:31,859 --> 00:05:33,650
First-- da je dejansko
le nekaj stvari.

120
00:05:33,650 --> 00:05:38,760
Vedeti pa je treba, da se določi okolico
kazalci vozlišč ", tako da jih preskočimo

121
00:05:38,760 --> 00:05:40,240
vozlišče želimo izbrisati.

122
00:05:40,240 --> 00:05:43,484
In potem bomo lahko izbrišete to vozlišče.

123
00:05:43,484 --> 00:05:45,150
Torej še enkrat, smo le, da bo tu skozi.

124
00:05:45,150 --> 00:05:49,625
Očitno smo se odločili, da
želimo izbrisati X. vozlišča

125
00:05:49,625 --> 00:05:51,500
In še enkrat, kaj sem
početje here--, ki jih way--

126
00:05:51,500 --> 00:05:54,580
je splošni primer za
vozlišče, ki je v sredini.

127
00:05:54,580 --> 00:05:56,547
Obstaja nekaj
extra opozorili, da ste

128
00:05:56,547 --> 00:05:59,380
morali razmisliti, ko ste izbrisali
na samem začetku seznama

129
00:05:59,380 --> 00:06:01,040
ali zelo konec seznama.

130
00:06:01,040 --> 00:06:03,730
Tukaj je nekaj posebnega
primeri corner, da se ukvarjajo s tam.

131
00:06:03,730 --> 00:06:07,960
>> Torej, to deluje za brisanje kateregakoli vozlišča
v sredini list-- tistega, ki

132
00:06:07,960 --> 00:06:11,550
ima legitimno kazalec naprej
in legitimna kazalec nazaj,

133
00:06:11,550 --> 00:06:14,460
legitimno Prejšnji in Naslednji kazalec.

134
00:06:14,460 --> 00:06:16,530
Še enkrat, če ste delajo
s konci, ki jih

135
00:06:16,530 --> 00:06:18,500
potrebe po obdelavi tistih
nekoliko drugače,

136
00:06:18,500 --> 00:06:19,570
in ne bomo do
govoriti o tem zdaj.

137
00:06:19,570 --> 00:06:21,319
Vendar pa boste verjetno lahko
ugotovimo, kaj je potrebno

138
00:06:21,319 --> 00:06:24,610
treba storiti samo z gledanjem ta video.

139
00:06:24,610 --> 00:06:28,910
>> Torej smo izolirali X. X je vozlišče
želimo izbrisati iz seznama.

140
00:06:28,910 --> 00:06:30,140
Kaj počnemo?

141
00:06:30,140 --> 00:06:32,800
Najprej moramo preurediti
zunanja kazalci.

142
00:06:32,800 --> 00:06:35,815
Moramo preurediti
9 je zraven preskočiti 13

143
00:06:35,815 --> 00:06:38,030
in točka, 10--, ki
je tisto, kar smo pravkar končali.

144
00:06:38,030 --> 00:06:41,180
In moramo tudi
preurediti 10 je Prejšnja

145
00:06:41,180 --> 00:06:44,610
izpostaviti 9 namesto kaže na 13.

146
00:06:44,610 --> 00:06:46,490
>> Torej še enkrat, to je bil
diagram za začetek.

147
00:06:46,490 --> 00:06:47,730
To je bil naš verige.

148
00:06:47,730 --> 00:06:51,027
Moramo preskočiti 13,
vendar moramo tudi ohraniti

149
00:06:51,027 --> 00:06:52,110
celovitost seznama.

150
00:06:52,110 --> 00:06:54,680
Ne želimo izgubiti koli
informacije v obe smeri.

151
00:06:54,680 --> 00:06:59,620
Zato moramo preurediti
so kazalci previdno

152
00:06:59,620 --> 00:07:02,240
tako da ne bomo prekinili verigo sploh.

153
00:07:02,240 --> 00:07:05,710
>> Tako lahko rečemo, 9 Next kazalec
opozarja na istem mestu

154
00:07:05,710 --> 00:07:08,040
da je trinajst Next
Kazalec kaže zdaj.

155
00:07:08,040 --> 00:07:10,331
Ker smo na koncu
bomo želeli preskočiti 13.

156
00:07:10,331 --> 00:07:13,750
Torej, kjerkoli 13 točk zraven vas
želijo devet tam namesto točko.

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

158
00:07:15,200 --> 00:07:20,370
In potem kamorkoli 13 točk nazaj
da, kar pride pred 13.,

159
00:07:20,370 --> 00:07:24,800
želimo 10 do točke
tistemu namesto 13.

160
00:07:24,800 --> 00:07:29,290
Zdaj opazili, če boste sledili
puščice, da lahko spusti 13

161
00:07:29,290 --> 00:07:32,380
ne da bi dejansko izgubili vse podatke.

162
00:07:32,380 --> 00:07:36,002
Mi smo ohranil celovitost seznamu
premika naprej in nazaj.

163
00:07:36,002 --> 00:07:38,210
In potem bomo lahko nekako
, da počisti malo

164
00:07:38,210 --> 00:07:40,930
s potegom seznam skupaj.

165
00:07:40,930 --> 00:07:43,270
Tako smo preuredili
kazalci na obeh straneh.

166
00:07:43,270 --> 00:07:46,231
In potem smo osvobojeni x
vozlišča, ki je vseboval 13,

167
00:07:46,231 --> 00:07:47,480
in nismo prekinili verigo.

168
00:07:47,480 --> 00:07:50,980
Tako smo naredili dobro.

169
00:07:50,980 --> 00:07:53,000
>> Končna opomba tukaj na povezanih seznamih.

170
00:07:53,000 --> 00:07:55,990
Torej tako singly- in dvojno vezan
sezname, kot smo videli,

171
00:07:55,990 --> 00:07:58,959
Podpora za res učinkovito vstavljanje
in brisanje elementov.

172
00:07:58,959 --> 00:08:00,750
Lahko precej storiti
je v nenehnem času.

173
00:08:00,750 --> 00:08:03,333
Kaj moramo storiti, da se črta
element le sekundo?

174
00:08:03,333 --> 00:08:04,440
Preselili smo se en kazalec.

175
00:08:04,440 --> 00:08:05,920
Preselili smo se drug kazalec.

176
00:08:05,920 --> 00:08:07,915
Osvobojeni smo X-- vzel tri operacije.

177
00:08:07,915 --> 00:08:14,500
Vedno traja tri operacije na
izbrisati to node-- sprostiti vozlišče.

178
00:08:14,500 --> 00:08:15,280
>> Kako vstaviti?

179
00:08:15,280 --> 00:08:17,280
No, mi smo samo vedno
zlepljenje na začetku

180
00:08:17,280 --> 00:08:19,400
če bomo učinkovito vstavljanje.

181
00:08:19,400 --> 00:08:21,964
Zato moramo rearrange--
odvisno od tega, če je

182
00:08:21,964 --> 00:08:24,380
singly- ali dvojno vezan
seznam, bomo morda morali narediti tri

183
00:08:24,380 --> 00:08:26,824
ali štirih operacijah maks.

184
00:08:26,824 --> 00:08:28,365
Ampak še enkrat, to je vedno tri ali štiri.

185
00:08:28,365 --> 00:08:30,531
Ni važno, koliko
Elementi so v našem seznamu,

186
00:08:30,531 --> 00:08:33,549
je vedno tri ali štiri operations--
tako kot izbris, je vedno

187
00:08:33,549 --> 00:08:35,320
tri ali štiri operacije.

188
00:08:35,320 --> 00:08:36,919
To je stalen čas.

189
00:08:36,919 --> 00:08:38,169
Tako da je res super.

190
00:08:38,169 --> 00:08:40,620
>> Z nizi, smo počeli
nekaj podobnega vstavljanja vrste.

191
00:08:40,620 --> 00:08:44,739
Verjetno ste se spomni, da je vključitev
nekako ni konstantna čas algoritem.

192
00:08:44,739 --> 00:08:46,030
To je pravzaprav zelo drago.

193
00:08:46,030 --> 00:08:48,840
Torej je to veliko bolje za vstavljanje.

194
00:08:48,840 --> 00:08:51,840
Toda, kot sem omenil v
posamično povezane seznam video,

195
00:08:51,840 --> 00:08:54,030
imamo negativna tudi tukaj, kajne?

196
00:08:54,030 --> 00:08:57,580
Izgubili smo sposobnost, da
naključno dostop elemente.

197
00:08:57,580 --> 00:09:02,310
Ne moremo reči, želim število elementov štiri
ali element številka 10 povezanega seznama

198
00:09:02,310 --> 00:09:04,990
na enak način, da smo lahko
to, da s paleto

199
00:09:04,990 --> 00:09:08,630
ali mi lahko samo neposredno indeks
v elementu naše Array je.

200
00:09:08,630 --> 00:09:10,930
>> In tako poskušajo najti
element v povezanem list--

201
00:09:10,930 --> 00:09:15,880
če je iskanje important--
odslej lahko linearni čas.

202
00:09:15,880 --> 00:09:18,330
Kot seznam dobi več, to
lahko traja en dodaten korak

203
00:09:18,330 --> 00:09:22,644
za vsak element v seznamu v
da bi našli tisto, kar iščete.

204
00:09:22,644 --> 00:09:23,560
Torej je trgovinske off.

205
00:09:23,560 --> 00:09:25,780
Tam je malo pro
in con element tukaj.

206
00:09:25,780 --> 00:09:29,110
>> In še toliko bolj povezani, seznami niso
zadnja vrsta strukture podatkov kombinaciji

207
00:09:29,110 --> 00:09:32,840
da bomo govorili o tem,
ob vse osnovne stavbe na

208
00:09:32,840 --> 00:09:34,865
bloki C dajanje skupaj.

209
00:09:34,865 --> 00:09:37,900
Ker v resnici, smo lahko
še boljše kot to

210
00:09:37,900 --> 00:09:41,970
ustvariti podatkovno strukturo, ki
boste morda lahko iskali s pomočjo

211
00:09:41,970 --> 00:09:43,360
v stalnem času preveč.

212
00:09:43,360 --> 00:09:46,080
Ampak več o tem v drugem videu.

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

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

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