1
00:00:00,000 --> 00:00:02,832
>> [REPRODUCCIÓ DE MÚSICA]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, així que al
aquest punt en el curs,

4
00:00:08,560 --> 00:00:15,300
hem cobert molts dels conceptes bàsics de la C.
Sabem molt sobre variables, matrius,

5
00:00:15,300 --> 00:00:17,610
punters, totes aquestes coses bones.

6
00:00:17,610 --> 00:00:21,610
Aquests són tot tipus de construït
per veure com els fonaments,

7
00:00:21,610 --> 00:00:23,880
però podem fer més, no?

8
00:00:23,880 --> 00:00:27,930
Podem combinar coses
junts en formes interessants.

9
00:00:27,930 --> 00:00:31,010
>> I així anem a fer això, anem a començar
diversificar del que C ens dóna,

10
00:00:31,010 --> 00:00:35,270
i començar a crear les nostres pròpies dades
estructures que utilitzen aquests edificis

11
00:00:35,270 --> 00:00:40,590
blocs junts per fer alguna cosa
realment valuós, útil.

12
00:00:40,590 --> 00:00:43,420
Una manera de fer-ho és
per parlar sobre les col·leccions.

13
00:00:43,420 --> 00:00:48,360
Així que fins ara hem tingut un tipus de dades
estructura per representar col·leccions

14
00:00:48,360 --> 00:00:51,030
de rebre els valors, valors similars.

15
00:00:51,030 --> 00:00:52,350
Això seria una matriu.

16
00:00:52,350 --> 00:00:57,020
Disposem de col·leccions de nombres sencers, o
col·leccions de personatges i així successivament.

17
00:00:57,020 --> 00:01:00,890
>> Estructures també una mena de dades
estructura per a la recopilació d'informació,

18
00:01:00,890 --> 00:01:03,220
però no ho és per recollir com a valors.

19
00:01:03,220 --> 00:01:08,090
En general, es barreja diferents tipus de dades
junts dins d'una sola caixa.

20
00:01:08,090 --> 00:01:10,750
Però no és en si
utilitzat per encadenar

21
00:01:10,750 --> 00:01:16,920
o connecti juntes similars
articles, com una matriu.

22
00:01:16,920 --> 00:01:20,960
Les matrius són grans per
element de mirar cap amunt, però el record

23
00:01:20,960 --> 00:01:24,262
que és molt difícil
per inserir en una matriu,

24
00:01:24,262 --> 00:01:26,470
llevat que estem inserint en
al final d'aquesta matriu.

25
00:01:26,470 --> 00:01:29,730
>> I el millor exemple que té
per això és l'ordenació per inserció.

26
00:01:29,730 --> 00:01:31,650
Si vostè recorda el nostre vídeo
d'ordenació per inserció,

27
00:01:31,650 --> 00:01:34,110
hi havia una gran quantitat de
despeses involucrats en tenir

28
00:01:34,110 --> 00:01:37,970
per recollir elements, i desplaçar-los
fora del camí per adaptar-se a alguna cosa

29
00:01:37,970 --> 00:01:41,290
al centre de la seva matriu.

30
00:01:41,290 --> 00:01:44,690
Les matrius també pateixen d'una altra
problema, que és la inflexibilitat.

31
00:01:44,690 --> 00:01:47,150
Quan declarem una matriu,
tenim una oportunitat en ell.

32
00:01:47,150 --> 00:01:49,790
Hem de dir, vull
aquesta quantitat d'elements.

33
00:01:49,790 --> 00:01:51,940
Podria ser 100, podria
ser 1000, podria

34
00:01:51,940 --> 00:01:55,930
ser x, on x és un nombre que l'usuari
ens va donar en el símbol o en la comanda

35
00:01:55,930 --> 00:01:56,630
la línia.

36
00:01:56,630 --> 00:01:59,905
>> Però només tenim una oportunitat per ella,
no arribo a dir a continuació, oh, en realitat jo

37
00:01:59,905 --> 00:02:04,360
necessitava 101, o que necessitava x més 20.

38
00:02:04,360 --> 00:02:07,910
Massa tard, ja hem declarat la
matriu, i si volem obtenir 101 o x

39
00:02:07,910 --> 00:02:12,050
més 20, hem de declarar
un conjunt completament diferent,

40
00:02:12,050 --> 00:02:15,540
copiar tots els elements de la matriu
acabat, i llavors tenim prou.

41
00:02:15,540 --> 00:02:19,880
¿I si ens equivoquem de nou, el que
si en realitat necessitem 102, o x més de 40 anys,

42
00:02:19,880 --> 00:02:21,970
hem de fer això de nou.

43
00:02:21,970 --> 00:02:26,250
Així que són molt inflexibles
per canviar la mida de les nostres dades,

44
00:02:26,250 --> 00:02:29,360
però si combinem a alguns
dels conceptes bàsics que ja hem

45
00:02:29,360 --> 00:02:33,230
après sobre els punters i estructures,
en particular, l'ús de memòria dinàmica

46
00:02:33,230 --> 00:02:36,180
assignació amb malloc, que
pot posar aquestes peces juntes

47
00:02:36,180 --> 00:02:40,960
per crear un una nova dada structure--
llista podríem dir-- enllaçada

48
00:02:40,960 --> 00:02:45,400
que ens permet créixer i
reduir una col·lecció de valors

49
00:02:45,400 --> 00:02:48,800
i no tindrem cap espai perdut.

50
00:02:48,800 --> 00:02:53,320
>> Així que de nou, cridem a aquesta idea,
aquesta noció, una llista enllaçada.

51
00:02:53,320 --> 00:02:56,320
En particular, en aquest vídeo estem
parlant de llista enllaçada,

52
00:02:56,320 --> 00:02:59,185
i després un altre vídeo parlarem
llistes sobre doblement enllaçades, que

53
00:02:59,185 --> 00:03:01,560
és només una variació sobre un tema aquí.

54
00:03:01,560 --> 00:03:05,200
No obstant això, una llista enllaçada
es compon de nodes,

55
00:03:05,200 --> 00:03:08,559
nodes només ser un term-- abstracta
és només una cosa que estic trucant

56
00:03:08,559 --> 00:03:10,350
això és una mena de
estructura, bàsicament, estic?

57
00:03:10,350 --> 00:03:16,190
Només va a trucar a un node-- i això
node té dos membres, o dos camps.

58
00:03:16,190 --> 00:03:20,300
Té dades, en general una
nombre enter, un flotador caràcter,

