1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] A la programació, sovint necessitem per representar llistes de valors,

2
00:00:10,050 --> 00:00:12,840
com ara els noms dels estudiants d'una secció

3
00:00:12,840 --> 00:00:15,100
o classificacions en l'última prova.

4
00:00:15,100 --> 00:00:17,430
>> En el llenguatge C, va declarar matrius poden utilitzar

5
00:00:17,430 --> 00:00:19,160
per emmagatzemar llistes.

6
00:00:19,160 --> 00:00:21,200
És fàcil enumerar els elements d'una llista

7
00:00:21,200 --> 00:00:23,390
emmagatzemats en una matriu, i si vostè necessita per accedir a

8
00:00:23,390 --> 00:00:25,050
o modificar l'element de la llista ITH

9
00:00:25,050 --> 00:00:27,570
per algun índex arbitrari I,

10
00:00:27,570 --> 00:00:29,910
que es pot fer en un temps constant,

11
00:00:29,910 --> 00:00:31,660
però les matrius tenen desavantatges, també.

12
00:00:31,660 --> 00:00:33,850
>> Quan els declare, estem obligats a dir

13
00:00:33,850 --> 00:00:35,900
des del principi el grans que són,

14
00:00:35,900 --> 00:00:38,160
és a dir, quants elements es poden emmagatzemar

15
00:00:38,160 --> 00:00:40,780
i el gran que aquests elements són, que es determina pel seu tipus.

16
00:00:40,780 --> 00:00:45,450
Per exemple, arranjament de int (10)

17
00:00:45,450 --> 00:00:48,220
Pot emmagatzemar 10 elements

18
00:00:48,220 --> 00:00:50,200
que tenen la mida d'un int.

19
00:00:50,200 --> 00:00:52,590
>> No podem canviar la mida d'una matriu després de la declaració.

20
00:00:52,590 --> 00:00:55,290
Hem de fer una nova matriu si volem emmagatzemar més elements.

21
00:00:55,290 --> 00:00:57,410
La raó d'aquesta limitació que existeix és que el nostre

22
00:00:57,410 --> 00:00:59,040
programa emmagatzema tota la matriu

23
00:00:59,040 --> 00:01:02,310
com un tros contigu de memòria.

24
00:01:02,310 --> 00:01:04,500
Dir això és el buffer on s'emmagatzema en la nostra matriu.

25
00:01:04,500 --> 00:01:06,910
Hi pot haver altres variables

26
00:01:06,910 --> 00:01:08,310
situat just al costat de la matriu

27
00:01:08,310 --> 00:01:10,060
a la memòria, de manera que no pot

28
00:01:10,060 --> 00:01:12,060
només que la matriu més gran.

29
00:01:12,060 --> 00:01:15,700
>> De vegades ens agradaria que el comerç de la matriu ràpida velocitat d'accés a dades

30
00:01:15,700 --> 00:01:17,650
per una mica més de flexibilitat.

31
00:01:17,650 --> 00:01:20,380
Introduïu la llista enllaçada, una altra estructura de dades bàsiques

32
00:01:20,380 --> 00:01:22,360
vostè podria no ser tan familiaritzats.

33
00:01:22,360 --> 00:01:24,200
En un nivell alt,

34
00:01:24,200 --> 00:01:26,840
una llista enllaçada emmagatzema les dades en una seqüència de nodes

35
00:01:26,840 --> 00:01:29,280
que estan connectats entre si amb enllaços,

36
00:01:29,280 --> 00:01:31,760
per tant "llista enllaçada. 'el nom

37
00:01:31,760 --> 00:01:33,840
Com veurem, aquesta diferència en el disseny

38
00:01:33,840 --> 00:01:35,500
condueix a diferents avantatges i desavantatges

39
00:01:35,500 --> 00:01:37,000
d'una matriu.

40
00:01:37,000 --> 00:01:39,840
>> Aquí hi ha un codi C per a una llista molt simple enllaçada de nombres enters.

41
00:01:39,840 --> 00:01:42,190
Es pot veure que hem representat a cada node

