1
00:00:00,000 --> 00:00:03,381
>> [MUZIKO Ludante]

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

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

4
00:00:05,520 --> 00:00:07,860
Do se vi ĵus finis ke
vídeo sur unuope-ligitaj listoj bedaŭras

5
00:00:07,860 --> 00:00:09,568
Mi forlasas vin en vojaĝo
iom de cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Sed mi ĝojas ke vi estas tie por fini
la rakonto de duoble-ligitaj listoj.

7
00:00:12,790 --> 00:00:15,250
>> Do se vi memoras de
ke vídeo, ni parolis

8
00:00:15,250 --> 00:00:18,500
pri kiel unuope-ligitaj
listoj fari ĉeesti nian kapablon

9
00:00:18,500 --> 00:00:22,090
trakti informo
kie la nombro de elementoj

10
00:00:22,090 --> 00:00:24,442
aŭ la nombro de artikoloj en
listo povas kreski aŭ ŝrumpi.

11
00:00:24,442 --> 00:00:26,400
Ni povas nun trakti
io simila, kie

12
00:00:26,400 --> 00:00:28,310
ni ne povis pritrakti ĝin kun tabeloj.

13
00:00:28,310 --> 00:00:30,560
>> Sed ili suferas de unu
kritika limigo kiu

14
00:00:30,560 --> 00:00:33,790
estas ke per unuope-ligitaj
listo, ni povas nur iam movas

15
00:00:33,790 --> 00:00:36,200
en sola direkto tra la listo.

16
00:00:36,200 --> 00:00:39,010
Kaj la sola reala situacio
kie kiu povas igi problemon

17
00:00:39,010 --> 00:00:41,250
estis kiam ni provis
forviŝi sola ero.

18
00:00:41,250 --> 00:00:46,000
Kaj ni eĉ ne diskuti kiel fari ĝin
en unuope-ligillisto en _pseudocode_.

19
00:00:46,000 --> 00:00:48,797
Estas certe doable, sed
ĝi povas esti iom de ĝenaĵo.

20
00:00:48,797 --> 00:00:50,630
Do se vi trovas vin
en situacio kie

21
00:00:50,630 --> 00:00:53,175
vi provas forigi
sola elementoj el la listo

22
00:00:53,175 --> 00:00:55,430
aŭ ĝi estas tuj estos postulita
ke vi estos forviŝo

23
00:00:55,430 --> 00:00:57,970
sola elementoj el
la listo, vi eble volas

24
00:00:57,970 --> 00:01:02,090
konsideri uzanta duoble-ligitaj
listo anstataŭ unuope-ligillisto.

25
00:01:02,090 --> 00:01:06,320
Ĉar duoble-ligitaj listoj permesos
movi ambaŭ antaŭen kaj malantaŭen

26
00:01:06,320 --> 00:01:09,340
tra la diskutlisto anstataŭ
nur antaŭen tra la list--

27
00:01:09,340 --> 00:01:13,950
nur aldonante unu ekstra elemento
al nia strukturo difino

28
00:01:13,950 --> 00:01:16,690
por la duoble-ligillisto nodo.

29
00:01:16,690 --> 00:01:19,770
>> Denove, se vi ne tuj
estu viŝante sola elementoj

30
00:01:19,770 --> 00:01:24,810
el la list-- ĉar ni aldono
ekstran kampo al nia strukturo

31
00:01:24,810 --> 00:01:28,340
difinon, la nodoj sin
por duoble-ligitaj listoj

32
00:01:28,340 --> 00:01:29,550
tuj estos granda.

33
00:01:29,550 --> 00:01:31,600
Ili iras preni
supren pli bajtoj de memoro.

34
00:01:31,600 --> 00:01:34,160
Do se tio ne estas io
Vi tuj bezonas fari,

35
00:01:34,160 --> 00:01:36,300
vi eble decidos ĝi estas
Ne valoras la komerco ekstere

36
00:01:36,300 --> 00:01:39,360
devos elspezi la kroman
bajtoj de memoro postulata

37
00:01:39,360 --> 00:01:43,940
por duoble-ligillisto se vi ne estas
tuj estos forviŝo sola elementoj.