59
00:03:20,300 --> 00:03:23,790
o podria ser algun altre tipus de dades
que ha definit amb un tipus def.

60
00:03:23,790 --> 00:03:29,290
I conté un punter a
un altre node del mateix tipus.

61
00:03:29,290 --> 00:03:34,710
>> Així que tenim dues coses a l'interior de
aquest node, les dades i un punter

62
00:03:34,710 --> 00:03:36,380
a un altre node.

63
00:03:36,380 --> 00:03:39,370
I si vostè comença a visualitzar
això, es pot pensar-hi

64
00:03:39,370 --> 00:03:42,280
com una cadena de nodes que
estan connectats entre si.

65
00:03:42,280 --> 00:03:45,070
Tenim el primer node,
conté dades, i un punter

66
00:03:45,070 --> 00:03:49,110
al segon node, que conté
de dades, i un punter a la tercera node.

67
00:03:49,110 --> 00:03:52,940
I per això en diem un
llista enllaçada, estan units entre si.

68
00:03:52,940 --> 00:03:56,070
>> Què fa aquest especial
estructura de nodes sembla?

69
00:03:56,070 --> 00:04:01,120
Bé, si vostè recorda del nostre vídeo en
la definició de tipus personalitzats, amb el tipus de definició,

70
00:04:01,120 --> 00:04:05,400
podem definir un structure-- i
escrigui definir una estructura com aquesta.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, i llavors estic
utilitzant el valor de la paraula aquí arbitràriament

72
00:04:11,240 --> 00:04:13,891
per indicar qualsevol tipus de dades realment.

73
00:04:13,891 --> 00:04:16,890
Vostè podria passar un sencer o flotant,
vostè podria tenir el que vulguis.

74
00:04:16,890 --> 00:04:19,389
No està restringit només
sencers, ni res d'això.

75
00:04:19,389 --> 00:04:22,790
Així que el valor és només una arbitrària
tipus de dades, i després un punter

76
00:04:22,790 --> 00:04:26,310
a un altre node del mateix tipus.

77
00:04:26,310 --> 00:04:29,690
>> Ara, hi ha una mica de captures
aquí amb la definició d'una estructura de

78
00:04:29,690 --> 00:04:33,030
quan és una estructura auto referencial.

79
00:04:33,030 --> 00:04:35,340
He de tenir un temporal
nomenar per la meva estructura.

80
00:04:35,340 --> 00:04:37,640
Al final del dia I
clarament volen dir-

81
00:04:37,640 --> 00:04:43,030
node sll, que és en última instància, el nou
nomenar part de la meva tipus de definició,

82
00:04:43,030 --> 00:04:47,450
però no puc utilitzar el node sll
en el medi d'això.

83
00:04:47,450 --> 00:04:51,430
La raó és que no ho he fet
creat un node SLL tipus anomenat

84
00:04:51,430 --> 00:04:55,200
fins que vaig arribar a aquest punt final aquí.

85
00:04:55,200 --> 00:04:59,720
Fins a aquest moment, he de tenir
una altra manera de referir-se a aquest tipus de dades.

86
00:04:59,720 --> 00:05:02,440
>> I aquest és un acte
tipus de dades referencial.

87
00:05:02,440 --> 00:05:06,314
És, és un tipus de dades d'un
estructura que conté una dada,

88
00:05:06,314 --> 00:05:08,480
i un punter a un altre
estructura del mateix tipus.

89
00:05:08,480 --> 00:05:11,750
Així que he de ser capaç de referir-se a
aquest tipus de dades almenys temporalment,

90
00:05:11,750 --> 00:05:14,910
per la qual cosa li dóna un temporal
nom del struct sllist

91
00:05:14,910 --> 00:05:18,540
em permet llavors dic que vull un
punter a una altra estructura sllist,

92
00:05:18,540 --> 00:05:24,690
un estel struct sllist, i després
després d'haver completat la definició,

93
00:05:24,690 --> 00:05:27,220
Ara puc cridar a aquest tipus d'un node sll.

94
00:05:27,220 --> 00:05:30,520
>> Així que per això es veu que hi ha
un nom temporal aquí,

95
00:05:30,520 --> 00:05:31,879
sinó un nom permanent aquí.

96
00:05:31,879 --> 00:05:33,920
A vegades és possible que vegi
les definicions de l'estructura,

97
00:05:33,920 --> 00:05:36,570
per exemple, que no són
acte referencial, que

98
00:05:36,570 --> 00:05:39,390
no tenen un nom especificador aquí.

99
00:05:39,390 --> 00:05:43,040
Simplement diria typedef struct,
obrir claudàtor i després definir-lo.

100
00:05:43,040 --> 00:05:45,620
Però si vostè és struct és acte
referencial, com aquesta és,

101
00:05:45,620 --> 00:05:49,010
cal especificar un
nom de tipus temporal.

102
00:05:49,010 --> 00:05:51,310
Però en última instància, ara
que hem fet això,

103
00:05:51,310 --> 00:05:53,620
acabem de fer referència a
aquests nodes, aquestes unitats,

104
00:05:53,620 --> 00:05:57,900
com a nodes SLL propòsits
de la resta d'aquest vídeo.

105
00:05:57,900 --> 00:06:00,900
>> Molt bé, així que sabem com
crear un node de llista enllaçada.

106
00:06:00,900 --> 00:06:03,240
Sabem com definir
un node de llista enllaçada.

107
00:06:03,240 --> 00:06:06,670
Ara, si anem a començar
usar-les per recopilar informació,

108
00:06:06,670 --> 00:06:10,360
hi ha un parell d'operacions que
necessitat d'entendre i treballar amb ells.

109
00:06:10,360 --> 00:06:12,860
Hem de saber com crear
una llista enllaçada del no-res.

110
00:06:12,860 --> 00:06:14,901
Si no hi ha cap llista ja,
volem començar un.

111
00:06:14,901 --> 00:06:16,960
Així que hem de ser capaços de
per crear una llista enllaçada,

112
00:06:16,960 --> 00:06:19,130
hem de probablement buscar
a través de la llista d'enllaços

113
00:06:19,130 --> 00:06:21,830
per trobar un element que estem buscant.

114
00:06:21,830 --> 00:06:24,430
Hem de ser capaços d'inserir
noves coses a la llista,

115
00:06:24,430 --> 00:06:25,930
volem que la nostra llista per poder créixer.

116
00:06:25,930 --> 00:06:28,638
I de la mateixa manera, volem ser capaços
eliminar coses de la nostra llista,