42
00:01:42,190 --> 00:01:45,520
a la llista com una estructura que conté dues coses,

43
00:01:45,520 --> 00:01:47,280
un enter per emmagatzemar anomenat 'val'

44
00:01:47,280 --> 00:01:50,460
i un enllaç per al node següent a la llista

45
00:01:50,460 --> 00:01:52,990
que representem com un punter anomenat 'next'.

46
00:01:54,120 --> 00:01:56,780
D'aquesta manera, podem seguir la llista sencera

47
00:01:56,780 --> 00:01:58,790
amb només un únic punter al node primer,

48
00:01:58,790 --> 00:02:01,270
i després podem seguir els següents consells

49
00:02:01,270 --> 00:02:03,130
per al segon node,

50
00:02:03,130 --> 00:02:05,280
al node tercer,

51
00:02:05,280 --> 00:02:07,000
per al quart node,

52
00:02:07,000 --> 00:02:09,889
i així successivament, fins arribar a la final de la llista.

53
00:02:10,520 --> 00:02:12,210
>> Vostè pot ser capaç de veure un avantatge que això té

54
00:02:12,210 --> 00:02:14,490
sobre l'estructura matriu estàtica - amb una llista enllaçada,

55
00:02:14,490 --> 00:02:16,450
no necessitem una gran part de la memòria del tot.

56
00:02:17,400 --> 00:02:20,530
El node 1 de la llista podria viure en aquest lloc en la memòria,

57
00:02:20,530 --> 00:02:23,160
i el segon node podria ser tot el camí fins aquí.

58
00:02:23,160 --> 00:02:25,780
Podem arribar a tots els nodes no importa on en la memòria són,

59
00:02:25,780 --> 00:02:28,890
perquè a partir de la primera node, el punter següent de cada node

60
00:02:28,890 --> 00:02:31,700
ens diu exactament on anar després.

61
00:02:31,700 --> 00:02:33,670
>> A més, no has de dir per avançat

62
00:02:33,670 --> 00:02:36,740
el gran que una llista enllaçada és el camí que fem amb arrays estàtics,

63
00:02:36,740 --> 00:02:39,060
ja que podem seguir afegint nodes a una llista

64
00:02:39,060 --> 00:02:42,600
sempre que no hi ha espai en algun lloc de la memòria dels nous nodes.

65
00:02:42,600 --> 00:02:45,370
Per tant, les llistes enllaçades són fàcils de canviar la mida de forma dinàmica.

66
00:02:45,370 --> 00:02:47,950
Diguem, més tard en el programa hem d'afegir més nodes

67
00:02:47,950 --> 00:02:49,350
a la nostra llista.

68
00:02:49,350 --> 00:02:51,480
Per inserir un nou node a la llista sobre la marxa,

69
00:02:51,480 --> 00:02:53,740
tot el que hem de fer és assignar memòria per a aquest node,

70
00:02:53,740 --> 00:02:55,630
plop en el valor de les dades,

71
00:02:55,630 --> 00:02:59,070
i després col · locar on vulguem amb la configuració dels indicadors apropiats.

72
00:02:59,070 --> 00:03:02,310
>> Per exemple, si volguéssim posar un node en el medi

73
00:03:02,310 --> 00:03:04,020
els nodes 2 i 3 de la llista,

74
00:03:04,020 --> 00:03:06,800
 no hauríem de moure els nodes segon o tercer en absolut.

75
00:03:06,800 --> 00:03:09,190
Diguem que vas a inserir aquest node vermell.

76
00:03:09,190 --> 00:03:12,890
Tot el que hauria de fer és configurar punter següent del nou node

77
00:03:12,890 --> 00:03:14,870
perquè apunti al node 3

78
00:03:14,870 --> 00:03:18,580
i després tornar a col · locar el punter següent node de segon

79
00:03:18,580 --> 00:03:20,980
perquè apunti al nostre nou node.

80
00:03:22,340 --> 00:03:24,370
Per tant, podem canviar la mida de les nostres llistes sobre la marxa