38
00:01:43,940 --> 00:01:46,760
Sed ili estas ankaŭ malvarmeta
por aliaj aĵoj ankaŭ.

39
00:01:46,760 --> 00:01:51,260
>> Do kiel mi diris, ni nur devas aldoni
unu sola kampo al nia strukturo

40
00:01:51,260 --> 00:01:55,360
definition-- ĉi nocio
de antaŭa montrilo.

41
00:01:55,360 --> 00:01:58,620
Do kun unuope-ligillisto, ni
havas la valoron kaj la Sekvanta montrilon,

42
00:01:58,620 --> 00:02:02,850
do la duoble-ligillisto nur havas
manieron por movi malantaŭen tiel.

43
00:02:02,850 --> 00:02:04,960
>> Nun en la unuope-ligitaj
listo filmetoj, ni parolis

44
00:02:04,960 --> 00:02:07,210
pri tiuj estas kvin el la
ĉefa aĵoj vi bezonas esti

45
00:02:07,210 --> 00:02:09,449
kapabla fari labori kun ligitaj listoj.

46
00:02:09,449 --> 00:02:12,880
Kaj por la plej multaj el tiuj, la fakto
ke ĝi estas duoble-ligillisto

47
00:02:12,880 --> 00:02:14,130
ne vere estas granda salto.

48
00:02:14,130 --> 00:02:17,936
Ni povas ankoraŭ traserĉi per nur
antaŭeniras de komenco al fino.

49
00:02:17,936 --> 00:02:20,810
Ni ankoraŭ povos krei nodon el
maldika aero, preskaux la sama maniero.

50
00:02:20,810 --> 00:02:23,591
Ni povas forviŝi listoj bela
iom same ankaŭ.

51
00:02:23,591 --> 00:02:25,340
La nuraj aĵoj kiuj
estas subtile malsama,

52
00:02:25,340 --> 00:02:28,970
vere, estas enmeto
novaj nodoj en la listo,

53
00:02:28,970 --> 00:02:33,722
kaj ni fine paroli pri forviŝo
sola elemento el la listo ankaŭ.

54
00:02:33,722 --> 00:02:35,430
Denove, preskaux
la aliaj tri, ni estas

55
00:02:35,430 --> 00:02:37,888
Ne tuj parolos pri ili
nun ĉar ili estas nur

56
00:02:37,888 --> 00:02:43,920
tre minora retuŝojn sur la ideoj diskutitaj
en la unuope-ligillisto vídeo.

57
00:02:43,920 --> 00:02:46,292
>> Do ni enmeti novan nodon
en duoble-ligillisto.

58
00:02:46,292 --> 00:02:48,750
Ni parolis pri faranta tion ĉi por
unuope-ligitaj listoj tiel,

59
00:02:48,750 --> 00:02:52,020
Sed tie estas paro de ekstra
kaptas kun duoble-ligitaj listoj.

60
00:02:52,020 --> 00:02:55,280
Ni estas [? pasante?] en la kapo de la
listo tie kaj iuj arbitraj valoro,

61
00:02:55,280 --> 00:02:58,600
kaj ni volas atingi la novan estron
de la listo el tiu funkcio.

62
00:02:58,600 --> 00:03:01,414
Tial ĝi resendas dllnode stelo.

63
00:03:01,414 --> 00:03:02,330
Do kio estas la paŝoj?

64
00:03:02,330 --> 00:03:04,496
Ili estas, denove, tre simila
al unuope-ligitaj listoj

65
00:03:04,496 --> 00:03:05,670
kun unu ekstra aldono.

66
00:03:05,670 --> 00:03:08,900
Ni volas allocates spacon por nova
nodo kaj ĉeko por certigi ĝi estas valida.

67
00:03:08,900 --> 00:03:11,510
Ni volas plenigi tiu nodo ĝis
kun kiom informo ni

68
00:03:11,510 --> 00:03:12,564
volas meti en ĝin.

69
00:03:12,564 --> 00:03:15,480
La lasta afero ni devas do-- la
ekstraj afero ni devas fari, rather--