117
00:06:28,638 --> 00:06:30,250
volem que la nostra llista per ser capaç de reduir la mida.

118
00:06:30,250 --> 00:06:32,160
I al final de la nostra
programes, especialment

119
00:06:32,160 --> 00:06:34,550
si vostè recorda que som
assignació dinàmica de memòria

120
00:06:34,550 --> 00:06:38,337
per construir aquestes llistes normalment,
volem alliberar tota la que la memòria

121
00:06:38,337 --> 00:06:39,670
quan hàgim acabat de treballar amb ell.

122
00:06:39,670 --> 00:06:44,627
I així hem de ser capaços d'esborrar 01:00
tota llista enllaçada en un error de la batuda.

123
00:06:44,627 --> 00:06:46,460
Així que anem a anar a través
algunes d'aquestes operacions

124
00:06:46,460 --> 00:06:51,192
i com podem visualitzar-los,
parlant en codi pseudocodi específicament.

125
00:06:51,192 --> 00:06:53,150
Així que volem crear un
llista enllaçada, així que potser

126
00:06:53,150 --> 00:06:56,480
voleu definir una funció
amb aquest prototip.

127
00:06:56,480 --> 00:07:01,690
sll estrelles node, creu, i jo estic passant
en un argument, algunes dades arbitraris

128
00:07:01,690 --> 00:07:05,530
escrigui de nou, d'algun tipus de dades arbitrari.

129
00:07:05,530 --> 00:07:10,482
Però estic returning-- aquesta funció hauria
tornarà a mi un punter, a un solitari

130
00:07:10,482 --> 00:07:11,190
node de llista enllaçada.

131
00:07:11,190 --> 00:07:14,050
Un cop més, estem tractant de crear
una llista enllaçada del no-res,

132
00:07:14,050 --> 00:07:17,900
així que necessito un punter a
aquesta llista quan he acabat.

133
00:07:17,900 --> 00:07:19,420
>> Quins són els passos a seguir aquí?

134
00:07:19,420 --> 00:07:20,960
Bé, primer que estic
farem és dinàmicament

135
00:07:20,960 --> 00:07:22,550
assignar espai per a un nou node.

136
00:07:22,550 --> 00:07:26,689
Un cop més, estem creant fora de fina
aire, de manera que necessitem l'espai malloc per a això.

137
00:07:26,689 --> 00:07:28,480
I, per descomptat, immediatament
després que malloc,

138
00:07:28,480 --> 00:07:31,692
sempre comprovar per assegurar-se que la nostra
pointer-- no aconseguim tornar nul.

139
00:07:31,692 --> 00:07:33,650
Perquè si tractem de
deferència un punter nul,

140
00:07:33,650 --> 00:07:36,190
anem a patir un
violació de segment i no volem això.

141
00:07:36,190 --> 00:07:39,510
>> Llavors volem omplir el camp,
volem inicialitzar el camp de valor

142
00:07:39,510 --> 00:07:41,690
i inicialitzar el següent camp.

143
00:07:41,690 --> 00:07:45,450
I després volem A-- finalment com el
prototip de funció indicates-- volem

144
00:07:45,450 --> 00:07:49,940
per tornar un punter a un node sll.

145
00:07:49,940 --> 00:07:51,710
Llavors, què fa aquest parer visualment?

146
00:07:51,710 --> 00:07:55,230
Bé, primer anem a dinàmicament
assignar espai per a un nou node SLL,

147
00:07:55,230 --> 00:07:58,320
així que això és malloc--
una representació visual

148
00:07:58,320 --> 00:08:00,020
del node que acabem de crear.

149
00:08:00,020 --> 00:08:02,757
I vam comprovar que assegurar
no és null-- en aquest cas,

150
00:08:02,757 --> 00:08:04,840
la imatge no tindria
aparegut si era nul,

151
00:08:04,840 --> 00:08:07,298
ens hauríem quedat sense memòria,
així que estem bé per anar-hi.

152
00:08:07,298 --> 00:08:10,200
Així que ara estem en el pas C,
inicialitzar el camp de valor nodes.

153
00:08:10,200 --> 00:08:12,280
Doncs bé, en base a aquesta funció
dic estic fent servir aquí,

154
00:08:12,280 --> 00:08:16,700
sembla que vull passar a 6,
Així que vaig a 6 al camp de valor.

155
00:08:16,700 --> 00:08:18,865
Ara, inicialitzar el següent camp.

156
00:08:18,865 --> 00:08:21,640
Bé, què faré allà,
no hi ha res al costat, a la dreta,

157
00:08:21,640 --> 00:08:23,600
aquesta és l'única cosa a la llista.

158
00:08:23,600 --> 00:08:27,206
Llavors, ¿què és el proper a la llista?

159
00:08:27,206 --> 00:08:29,660
>> No ha d'apuntar a res, és clar.

160
00:08:29,660 --> 00:08:33,600
No hi ha res més allà, així que el que és
el concepte que coneixem que és nothing--

161
00:08:33,600 --> 00:08:35,638
punters a res?

162
00:08:35,638 --> 00:08:37,929
Ha de ser tal que volem
posar un punter nul allà,

163
00:08:37,929 --> 00:08:40,178
i vaig a representar la nul·la
punter només com una caixa vermella,

164
00:08:40,178 --> 00:08:41,559
no podem anar més enllà.

165
00:08:41,559 --> 00:08:44,430
Com veurem una mica més endavant,
tindrem eventualment cadenes

166
00:08:44,430 --> 00:08:46,330
de fletxes que connecten
aquests nodes junts,

167
00:08:46,330 --> 00:08:48,480
però quan es prem el
caixa vermella, que és nul·la,

168
00:08:48,480 --> 00:08:51,150
no podem anar més lluny,
aquest és el final de la llista.

169
00:08:51,150 --> 00:08:53,960
>> I finalment, només volem
retornar un punter a aquest node.

170
00:08:53,960 --> 00:08:56,160
Així que ho anem a cridar nova,
i tornarà nova

171
00:08:56,160 --> 00:08:59,370
per la qual cosa es pot utilitzar en
qualsevol funció va crear.

172
00:08:59,370 --> 00:09:03,100
Així que aquí anem, Hem creat una individualment
node de llista enllaçada del no-res,

173
00:09:03,100 --> 00:09:05,920
i ara tenim una llista que podem treballar.

174
00:09:05,920 --> 00:09:08,260
>> Ara, anem a dir que ja
tenen una gran cadena,

175
00:09:08,260 --> 00:09:09,800
i volem trobar alguna cosa en ella.