81
00:03:24,370 --> 00:03:26,090
ja que el nostre equip no depèn de la indexació,

82
00:03:26,090 --> 00:03:28,990
sinó més aviat en vincular l'ús de punters per emmagatzemar-los.

83
00:03:29,120 --> 00:03:31,600
>> Llistes Però un desavantatge de vinculats

84
00:03:31,600 --> 00:03:33,370
és que, a diferència d'una matriu estàtica,

85
00:03:33,370 --> 00:03:36,690
l'ordinador no només pot saltar a la meitat de la llista.

86
00:03:38,040 --> 00:03:40,780
Atès que l'equip ha de visitar cada node en la llista enllaçada

87
00:03:40,780 --> 00:03:42,330
per arribar a la següent,

88
00:03:42,330 --> 00:03:44,770
que prendrà més temps per trobar un node particular

89
00:03:44,770 --> 00:03:46,400
el que ho faria en una matriu.

90
00:03:46,400 --> 00:03:48,660
Per recórrer tota la llista pren temps proporcional

91
00:03:48,660 --> 00:03:50,580
a la longitud de la llista,

92
00:03:50,580 --> 00:03:54,630
o O (n) en notació asimptòtica.

93
00:03:54,630 --> 00:03:56,510
De mitjana, arribant qualsevol node

94
00:03:56,510 --> 00:03:58,800
També es necessita temps proporcional a n.

95
00:03:58,800 --> 00:04:00,700
>> Ara, anem a realment escriure codi

96
00:04:00,700 --> 00:04:02,000
que treballa amb llistes enllaçades.

97
00:04:02,000 --> 00:04:04,220
Diguem que volem una llista enllaçada d'enters.

98
00:04:04,220 --> 00:04:06,140
Podem representar un node en la llista de nou

99
00:04:06,140 --> 00:04:08,340
com una estructura amb dos camps,

100
00:04:08,340 --> 00:04:10,750
un valor enter anomenat 'val'

101
00:04:10,750 --> 00:04:13,490
i un punter proper al següent node de la llista.

102
00:04:13,490 --> 00:04:15,660
Bé, sembla bastant simple.

103
00:04:15,660 --> 00:04:17,220
>> Suposem que volem escriure una funció

104
00:04:17,220 --> 00:04:19,329
que recorre la llista i imprimeix el

105
00:04:19,329 --> 00:04:22,150
valor emmagatzemat en l'últim node de la llista.

106
00:04:22,150 --> 00:04:24,850
Bé, això vol dir que haurem de recórrer tots els nodes de la llista

107
00:04:24,850 --> 00:04:27,310
per trobar l'última, però ja no estem afegint

108
00:04:27,310 --> 00:04:29,250
o esborrar res, no volem canviar

109
00:04:29,250 --> 00:04:32,210
l'estructura interna dels punters següents a la llista.

110
00:04:32,210 --> 00:04:34,790
>> Per tant, anem a necessitar un punter específicament per traversal

111
00:04:34,790 --> 00:04:36,940
que anomenarem "crawler".

112
00:04:36,940 --> 00:04:38,870
Es arrosseguen a través de tots els elements de la llista

113
00:04:38,870 --> 00:04:41,190
seguint la cadena de punters propers.

114
00:04:41,190 --> 00:04:43,750
Tots hem emmagatzemat és un punter al node primer,

115
00:04:43,750 --> 00:04:45,730
o "cap" de la llista.

116
00:04:45,730 --> 00:04:47,370
Punts del cap a la primera node.

117
00:04:47,370 --> 00:04:49,120
És de tipus punter a node.

118
00:04:49,120 --> 00:04:51,280
>> Per obtenir l'actual primera node a la llista,

119
00:04:51,280 --> 00:04:53,250
hem d'eliminar la referència aquest indicador,

120
00:04:53,250 --> 00:04:55,100
però abans de poder deferenciarlo, hem de comprovar

121
00:04:55,100 --> 00:04:57,180
si el punter és nul en primer lloc.