70
00:03:15,480 --> 00:03:19,435
estas fiksi la Antaŭa montrilon
de la maljuna kapo de la listo.

71
00:03:19,435 --> 00:03:21,310
Memoru ke ĉar
de duoble-ligitaj listoj,

72
00:03:21,310 --> 00:03:23,110
Ni povas movi antaŭen
kaj backwards-- kiu

73
00:03:23,110 --> 00:03:27,080
signifas ke ĉiu nodo indikas reale
al du aliaj nodoj anstataŭ nur unu.

74
00:03:27,080 --> 00:03:29,110
Kaj tial ni devas redifini
la malnova kapo de la listo

75
00:03:29,110 --> 00:03:32,151
atentigi dorsen al la nova estro de
la ligillisto, kiu estis iu

76
00:03:32,151 --> 00:03:33,990
ni ne devis fari antaŭe.

77
00:03:33,990 --> 00:03:37,420
Kaj kiel antaŭe, ni nur resendas
sagon al la nova kapo de la listo.

78
00:03:37,420 --> 00:03:38,220
>> Do jen listo.

79
00:03:38,220 --> 00:03:40,144
Ni volas enmeti 12 en tiun liston.

80
00:03:40,144 --> 00:03:42,060
Rimarku ke la diagramo
estas iomete malsamaj.

81
00:03:42,060 --> 00:03:47,710
Ĉiu nodo enhavas tri fields--
datumoj, kaj Next montrilon en ruĝa,

82
00:03:47,710 --> 00:03:50,170
kaj Antaŭa montrilon en blua.

83
00:03:50,170 --> 00:03:54,059
Nenio venas antaŭ la 15 nodon,
do ĝia Antaŭa puntero estas nula.

84
00:03:54,059 --> 00:03:55,350
Ĝi estas la komenco de la listo.

85
00:03:55,350 --> 00:03:56,560
Nenio antaŭ ĝi.

86
00:03:56,560 --> 00:04:03,350
Kaj nenio venas post la 10 nodo, kaj
do ĝi estas Sekva puntero estas nula krom.

87
00:04:03,350 --> 00:04:05,616
>> Do ni aldonu 12 al tiu listo.

88
00:04:05,616 --> 00:04:08,070
Ni bezonas [inaudible] spaco por la nodo.

89
00:04:08,070 --> 00:04:11,480
Ni metis 12 ene de ĝi.

90
00:04:11,480 --> 00:04:14,840
Kaj cetere, ni bezonas esti vere
atenti ne rompi la ĉenon.

91
00:04:14,840 --> 00:04:17,144
Ni volas reordigi la
punteros en la ĝusta ordo.

92
00:04:17,144 --> 00:04:19,519
Kaj foje ke povus mean--
kiel ni vidos aparte

93
00:04:19,519 --> 00:04:24,120
kun delete-- ke ni ja havas kelkajn
redunda punteros, sed tio estas bone.

94
00:04:24,120 --> 00:04:25,750
>> Do kion ni volas fari unue?

95
00:04:25,750 --> 00:04:28,290
Mi rekomendus la
aferojn vi supozeble

96
00:04:28,290 --> 00:04:35,350
fari estas plenigi la punteros de la 12
nodo antaŭ tuŝi iu alio.

97
00:04:35,350 --> 00:04:38,640
Do kio estas 12 tuj atentigi al sekva?

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

99
00:04:39,860 --> 00:04:42,430
Kio venas antaŭ 12?

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

101
00:04:43,640 --> 00:04:46,280
Nun ni plenigis la
ekstra informo en 12

102
00:04:46,280 --> 00:04:49,320
do ĝi havas antaŭa, sekva, kaj valoro.

103
00:04:49,320 --> 00:04:53,505
>> Nun ni povas havi 15-- tiu ekstra
paŝo ni parolis about-- ni

104
00:04:53,505 --> 00:04:56,590
povas havi 15 punkto reen al 12.

105
00:04:56,590 --> 00:04:59,634
Kaj nun ni povas movi la kapon de
la ligillisto ankaŭ esti 12.