176
00:09:09,800 --> 00:09:12,716
I volem una funció que està passant
per tornar veritable o fals, depenent

177
00:09:12,716 --> 00:09:15,840
sobre si hi ha un valor en aquesta llista.

178
00:09:15,840 --> 00:09:18,160
Un prototip de funció, o
declaració per a aquesta funció,

179
00:09:18,160 --> 00:09:23,320
podria semblar esto-- Bool trobar, i
llavors volem passar en dos arguments.

180
00:09:23,320 --> 00:09:26,996
>> El primer, és un punter a la
primer element de la llista enllaçada.

181
00:09:26,996 --> 00:09:29,620
Això és realment una cosa que vostè
sempre volen perdre de vista,

182
00:09:29,620 --> 00:09:33,110
i en realitat podria ser una cosa que
fins i tot es posa en una variable global.

183
00:09:33,110 --> 00:09:35,360
Un cop creada una llista,
sempre, sempre

184
00:09:35,360 --> 00:09:38,990
vull fer un seguiment de la mateixa
primer element de la llista.

185
00:09:38,990 --> 00:09:43,690
D'aquesta manera vostè pot fer referència a tots els altres
elements per només seguint la cadena,

186
00:09:43,690 --> 00:09:47,300
sense haver de mantenir punters
intacte per a cada element.

187
00:09:47,300 --> 00:09:50,920
Només cal fer un seguiment de la primera
un si tots estan encadenats junts.

188
00:09:50,920 --> 00:09:52,460
>> I després la segona cosa
estem passant de nou

189
00:09:52,460 --> 00:09:54,376
és some-- arbitràriament
qualsevol que sigui el tipus de dades que estem

190
00:09:54,376 --> 00:09:59,640
buscant que hi ha dins de
amb sort un dels nodes de la llista.

191
00:09:59,640 --> 00:10:00,980
Quins són els passos?

192
00:10:00,980 --> 00:10:04,250
Bé, el primer que fem és
vam crear un punter transversal

193
00:10:04,250 --> 00:10:06,015
apuntant al capdavant de les llistes.

194
00:10:06,015 --> 00:10:08,890
Bé, per què ho fem, ja
tenir un punter al capdavant llistes,

195
00:10:08,890 --> 00:10:10,974
¿Per què no simplement movem que ningú al voltant?

196
00:10:10,974 --> 00:10:13,140
Bé, com acabo de dir,
que és molt important per a nosaltres

197
00:10:13,140 --> 00:10:17,580
sempre mantenir un seguiment de la
molt primer element a la llista.

198
00:10:17,580 --> 00:10:21,270
I el que és en realitat millor
per crear un duplicat que,

199
00:10:21,270 --> 00:10:25,350
i l'ús que per moure de manera que mai
moure accidentalment de distància, o sempre

200
00:10:25,350 --> 00:10:30,430
tenir un punter en algun moment que és
a la dreta en el primer element de la llista.

201
00:10:30,430 --> 00:10:33,290
Així que és millor crear un
segon que fem servir per moure.

202
00:10:33,290 --> 00:10:35,877
>> Llavors només si comparem
el camp de valor en aquest node

203
00:10:35,877 --> 00:10:38,960
és el que estem buscant, i si és
No, simplement movem al següent node.

204
00:10:38,960 --> 00:10:41,040
I seguim fent això
una altra vegada, i una altra, i una altra,

205
00:10:41,040 --> 00:10:44,811
fins que ens trobem, ja sigui
l'element, o colpegem

206
00:10:44,811 --> 00:10:47,310
null-- que hem arribat al final
de la llista i no hi és.

207
00:10:47,310 --> 00:10:50,540
Això hauria de sonar una campana
a vostè com acaba de recerca lineal,

208
00:10:50,540 --> 00:10:54,430
només estem replicant en
una estructura de llista enllaçada

209
00:10:54,430 --> 00:10:56,280
en lloc d'utilitzar una matriu per fer-ho.

210
00:10:56,280 --> 00:10:58,210
>> Així que aquí està un exemple de
una llista simplement enllaçada.

211
00:10:58,210 --> 00:11:00,043
Aquest consisteix en
5 nodes, i tenim

212
00:11:00,043 --> 00:11:04,330
un punter al capdavant de la
llista, que es diu llista.

213
00:11:04,330 --> 00:11:07,385
El primer que volem fer és
de nou, crear aquest punter recorregut.

214
00:11:07,385 --> 00:11:09,760
Així que tenim ara dos punters
que apunten al mateix.

215
00:11:09,760 --> 00:11:15,025
>> Ara, noti aquí també, no ho vaig fer
que malloc qualsevol espai per trav.

216
00:11:15,025 --> 00:11:18,970
Jo no he dit trav és igual a malloc
alguna cosa, aquest node ja existeix,

217
00:11:18,970 --> 00:11:21,160
que l'espai en la memòria ja existeix.

218
00:11:21,160 --> 00:11:24,290
Així que tot el que en realitat estic fent és
creant un altre punter a ell.

219
00:11:24,290 --> 00:11:28,210
No estic mallocing addicionals
espai, només hi ha ara dos punters

220
00:11:28,210 --> 00:11:31,370
apuntant a la mateixa cosa.

221
00:11:31,370 --> 00:11:33,710
>> Així és 2 el que estic buscant?

222
00:11:33,710 --> 00:11:37,220
Bé, no, així que en comptes estic
passarà a la següent.

223
00:11:37,220 --> 00:11:41,740
Així que, bàsicament, jo diria,
trav és igual a trav següent.

224
00:11:41,740 --> 00:11:43,630
És de 3 el que estic buscant, no.

225
00:11:43,630 --> 00:11:45,780
Així que segueixo anar
a través, fins que al final

226
00:11:45,780 --> 00:11:48,690
arribo a 6 que és el que estic buscant
per a la base de la crida a la funció

227
00:11:48,690 --> 00:11:51,600
Tinc a la part superior
allà, i l'he acabat.

228
00:11:51,600 --> 00:11:54,150
>> Ara, què passa si l'element que sóc
buscant no està a la llista,

229
00:11:54,150 --> 00:11:55,510
està encara funcionarà?

230
00:11:55,510 --> 00:11:57,120
Bé, notarà que la llista
aquí és subtilment diferent,

231
00:11:57,120 --> 00:11:59,410
i això és una altra cosa que és
important amb llistes enllaçades,

232
00:11:59,410 --> 00:12:01,780
vostè no ha de preservar
en qualsevol ordre particular.