122
00:04:57,180 --> 00:04:59,190
Si és nul, la llista és buida,

123
00:04:59,190 --> 00:05:01,320
i hem imprimir un missatge que, pel fet que la llista és buida,

124
00:05:01,320 --> 00:05:03,250
no hi ha últim node.

125
00:05:03,250 --> 00:05:05,190
Però, suposem que la llista no és buida.

126
00:05:05,190 --> 00:05:08,340
Si no és així, llavors hem de gatejar per tota la llista

127
00:05:08,340 --> 00:05:10,440
fins arribar a l'últim node de la llista,

128
00:05:10,440 --> 00:05:13,030
i com podem saber si estem davant l'últim node a la llista?

129
00:05:13,670 --> 00:05:16,660
>> Bé, si el punter següent d'un node és nul,

130
00:05:16,660 --> 00:05:18,320
sabem que estem al final

131
00:05:18,320 --> 00:05:22,390
des del següent punter darrera no tindria cap node següent a la llista per apuntar.

132
00:05:22,390 --> 00:05:26,590
És una bona pràctica per mantenir sempre punter següent de l'últim node de s'inicialitzen a null

133
00:05:26,590 --> 00:05:30,800
tenir una propietat estàndard que ens avisa quan hem arribat al final de la llista.

134
00:05:30,800 --> 00:05:33,510
>> Per tant, si crawler → següent és nul,

135
00:05:34,120 --> 00:05:38,270
recordar que la sintaxi de fletxa és un accés directe per eliminar la referència

136
00:05:38,270 --> 00:05:40,010
un punter a una estructura, a continuació, accedir a

137
00:05:40,010 --> 00:05:42,510
seu següent camp equivalent al maldestre:

138
00:05:42,510 --> 00:05:48,750
(* Crawler). Següent.

139
00:05:49,820 --> 00:05:51,260
Una vegada que hagis trobat l'últim node,

140
00:05:51,260 --> 00:05:53,830
volem imprimir crawler → val,

141
00:05:53,830 --> 00:05:55,000
el valor en el node actual

142
00:05:55,000 --> 00:05:57,130
que sabem que és l'última.

143
00:05:57,130 --> 00:05:59,740
En cas contrari, si no estem encara en l'últim node de la llista,

144
00:05:59,740 --> 00:06:02,340
hem de passar a la següent node a la llista

145
00:06:02,340 --> 00:06:04,750
i comprovar si aquest és l'últim.

146
00:06:04,750 --> 00:06:07,010
Per això, s'acaba d'establir nostre punter sobre erugues

147
00:06:07,010 --> 00:06:09,840
per apuntar al següent valor del node actual,

148
00:06:09,840 --> 00:06:11,680
és a dir, el node següent a la llista.

149
00:06:11,680 --> 00:06:13,030
Això es fa mitjançant l'establiment

150
00:06:13,030 --> 00:06:15,280
crawler = crawler → següent.

151
00:06:16,050 --> 00:06:18,960
Després repetim aquest procés, amb un llaç per exemple,

152
00:06:18,960 --> 00:06:20,960
fins a trobar l'últim node.

153
00:06:20,960 --> 00:06:23,150
Així, per exemple, si rastrejador estava apuntant al capdavant,

154
00:06:24,050 --> 00:06:27,710
ens vam proposar rastrejador perquè apunti a erugues → següent,

155
00:06:27,710 --> 00:06:30,960
que és el mateix que el camp proper de la primera node.

156
00:06:30,960 --> 00:06:33,620
Així que, ara que el nostre rastrejador està apuntant al node 2,

157
00:06:33,620 --> 00:06:35,480
i, de nou, es repeteix això amb un bucle,

158
00:06:37,220 --> 00:06:40,610
fins que hàgim trobat l'últim node, és a dir,

159
00:06:40,610 --> 00:06:43,640
on punter següent del node apunta null.

160
00:06:43,640 --> 00:06:45,070
I aquí el tenim,