106
00:04:59,634 --> 00:05:02,550
Do estas sufiĉe simila al kion ni
faris per unuope-ligitaj listoj,

107
00:05:02,550 --> 00:05:06,940
krom la ekstra paŝo de
konektante la malnova kapo de la listo

108
00:05:06,940 --> 00:05:09,810
Reen al la nova kapo de la listo.

109
00:05:09,810 --> 00:05:12,170
>> Nun ni fine forviŝi
nodo de ligillisto.

110
00:05:12,170 --> 00:05:14,350
Do diru ni havas
iu alia funkcio kiu

111
00:05:14,350 --> 00:05:18,080
estas trovanta nodo ni volas forigi
kaj donis al ni puntero al ekzakte

112
00:05:18,080 --> 00:05:19,710
la nodo ke ni volas forigi.

113
00:05:19,710 --> 00:05:22,360
Ni eĉ ne need-- diri la
kapo estas ankoraŭ tutmonde deklaris.

114
00:05:22,360 --> 00:05:23,590
Ni ne bezonas kapon tie.

115
00:05:23,590 --> 00:05:26,830
Ĉiuj ĉi funkcio faras estas ni
trovis montrilon al ekzakte la nodo ni

116
00:05:26,830 --> 00:05:28,090
volas forigi.

117
00:05:28,090 --> 00:05:28,940
Ni forigi gxin.

118
00:05:28,940 --> 00:05:31,859
Estas multe pli facile per
duoble-ligitaj listoj.

119
00:05:31,859 --> 00:05:33,650
First-- ĝi estas fakte
nur kelkaj aferoj.

120
00:05:33,650 --> 00:05:38,760
Ni simple devas redifini la ĉirkaŭa
nodoj 'punteros por ke ili transsaltu super

121
00:05:38,760 --> 00:05:40,240
la nodo ni volas forigi.

122
00:05:40,240 --> 00:05:43,484
Kaj tiam ni povas forviŝi tiu nodo.

123
00:05:43,484 --> 00:05:45,150
Do denove, ni simple tuj tra tie.

124
00:05:45,150 --> 00:05:49,625
Ni ŝajne decidis ke
ni volas forigi la nodon X.

125
00:05:49,625 --> 00:05:51,500
Kaj cetere, kion mi
faras here-- de bare

126
00:05:51,500 --> 00:05:54,580
estas ĝenerala kazo por
nodo, kio estas en la mezo.

127
00:05:54,580 --> 00:05:56,547
Estas paro de
ekstraj _caveats_ ke vi

128
00:05:56,547 --> 00:05:59,380
bezonas konsideri kiam vi forviŝo
la komenco de la listo

129
00:05:59,380 --> 00:06:01,040
aŭ la tre fino de la listo.

130
00:06:01,040 --> 00:06:03,730
Ekzistas kelkaj specialaj
angulo kazoj trakti tie.

131
00:06:03,730 --> 00:06:07,960
>> Do tiu funkcias por viŝante ajna nodo
en la mezo de la list-- kiu

132
00:06:07,960 --> 00:06:11,550
havas legitiman montrilon antaŭen
kaj legitima montrilo dorsdirekte

133
00:06:11,550 --> 00:06:14,460
legitima antaŭa kaj sekva puntero.

134
00:06:14,460 --> 00:06:16,530
Denove, se vi laboras
kun la randoj, vi

135
00:06:16,530 --> 00:06:18,500
bezonas manipuli tiujn
iomete malsame,

136
00:06:18,500 --> 00:06:19,570
kaj ni ne tuj
paroli pri tio nun.

137
00:06:19,570 --> 00:06:21,319
Sed vi povas verŝajne
elkompreni bezonas

138
00:06:21,319 --> 00:06:24,610
farenda nur rigardas ĉi video.

139
00:06:24,610 --> 00:06:28,910
>> Do ni izolis X. X estas la nodo
ni volas forigi el la listo.

140
00:06:28,910 --> 00:06:30,140
Kion ni faru?

141
00:06:30,140 --> 00:06:32,800
Unue, ni devas reordigi
la ekstera punteros.