233
00:12:01,780 --> 00:12:05,390
Vostè pot si ho desitja, però
és possible que ja hagi notat

234
00:12:05,390 --> 00:12:09,310
que no estem fer el seguiment de
el que l'element nombre estem.

235
00:12:09,310 --> 00:12:13,150
>> I això és una espècie d'un comerç que
tenir amb llista enllaçada versos matrius,

236
00:12:13,150 --> 00:12:15,300
és que no tenim
accés aleatori més.

237
00:12:15,300 --> 00:12:18,150
No podem dir, que vull
per anar a l'element 0 ª,

238
00:12:18,150 --> 00:12:21,410
o el sisè element de la meva matriu,
que puc fer en una matriu.

239
00:12:21,410 --> 00:12:25,080
No puc dir que em vull anar a la
Element 0 ª, o el sisè element,

240
00:12:25,080 --> 00:12:30,360
o l'element 25a de la cistella enllaçada,
no hi ha índex associat amb ells.

241
00:12:30,360 --> 00:12:33,660
I pel que en realitat no importa
si preservem la nostra llista en ordre.

242
00:12:33,660 --> 00:12:36,080
Si desitja vostè
certament pot, però hi ha

243
00:12:36,080 --> 00:12:38,567
cap raó per la qual necessiten per
preservar en qualsevol ordre.

244
00:12:38,567 --> 00:12:40,400
Així que de nou, tractarem de
trobar 6 en aquesta llista.

245
00:12:40,400 --> 00:12:43,200
Bé, comencem pel
començant, no trobem 6,

246
00:12:43,200 --> 00:12:47,690
i llavors no seguim trobant
6, fins que finalment vam arribar a aquí.

247
00:12:47,690 --> 00:12:52,790
Així correctes punts ara trav al node
conté 8, i sis no hi és.

248
00:12:52,790 --> 00:12:55,250
>> Així que el següent pas seria
per anar al següent punter,

249
00:12:55,250 --> 00:12:57,440
ho diuen trav és igual a trav següent.

250
00:12:57,440 --> 00:13:00,750
Bé, trav següent, indicat per
la caixa vermella allà, és nul.

251
00:13:00,750 --> 00:13:03,020
Així que no hi ha cap altre lloc a
anar, i el que en aquest punt

252
00:13:03,020 --> 00:13:06,120
podem concloure que hem arribat
al final de la llista enllaçada,

253
00:13:06,120 --> 00:13:07,190
i 6 no hi és.

254
00:13:07,190 --> 00:13:10,980
I seria retornat
falsa en aquest cas.

255
00:13:10,980 --> 00:13:14,540
>> OK, com ens inserim una nova
node en la llista enllaçada?

256
00:13:14,540 --> 00:13:17,310
Així que hem estat capaços de crear
una llista enllaçada del no-res,

257
00:13:17,310 --> 00:13:19,370
però probablement volem
construir una cadena i no

258
00:13:19,370 --> 00:13:22,620
crear un munt de llistes diferents.

259
00:13:22,620 --> 00:13:25,700
Volem tenir una sola llista que
té un grup de nodes al mateix,

260
00:13:25,700 --> 00:13:28,040
no un munt de llistes amb un únic node.

261
00:13:28,040 --> 00:13:31,260
Així no podem seguir utilitzant el Crear
funció que definim abans, ara ens

262
00:13:31,260 --> 00:13:33,860
vol inserir en un
llista que ja existeix.

263
00:13:33,860 --> 00:13:36,499
>> Així que aquest cas, anem
Va esdevenir en dos arguments,

264
00:13:36,499 --> 00:13:39,290
el punter al capdavant d'aquest
llista que volem afegir a la vinculada.

265
00:13:39,290 --> 00:13:40,910
Un cop més, és per això que és tan
important que sempre

266
00:13:40,910 --> 00:13:43,400
no perdre de vista, perquè
és l'única manera en què realment

267
00:13:43,400 --> 00:13:46,690
que es refereixen a tota la llista és
amb només un punter al primer element.

268
00:13:46,690 --> 00:13:49,360
Així que volem transmetre en un
punter a aquest primer element,

269
00:13:49,360 --> 00:13:52,226
i qualsevol que sigui el valor que
que voleu afegir a la llista.

270
00:13:52,226 --> 00:13:54,600
I, finalment, aquesta funció
va retornar un punter

271
00:13:54,600 --> 00:13:57,980
a la nova cap d'una llista enllaçada.

272
00:13:57,980 --> 00:13:59,700
>> Quins són els passos a seguir aquí?

273
00:13:59,700 --> 00:14:02,249
Bé, igual que amb crear,
hem d'assignar dinàmicament

274
00:14:02,249 --> 00:14:05,540
espai per a un nou node, i comprovar per
assegurar-se que no es quedi sense memòria, de nou,

275
00:14:05,540 --> 00:14:07,150
perquè estem usant malloc.

276
00:14:07,150 --> 00:14:09,080
Llavors volem poblar
i inserir el node,

277
00:14:09,080 --> 00:14:12,730
a fi de posar el nombre, el que sigui
val és, en el node.

278
00:14:12,730 --> 00:14:17,310
Volem inserir el node en
l'inici de la llista enllaçada.

279
00:14:17,310 --> 00:14:19,619
>> Hi ha una raó per la qual
voler fer això, i

280
00:14:19,619 --> 00:14:21,910
valdria la pena prendre un segon
per aturar el vídeo aquí,

281
00:14:21,910 --> 00:14:25,860
i pensar sobre per què voldria
inserir al començament d'una lligat

282
00:14:25,860 --> 00:14:26,589
llista.

283
00:14:26,589 --> 00:14:28,630
Un cop més, he esmentat abans
que en realitat no

284
00:14:28,630 --> 00:14:33,020
importa si preservem en qualsevol
ordre, així que potser això és una pista.

285
00:14:33,020 --> 00:14:36,040
I vas veure el que passaria si ens
volgut A-- o des d'un segon

286
00:14:36,040 --> 00:14:37,360
fa quan ens anàvem
a través de cerca

287
00:14:37,360 --> 00:14:39,235
podria veure el que podria
passaria si tractàvem

288
00:14:39,235 --> 00:14:41,330
per inserir al final de la llista.

289
00:14:41,330 --> 00:14:44,750
Perquè no tenim un
punter al final de la llista.

290
00:14:44,750 --> 00:14:47,490
>> Així que la raó per la qual jo voldria
per inserir al principi,

291
00:14:47,490 --> 00:14:49,380
és perquè puc fer-ho immediatament.