161
00:06:45,070 --> 00:06:47,620
hem trobat l'últim node de la llista, i la impressió del seu valor,

162
00:06:47,620 --> 00:06:50,800
només ha d'utilitzar crawler → val.

163
00:06:50,800 --> 00:06:53,130
>> Travessant no és tan dolent, però què passa amb la inserció?

164
00:06:53,130 --> 00:06:56,290
Diguem que volem inserir un nombre sencer en la 4 ª posició

165
00:06:56,290 --> 00:06:58,040
en una llista de nombres enters.

166
00:06:58,040 --> 00:07:01,280
Que està entre els nodes actuals tercer i quart.

167
00:07:01,280 --> 00:07:03,760
Un cop més, hem de recórrer la llista només per

168
00:07:03,760 --> 00:07:06,520
arribar a la tercera part, la qual estem inserint després.

169
00:07:06,520 --> 00:07:09,300
Així, vam crear un punter rastrejador de nou per recórrer la llista,

170
00:07:09,300 --> 00:07:11,400
comprovar si el nostre cap punter és nul,

171
00:07:11,400 --> 00:07:14,810
i si no ho és, apuntar amb el punter sobre erugues en el node principal.

172
00:07:16,880 --> 00:07:18,060
Per tant, estem en l'element primer.

173
00:07:18,060 --> 00:07:21,020
Hem d'anar cap endavant 2 elements més abans de poder inserir,

174
00:07:21,020 --> 00:07:23,390
pel que podem utilitzar un bucle for

175
00:07:23,390 --> 00:07:26,430
int i = 1; i <3; i + +

176
00:07:26,430 --> 00:07:28,590
i en cada iteració del bucle,

177
00:07:28,590 --> 00:07:31,540
avançar en el punter sobre erugues presentades per un node

178
00:07:31,540 --> 00:07:34,570
comprovant si el camp proper del node actual és nul · la,

179
00:07:34,570 --> 00:07:37,550
i si no és així, moure el nostre rastrejador punter al següent node

180
00:07:37,550 --> 00:07:41,810
fixant igual al següent punter del node actual.

181
00:07:41,810 --> 00:07:45,210
Per tant, des del nostre bucle per fer això, diu

182
00:07:45,210 --> 00:07:47,550
dues vegades,

183
00:07:49,610 --> 00:07:51,190
hem arribat al node 3,

184
00:07:51,190 --> 00:07:53,110
i una vegada que el nostre punter rastrejador ha arribat al node després de

185
00:07:53,110 --> 00:07:55,270
que volem inserir el nostre nou sencer,

186
00:07:55,270 --> 00:07:57,050
Com és en realitat la inserció?

187
00:07:57,050 --> 00:07:59,440
>> Doncs bé, el nostre nou sencer ha de ser inserit en la llista

188
00:07:59,440 --> 00:08:01,250
com a part de la seva pròpia estructura de node,

189
00:08:01,250 --> 00:08:03,140
ja que això és realment una seqüència de nodes.

190
00:08:03,140 --> 00:08:05,690
Per tant, farem un nou punter al node

191
00:08:05,690 --> 00:08:08,910
anomenat 'new_node,'

192
00:08:08,910 --> 00:08:11,800
i configurar-lo perquè apunti a la memòria que ara assignar

193
00:08:11,800 --> 00:08:14,270
a la pila per al node en si,

194
00:08:14,270 --> 00:08:16,000
i la quantitat de memòria hem d'assignar?

195
00:08:16,000 --> 00:08:18,250
Doncs bé, la mida d'un node,

196
00:08:20,450 --> 00:08:23,410
i volem establir el seu camp val l'enter que volem inserir.

197
00:08:23,410 --> 00:08:25,590
Diguem, 6.

198
00:08:25,590 --> 00:08:27,710
Ara, el node conté el nostre valor sencer.

199
00:08:27,710 --> 00:08:30,650
També és una bona pràctica per inicialitzar camp proper del nou node

200
00:08:30,650 --> 00:08:33,690
per apuntar a null,