142
00:06:32,800 --> 00:06:35,815
Ni devas reordigi
9 La venonta salti super 13

143
00:06:35,815 --> 00:06:38,030
kaj punkto al 10-- kiu
Estas kion ni ĵus faris.

144
00:06:38,030 --> 00:06:41,180
Kaj ni ankaŭ bezonos
reordigi 10 La Antaŭa

145
00:06:41,180 --> 00:06:44,610
atentigi al 9 anstataŭ indikante 13.

146
00:06:44,610 --> 00:06:46,490
>> Do denove, ĉi tiu estis la
diagramo komence.

147
00:06:46,490 --> 00:06:47,730
Tiu estis nia ĉeno.

148
00:06:47,730 --> 00:06:51,027
Ni devas salti super 13,
sed ni bezonas ankaŭ konservi

149
00:06:51,027 --> 00:06:52,110
la integreco de la listo.

150
00:06:52,110 --> 00:06:54,680
Ni ne deziras perdi ajnan
informoj en ĉu direkto.

151
00:06:54,680 --> 00:06:59,620
Do ni devas reordigi
la punteros singarde

152
00:06:59,620 --> 00:07:02,240
do ni ne rompi la ĉenon ajn.

153
00:07:02,240 --> 00:07:05,710
>> Do ni povas diri 9 Next montrilon
notas al la sama loko

154
00:07:05,710 --> 00:07:08,040
ke dektri Next
montrilo indikas ĝuste nun.

155
00:07:08,040 --> 00:07:10,331
Ĉar ni estas eventuale
tuj volas salti super 13.

156
00:07:10,331 --> 00:07:13,750
Do kien 13 punktoj sekva, vin
volas naŭ atentigi tie anstataŭe.

157
00:07:13,750 --> 00:07:15,200
Do jen tio.

158
00:07:15,200 --> 00:07:20,370
Kaj tiam Wherever 13 poentoj reen
al, kio ajn venas antaŭ 13,

159
00:07:20,370 --> 00:07:24,800
ni volas 10 atentigi
por ke anstataux 13.

160
00:07:24,800 --> 00:07:29,290
Nun rimarkas, se vi sekvas
la sagoj, ni povas faligi 13

161
00:07:29,290 --> 00:07:32,380
sen fakte perdi iun informon.

162
00:07:32,380 --> 00:07:36,002
Ni konservis la integrecon de la listo,
movanta ambaŭ antaŭen kaj malantaŭen.

163
00:07:36,002 --> 00:07:38,210
Kaj tiam ni povas nur ia
de purigi ĝin iomete

164
00:07:38,210 --> 00:07:40,930
tirante la listo kune.

165
00:07:40,930 --> 00:07:43,270
Do ni rearanĝis la
punteros ambaŭflanke.

166
00:07:43,270 --> 00:07:46,231
Kaj tiam ni liberigis X
nodo kiu enhavis 13

167
00:07:46,231 --> 00:07:47,480
kaj ni ne rompis la ĉenon.

168
00:07:47,480 --> 00:07:50,980
Do ni bonfaris.

169
00:07:50,980 --> 00:07:53,000
>> Fino noto tie en ligitaj listoj.

170
00:07:53,000 --> 00:07:55,990
Do ambaŭ singly- kaj duoble-ligitaj
listoj, kiel ni vidis,

171
00:07:55,990 --> 00:07:58,959
subteno vere efika inserción
kaj forigo de elementoj.

172
00:07:58,959 --> 00:08:00,750
Vi povas sufiĉe tre faras
ĝin en konstanta tempo.

173
00:08:00,750 --> 00:08:03,333
Kion ni devas fari por forviŝi
ero nur dua antaŭe?

174
00:08:03,333 --> 00:08:04,440
Ni movita montrilo.

175
00:08:04,440 --> 00:08:05,920
Ni translokiĝis al alia puntero.

176
00:08:05,920 --> 00:08:07,915
Ni liberigita X-- prenis tri operacioj.

177
00:08:07,915 --> 00:08:14,500
Ĝi ĉiam prenas tri operacioj al
forviŝi ke node-- liberigi nodo.