292
00:14:49,380 --> 00:14:52,730
Tinc un punter al començament, i
anem a veure això en un visual en un segon.

293
00:14:52,730 --> 00:14:55,605
Però si vull inserir al final,
He de començar pel principi,

294
00:14:55,605 --> 00:14:58,760
recórrer tot el camí fins a la
final, i després virar a engegar.

295
00:14:58,760 --> 00:15:01,420
Així que això significaria que
inserir al final de la llista

296
00:15:01,420 --> 00:15:04,140
es convertiria en un o de n
operació, que es remunta

297
00:15:04,140 --> 00:15:06,720
a la nostra discussió de
complexitat computacional.

298
00:15:06,720 --> 00:15:10,140
S'havia convertit en un o de l'operació n, on
com la llista es va fer més gran i més gran,

299
00:15:10,140 --> 00:15:13,310
i més gran, que serà més i
més difícil de virar una mica

300
00:15:13,310 --> 00:15:14,661
en al final.

301
00:15:14,661 --> 00:15:17,410
Però sempre és molt fàcil
virar alguna cosa en al principi,

302
00:15:17,410 --> 00:15:19,060
sempre estàs al principi.

303
00:15:19,060 --> 00:15:21,620
>> I anem a veure una representació visual d'aquest nou.

304
00:15:21,620 --> 00:15:24,100
I després, un cop que haguem acabat, un cop
hem inserit el nou node,

305
00:15:24,100 --> 00:15:26,880
volem tornar la nostra punter a
el nou cap d'una llista enllaçada, que

306
00:15:26,880 --> 00:15:29,213
ja que estem inserint en el
començant, serà realment

307
00:15:29,213 --> 00:15:31,060
un punter al node que acabem de crear.

308
00:15:31,060 --> 00:15:33,280
Anem a visualitzar això,
perquè crec que va a ajudar.

309
00:15:33,280 --> 00:15:36,661
>> Així que aquí està la nostra llista, que consisteix en
quatre elements, un node que conté 15,

310
00:15:36,661 --> 00:15:38,410
el que apunta a un node
que conté 9, que

311
00:15:38,410 --> 00:15:41,370
apunta a un node que conté 13,
que apunta a un node que conté

312
00:15:41,370 --> 00:15:44,840
10, que té la hipòtesi nul·la
punter com a pròxim punter

313
00:15:44,840 --> 00:15:47,010
de manera que és el final de la llista.

314
00:15:47,010 --> 00:15:50,200
Així que volem inserir un
nou node amb el valor 12

315
00:15:50,200 --> 00:15:52,720
a l'inici d'aquesta
llista, què fem?

316
00:15:52,720 --> 00:15:58,770
Bé, primer que malloc espai per al
node, i després posem 12 en aquest país.

317
00:15:58,770 --> 00:16:02,211
>> Així que ara hem arribat a un
punt de decisió, no?

318
00:16:02,211 --> 00:16:03,960
Tenim un parell de
punters que vam poder

319
00:16:03,960 --> 00:16:06,770
movem, quina hem de passar primer?

320
00:16:06,770 --> 00:16:09,250
Cal fer 12 punts per
el nou cap de la pel·lícules--

321
00:16:09,250 --> 00:16:13,020
o perdó, hem de fer 12
apuntar a la vella cap de la llista?

322
00:16:13,020 --> 00:16:15,319
O hauríem de dir que la
llista ara comença a les 12.

323
00:16:15,319 --> 00:16:17,110
Hi ha una distinció
allà, i anem a veure

324
00:16:17,110 --> 00:16:19,870
al que succeeix amb els dos en un segon.

325
00:16:19,870 --> 00:16:23,350
>> Però això condueix a una
gran tema de la barra lateral,

326
00:16:23,350 --> 00:16:26,280
que és que una de les
les coses més difícils amb llistes enllaçades

327
00:16:26,280 --> 00:16:30,980
és el d'organitzar els punters
en l'ordre correcte.

328
00:16:30,980 --> 00:16:34,520
Si mou les coses fora d'ordre,
vostè pot acabar accidentalment

329
00:16:34,520 --> 00:16:36,050
orfandat la resta de la llista.

330
00:16:36,050 --> 00:16:37,300
I aquí és un exemple d'això.

331
00:16:37,300 --> 00:16:40,540
Així que anirem amb la idea de--
així, hem acabem de crear 12.

332
00:16:40,540 --> 00:16:43,180
Sabem 12 serà
el nou cap de la llista,

333
00:16:43,180 --> 00:16:47,660
i així que per què no ens movem
el punter de la llista perquè apunti allà.

334
00:16:47,660 --> 00:16:49,070
>> OK, així que això és bo.

335
00:16:49,070 --> 00:16:51,560
Així que ara, on 12 següent punt?

336
00:16:51,560 --> 00:16:54,580
Vull dir, visualment podem veure
que apuntarà a 15,

337
00:16:54,580 --> 00:16:57,250
com a éssers humans és molt obvi per a nosaltres.

338
00:16:57,250 --> 00:17:00,300
Com sap l'equip?

339
00:17:00,300 --> 00:17:02,720
Nosaltres no tenim res
assenyalant a 15 més, no?

340
00:17:02,720 --> 00:17:05,869
>> Hem perdut tota capacitat per fer referència a 15.

341
00:17:05,869 --> 00:17:11,460
No podem dir nova fletxa propers iguals
alguna cosa, no hi ha res allà.

342
00:17:11,460 --> 00:17:13,510
De fet, hem orfes
la resta de la llista

343
00:17:13,510 --> 00:17:16,465
en fer-ho, tenim
trencat accidentalment la cadena.

344
00:17:16,465 --> 00:17:18,089
I certament no volem fer això.

345
00:17:18,089 --> 00:17:20,000
>> Així que anem a tornar i provar de nou.

346
00:17:20,000 --> 00:17:24,060
Potser el que cal fer
és establir de 12 següent punter

347
00:17:24,060 --> 00:17:28,290
l'antic cap de la primera llista,
llavors podem moure la llista més.

348
00:17:28,290 --> 00:17:30,420
I de fet, aquest és el
ordre correcte que nosaltres

349
00:17:30,420 --> 00:17:32,836
ha de seguir quan estem
treballar amb llista enllaçada.

350
00:17:32,836 --> 00:17:36,460
Sempre volem connectar el
nou element a la llista,

351
00:17:36,460 --> 00:17:41,010
abans de prendre aquest tipus de
important pas de canviar