201
00:08:33,690 --> 00:08:35,080
però ara què?

202
00:08:35,080 --> 00:08:37,179
>> Cal canviar l'estructura interna de la llista

203
00:08:37,179 --> 00:08:40,409
i els indicadors continguts en els següents de la llista

204
00:08:40,409 --> 00:08:42,950
Els nodes 3 i 4.

205
00:08:42,950 --> 00:08:46,560
Atès que els punters propers determinar l'ordre de la llista,

206
00:08:46,560 --> 00:08:48,650
i ja que estem introduint el nostre nou node

207
00:08:48,650 --> 00:08:50,510
a la dreta en el mitjà de la llista,

208
00:08:50,510 --> 00:08:52,010
que pot ser una mica complicat.

209
00:08:52,010 --> 00:08:54,250
Això és perquè, recordi, el nostre equip

210
00:08:54,250 --> 00:08:56,250
només coneix la ubicació dels nodes a la llista

211
00:08:56,250 --> 00:09:00,400
perquè dels punters propers emmagatzemats en els nodes anteriors.

212
00:09:00,400 --> 00:09:03,940
Per tant, si mai perdut el rastre de cap d'aquests llocs,

213
00:09:03,940 --> 00:09:06,860
diuen que en canviar un dels punters següents a la llista,

214
00:09:06,860 --> 00:09:09,880
Per exemple, diguem que canviem

215
00:09:09,880 --> 00:09:12,920
camp següent node de la tercera de

216
00:09:12,920 --> 00:09:15,610
perquè apunti a algun node per aquí.

217
00:09:15,610 --> 00:09:17,920
Ens agradaria estar fora de sort, ja que no ho faria

218
00:09:17,920 --> 00:09:20,940
Té alguna idea d'on trobar la resta de la llista,

219
00:09:20,940 --> 00:09:23,070
i això és, òbviament, molt malament.

220
00:09:23,070 --> 00:09:25,080
Per tant, hem de tenir molta cura per tal de

221
00:09:25,080 --> 00:09:28,360
en el qual manipulem nostres punters propers durant la inserció.

222
00:09:28,360 --> 00:09:30,540
>> Així que, per simplificar això, direm que

223
00:09:30,540 --> 00:09:32,220
nostres primers 4 nodes

224
00:09:32,220 --> 00:09:36,200
es denominen A, B, C, i D, amb les fletxes que representen la cadena de punters

225
00:09:36,200 --> 00:09:38,070
que connecten els nodes.

226
00:09:38,070 --> 00:09:40,050
Per tant, hem d'inserir el nostre nou node

227
00:09:40,050 --> 00:09:42,070
entre els nodes C i D.

228
00:09:42,070 --> 00:09:45,060
És molt important fer-ho en l'ordre correcte, i jo et mostraré per què.

229
00:09:45,060 --> 00:09:47,500
>> Fem una ullada a la forma incorrecta de fer-ho en primer lloc.

230
00:09:47,500 --> 00:09:49,490
Hey, sabem que el nou node ha de venir a la dreta després de C,

231
00:09:49,490 --> 00:09:51,910
així que anem a establir el punter pròxim C

232
00:09:51,910 --> 00:09:54,700
perquè apunti a new_node.

233
00:09:56,530 --> 00:09:59,180
D'acord, sembla estar bé, només hem d'acabar ara per

234
00:09:59,180 --> 00:10:01,580
fer punt del nou node punter prop de D,

235
00:10:01,580 --> 00:10:03,250
però espera, com podem fer això?

236
00:10:03,250 --> 00:10:05,170
L'única cosa que ens pot dir on D és,

237
00:10:05,170 --> 00:10:07,630
va ser el següent punter emmagatzemat prèviament en C,

238
00:10:07,630 --> 00:10:09,870
però ens va tornar a escriure aquest punter

239
00:10:09,870 --> 00:10:11,170
perquè apunti al nou node,

240
00:10:11,170 --> 00:10:14,230
de manera que ja no tenim ni idea d'on D és en la memòria,