178
00:08:14,500 --> 00:08:15,280
>> Kiel ni enmeti?

179
00:08:15,280 --> 00:08:17,280
Nu, ni estas nur ĉiam
tacking sur la komenco

180
00:08:17,280 --> 00:08:19,400
se ni enmeto kompetente.

181
00:08:19,400 --> 00:08:21,964
Do ni bezonas rearrange--
depende se ĝi estas

182
00:08:21,964 --> 00:08:24,380
a singly- aŭ duoble-ligitaj
listo, ni eble bezonas por fari tri

183
00:08:24,380 --> 00:08:26,824
aŭ kvar operacioj maks.

184
00:08:26,824 --> 00:08:28,365
Sed denove, estas ĉiam tri aŭ kvar.

185
00:08:28,365 --> 00:08:30,531
Ne gravas kiom da
elementoj estas en nia listo,

186
00:08:30,531 --> 00:08:33,549
ĝi estas ĉiam tri aŭ kvar operations--
samkiel forigo ĉiam

187
00:08:33,549 --> 00:08:35,320
tri aŭ kvar operacioj.

188
00:08:35,320 --> 00:08:36,919
Estas konstanta tempo.

189
00:08:36,919 --> 00:08:38,169
Do jen vere granda.

190
00:08:38,169 --> 00:08:40,620
>> Kun tabeloj, ni faris
io kiel inserción varon.

191
00:08:40,620 --> 00:08:44,739
Vi probable memoras ke inserción
varo estas ne konstanta tempa algoritmo.

192
00:08:44,739 --> 00:08:46,030
Estas efektive sufiĉe multekosta.

193
00:08:46,030 --> 00:08:48,840
Do tiu estas multe pli bone por enmeto.

194
00:08:48,840 --> 00:08:51,840
Sed, kiel mi menciis en la
unuope-ligillisto vídeo,

195
00:08:51,840 --> 00:08:54,030
ni hvas downside ĉi tie tro, ĉu ne?

196
00:08:54,030 --> 00:08:57,580
Ni perdis la kapablon
hazarde aliri elementojn.

197
00:08:57,580 --> 00:09:02,310
Ni ne povas diri, mi volas elemento numero kvar
aŭ elemento numero 10 de ligitaj listo

198
00:09:02,310 --> 00:09:04,990
la sama maniero kiun ni povas
fari tion kun tabelo

199
00:09:04,990 --> 00:09:08,630
aŭ ni povas nur rekte indekso
en nia tabelo la elemento.

200
00:09:08,630 --> 00:09:10,930
>> Kaj tiel provas trovi
elemento en ligitaj list--

201
00:09:10,930 --> 00:09:15,880
se traserĉado estas important--
Eble nun prenu lineara tempo.

202
00:09:15,880 --> 00:09:18,330
Kiel la listo ricevas longa, ĝi
povus preni unu plian paŝon

203
00:09:18,330 --> 00:09:22,644
por ĉiu unuopa elemento en la listo en
Por trovi kion ni serĉas.

204
00:09:22,644 --> 00:09:23,560
Do ekzistas komerco offs.

205
00:09:23,560 --> 00:09:25,780
Ekzistas iom de avantaĝo
kaj con elemento tie.

206
00:09:25,780 --> 00:09:29,110
>> Kaj duoble-ligitaj listoj ne estas la
lasta speco de datumstrukturo kombinaĵo

207
00:09:29,110 --> 00:09:32,840
ke ni parolos pri,
prenante ĉiujn bazajn konstruaĵo

208
00:09:32,840 --> 00:09:34,865
blokoj de C de kunmetado.

209
00:09:34,865 --> 00:09:37,900
Ĉar fakte, ni povas
eĉ pli bone ol tio

210
00:09:37,900 --> 00:09:41,970
krei datumstrukturo ke
vi eble povos traserĉi

211
00:09:41,970 --> 00:09:43,360
en konstanta tempo tro.

212
00:09:43,360 --> 00:09:46,080
Sed pli en kiuj en alia video.

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

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

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