352
00:17:41,010 --> 00:17:43,360
on el cap de la llista enllaçada és.

353
00:17:43,360 --> 00:17:46,740
Un cop més, això és una cosa tan fonamental,
no volem perdre la pista d'ell.

354
00:17:46,740 --> 00:17:49,310
>> Així que volem assegurar-nos que
tot està encadenat junts,

355
00:17:49,310 --> 00:17:52,040
abans de passar aquest punter.

356
00:17:52,040 --> 00:17:55,300
I pel que aquest seria l'ordre correcte,
que és connectar 12 a la llista,

357
00:17:55,300 --> 00:17:57,630
després dir que la llista comença 1 des.

358
00:17:57,630 --> 00:18:00,860
Si ens va dir que la llista comença a les 12 i
després va tractar de connectar 12 a la llista,

359
00:18:00,860 --> 00:18:02,193
ja hem vist el que passa.

360
00:18:02,193 --> 00:18:04,920
Perdem la llista per error.

361
00:18:04,920 --> 00:18:06,740
>> OK, així que una cosa més que parlar.

362
00:18:06,740 --> 00:18:09,750
Què passa si volem desfer-nos d'
tota una llista lligada a la vegada?

363
00:18:09,750 --> 00:18:11,750
Un cop més, estem mallocing
tot aquest espai, de manera que

364
00:18:11,750 --> 00:18:13,351
necessari per alliberar quan hàgim acabat.

365
00:18:13,351 --> 00:18:15,350
Així que ara volem eliminar
la llista enllaçada sencer.

366
00:18:15,350 --> 00:18:16,850
Bé, què és el que volem fer?

367
00:18:16,850 --> 00:18:20,460
>> Si hem arribat al punter nul, ens
vol deixar, en cas contrari, simplement esborri

368
00:18:20,460 --> 00:18:23,420
la resta de la llista i després em allibera.

369
00:18:23,420 --> 00:18:28,890
Elimineu la resta de la llista,
i després alliberar el node actual.

370
00:18:28,890 --> 00:18:32,850
El que fa que el so com,
quina tècnica hem de parlar

371
00:18:32,850 --> 00:18:35,440
sobre prèviament sona això?

372
00:18:35,440 --> 00:18:39,560
Eliminar tots els altres, a continuació,
tornar i em eliminar.

373
00:18:39,560 --> 00:18:42,380
>> Aquesta és la recursivitat, hem fet la
problema una mica més petit,

374
00:18:42,380 --> 00:18:46,910
estem dient esborrar tot el món
persona, llavors vostè em pot eliminar.

375
00:18:46,910 --> 00:18:50,940
I més pel camí, aquest node
diran, esborrar tots els altres.

376
00:18:50,940 --> 00:18:53,940
Però amb el temps arribarem a la
punt en el qual la llista és nul,

377
00:18:53,940 --> 00:18:55,310
i aquest és el nostre cas base.

378
00:18:55,310 --> 00:18:57,010
>> Així que anem a fer una ullada a això,
i com això podria funcionar.

379
00:18:57,010 --> 00:18:59,759
Així que aquí està la nostra llista, que és el mateix
Enumerem només estàvem parlant,

380
00:18:59,759 --> 00:19:00,980
i hi ha els passos.

381
00:19:00,980 --> 00:19:04,200
Hi ha una gran quantitat de text aquí, però
esperem que la visualització l'ajudarà.

382
00:19:04,200 --> 00:19:08,557
>> Així que tener-- i també vam aturar
la nostra marcs de pila il·lustració

383
00:19:08,557 --> 00:19:10,890
del nostre vídeo en piles de trucades,
i espero que tot això

384
00:19:10,890 --> 00:19:13,260
junts li mostrarà el que està passant.

385
00:19:13,260 --> 00:19:14,510
Així que aquí està el nostre codi pseudocodi.

386
00:19:14,510 --> 00:19:17,830
Si arribem a un nul
punter, parada, en cas contrari,

387
00:19:17,830 --> 00:19:21,320
eliminar la resta de la llista,
a continuació, alliberar el node actual.

388
00:19:21,320 --> 00:19:25,700
Així que ara mateix, pel·lícules--
el punter que estem

389
00:19:25,700 --> 00:19:28,410
passant per destruir punts a 12.

390
00:19:28,410 --> 00:19:33,340
12 no és un punter nul, així que estem
va a eliminar la resta de la llista.

391
00:19:33,340 --> 00:19:35,450
>> El que està esborrant el
resta de nosaltres involucrats?

392
00:19:35,450 --> 00:19:37,950
Bé, significa fer una
trucar per destruir, dient:

393
00:19:37,950 --> 00:19:42,060
15 que és el començament de la
resta de la llista que volem destruir.

394
00:19:42,060 --> 00:19:47,480
I així la crida a destruir
12 és tipus d'en espera.

395
00:19:47,480 --> 00:19:52,690
Ha congelat allà, esperant el
cridar per destruir 15, per acabar la seva feina.

396
00:19:52,690 --> 00:19:56,280
>> Bé, 15 no és un punter nul, i
pel que dirà, està bé,

397
00:19:56,280 --> 00:19:58,450
així, elimini la resta de la llista.

398
00:19:58,450 --> 00:20:00,760
La resta de la llista comença
a les 9, de manera que només haurem de

399
00:20:00,760 --> 00:20:04,514
espereu fins que s'elimini tot el que
coses, i després tornar i em eliminar.

400
00:20:04,514 --> 00:20:06,680
Bé setembre que dirà, bé,
Jo no sóc un punter nul,

401
00:20:06,680 --> 00:20:09,020
així eliminar la resta de la llista d'aquí.

402
00:20:09,020 --> 00:20:11,805
I així tractar de destruir 13.

403
00:20:11,805 --> 00:20:15,550
13 diu: Jo no sóc punter nul,
el mateix, passa la pilota.

404
00:20:15,550 --> 00:20:17,930
10 no és punter nul, 10
conté un punter nul,

405
00:20:17,930 --> 00:20:20,200
però 10 no és en si mateixa una
punter nul en aquest moment,

406
00:20:20,200 --> 00:20:22,470
i pel que passa els diners també.

407
00:20:22,470 --> 00:20:25,560
>> I ara una llista dels punts allà,
Realment seria apuntar a some--

408
00:20:25,560 --> 00:20:28,710
si tingués més espai en la imatge,
seria apuntar a un cert espai a l'atzar

409
00:20:28,710 --> 00:20:29,960
que no sabem el que és.