241
00:10:14,230 --> 00:10:17,020
i hem perdut la resta de la llista.

242
00:10:17,020 --> 00:10:19,000
No és bo en absolut.

243
00:10:19,000 --> 00:10:21,090
>> Així que, com podem fer això bé?

244
00:10:22,360 --> 00:10:25,090
En primer lloc, assenyalar punter següent del nou node al Sr

245
00:10:26,170 --> 00:10:28,990
Ara, tant el nou node i la de C pròxims punters

246
00:10:28,990 --> 00:10:30,660
apunten cap al mateix node, D,

247
00:10:30,660 --> 00:10:32,290
però això està bé.

248
00:10:32,290 --> 00:10:35,680
Ara podem assenyalar següent punter de C en el nou node.

249
00:10:37,450 --> 00:10:39,670
Per tant, hem fet això sense perdre cap dada.

250
00:10:39,670 --> 00:10:42,280
En el codi, C és el node actual

251
00:10:42,280 --> 00:10:45,540
que el recorregut punter rastrejador fa referència,

252
00:10:45,540 --> 00:10:50,400
i D està representat pel node al qual apunta el camp següent node actual,

253
00:10:50,400 --> 00:10:52,600
o rastrejador → següent.

254
00:10:52,600 --> 00:10:55,460
Així, en primer lloc establir el punter següent del nou node

255
00:10:55,460 --> 00:10:57,370
perquè apunti a erugues → següent,

256
00:10:57,370 --> 00:11:00,880
de la mateixa manera que vam dir punter proper new_node han de tenir per

257
00:11:00,880 --> 00:11:02,780
apuntar a D a la il · lustració.

258
00:11:02,780 --> 00:11:04,540
Llavors, podem establir el punter següent del node actual

259
00:11:04,540 --> 00:11:06,330
al nostre nou node,

260
00:11:06,330 --> 00:11:10,980
la mateixa manera que va haver d'esperar al punt C new_node en el dibuix.

261
00:11:10,980 --> 00:11:12,250
Ara tot està en ordre, i no va perdre

262
00:11:12,250 --> 00:11:14,490
fer un seguiment de les dades, i vam ser capaços de simplement

263
00:11:14,490 --> 00:11:16,200
enganxar nostre nou node al mig de la llista

264
00:11:16,200 --> 00:11:19,330
sense reconstruir tota la cosa, o fins i tot canviant els elements

265
00:11:19,330 --> 00:11:22,490
la forma en què s'han hagut de amb una matriu de longitud fixa.

266
00:11:22,490 --> 00:11:26,020
>> Per tant, les llistes enllaçades són un bàsic, però important, l'estructura de dades dinàmica

267
00:11:26,020 --> 00:11:29,080
que tenen avantatges i desavantatges

268
00:11:29,080 --> 00:11:31,260
en comparació amb les matrius i altres estructures de dades,

269
00:11:31,260 --> 00:11:33,350
i com és sovint el cas en informàtica,

270
00:11:33,350 --> 00:11:35,640
és important saber quan utilitzar cada eina,

271
00:11:35,640 --> 00:11:37,960
perquè pugui triar l'eina adequada per al treball correcte.

272
00:11:37,960 --> 00:11:40,060
>> Per practicar més, intenti escriure funcions per

273
00:11:40,060 --> 00:11:42,080
eliminar nodes d'una llista enllaçada -

274
00:11:42,080 --> 00:11:44,050
recordi anar amb compte amb l'ordre en què es reorganitzen

275
00:11:44,050 --> 00:11:47,430
els punters següents per assegurar-se que no perdi una bona part de la seva llista -

276
00:11:47,430 --> 00:11:50,200
o una funció per comptar els nodes en una llista enllaçada,

277
00:11:50,200 --> 00:11:53,280
o una diversió, per invertir l'ordre de tots els nodes d'una llista enllaçada.

278
00:11:53,280 --> 00:11:56,090
>> El meu nom és Jackson Steinkamp, ​​això és CS50.