410
00:20:29,960 --> 00:20:34,680
És el punter nul, però, la llista
s'estableix ara, literalment, és valors nuls.

411
00:20:34,680 --> 00:20:36,820
S'assenyala a la dreta dins d'aquesta caixa vermella.

412
00:20:36,820 --> 00:20:39,960
Arribem a un punter nul, de manera que
podem aturar, i estem fet.

413
00:20:39,960 --> 00:20:46,230
>> I perquè el marc porpra és ara-- al
part superior de stack-- que és el marc actiu,

414
00:20:46,230 --> 00:20:47,017
però es fa.

415
00:20:47,017 --> 00:20:48,600
Si hem arribat a un punter nul, per.

416
00:20:48,600 --> 00:20:51,290
Nosaltres no fem res,
no es pot alliberar un punter nul,

417
00:20:51,290 --> 00:20:55,070
que no malloc qualsevol
espai, i així hem acabat.

418
00:20:55,070 --> 00:20:57,590
Així que marc de funció
es destrueix, i nosaltres

419
00:20:57,590 --> 00:21:00,930
resume-- recollim on ho vam deixar
amb la següent més alta, la qual cosa

420
00:21:00,930 --> 00:21:02,807
És aquest marc blau fosc aquí.

421
00:21:02,807 --> 00:21:04,390
Així que prenem just on ho vam deixar.

422
00:21:04,390 --> 00:21:06,598
Hem suprimit la resta de la
llista ja, de manera que ara estem

423
00:21:06,598 --> 00:21:08,000
va alliberar els nodes actuals.

424
00:21:08,000 --> 00:21:12,920
Així que ara podem alliberar aquest node, i ara
hem arribat al final de la funció.

425
00:21:12,920 --> 00:21:16,810
I perquè marc de funció es destrueix,
i nosaltres recollim en el blau clar.

426
00:21:16,810 --> 00:21:20,650
>> Així que says-- ja he done--
suprimir la resta de la llista, per la qual

427
00:21:20,650 --> 00:21:23,140
alliberar el node actual.

428
00:21:23,140 --> 00:21:26,520
I ara el quadre groc és
tornar al cim de la pila.

429
00:21:26,520 --> 00:21:29,655
I així com veus, ara estem
la destrucció de la llista de dreta a esquerra.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> ¿Què hauria passat, però,
si haguéssim fet les coses de manera equivocada?

432
00:21:37,280 --> 00:21:39,410
Igual que quan intentem
per afegir un element.

433
00:21:39,410 --> 00:21:41,909
Si mal estat de la cadena, en cas
no ens connectem els punters

434
00:21:41,909 --> 00:21:44,690
en l'ordre correcte, si
alliberat al primer element,

435
00:21:44,690 --> 00:21:47,420
si ens alliberem de la
cap de la llista, ara

436
00:21:47,420 --> 00:21:49,642
no hi ha manera de referir-se a
la resta de la llista.

437
00:21:49,642 --> 00:21:51,350
I així tindríem
tot orfes,

438
00:21:51,350 --> 00:21:53,880
haguéssim tingut el que hi ha
diu una pèrdua de memòria.

439
00:21:53,880 --> 00:21:56,800
Si vostè recorda del nostre vídeo
en l'assignació de memòria dinàmica,

440
00:21:56,800 --> 00:21:58,650
això no és molt bo.

441
00:21:58,650 --> 00:22:00,810
>> Així que com ja he dit, hi ha
són diverses operacions

442
00:22:00,810 --> 00:22:04,010
que hem de fer servir per treballar
amb llista vinculada efectivament.

443
00:22:04,010 --> 00:22:08,430
I t'hauràs adonat vaig ometre un,
l'eliminació d'un sol element d'una lligat

444
00:22:08,430 --> 00:22:09,064
llista.

445
00:22:09,064 --> 00:22:10,980
La raó per la qual vaig fer
és que és en realitat una mica

446
00:22:10,980 --> 00:22:14,360
difícil de pensar sobre com eliminar
un sol element d'una individualment

447
00:22:14,360 --> 00:22:15,600
llista enllaçada.

448
00:22:15,600 --> 00:22:19,950
Hem de ser capaços de passar per alt
alguna cosa a la llista, que

449
00:22:19,950 --> 00:22:22,975
vol dir que arribem a un nosaltres point--
vols eliminar aquest node--

450
00:22:22,975 --> 00:22:25,350
però per tal que sigui així que
no perdi cap informació,

451
00:22:25,350 --> 00:22:30,530
hem de connectar aquest
node d'aquí, aquí.

452
00:22:30,530 --> 00:22:33,390
>> Així que probablement vaig fer malament
des d'una perspectiva visual.

453
00:22:33,390 --> 00:22:36,830
Així que estem en el començament de la nostra
llista, estem procedint a través,

454
00:22:36,830 --> 00:22:40,510
volem eliminar aquest node.

455
00:22:40,510 --> 00:22:43,440
Si ens limitem a esborrar-ho,
hem trencat la cadena.

456
00:22:43,440 --> 00:22:45,950
Aquest node aquí
es refereix a tota la resta,

457
00:22:45,950 --> 00:22:48,260
que conté la cadena d'ara endavant.

458
00:22:48,260 --> 00:22:51,190
>> Així que el que hem de fer realitat
després d'arribar a aquest punt,

459
00:22:51,190 --> 00:22:56,670
és que hem de donar un pas enrere un, i
connectar aquest node a través d'aquest node,

460
00:22:56,670 --> 00:22:58,590
així llavors podem eliminar
l'un al centre.

461
00:22:58,590 --> 00:23:02,120
Però les llistes per separat enllaçats no fan
ens proporcionen una manera d'anar cap enrere.

462
00:23:02,120 --> 00:23:05,160
Així que hem de mantenir qualsevol
dos punters, i moure'ls

463
00:23:05,160 --> 00:23:09,527
espècie de pas fora, una darrere de l'
altra mesura que avancem, o arribar a un punt

464
00:23:09,527 --> 00:23:11,110
i després enviar un altre punter a través.

465
00:23:11,110 --> 00:23:13,150
I com es pot veure,
pot ser una mica desordenat.

466
00:23:13,150 --> 00:23:15,360
Afortunadament, tenim
una altra manera de resoldre això,

467
00:23:15,360 --> 00:23:17,810
quan parlem de llistes doblement enllaçades.

468
00:23:17,810 --> 00:23:20,720
>> Sóc Doug Lloyd, això és CS50.

469
00:23:20,720 --> 00:23:22,298