1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Na programación, moitas veces necesitamos representar listas de valores,

2
00:00:10,050 --> 00:00:12,840
como os nomes dos alumnos nunha sección

3
00:00:12,840 --> 00:00:15,100
ou os seus resultados no último exame.

4
00:00:15,100 --> 00:00:17,430
>> Na linguaxe C, declarado matrices poden ser utilizadas

5
00:00:17,430 --> 00:00:19,160
para almacenar listas.

6
00:00:19,160 --> 00:00:21,200
É doado enumerar os elementos dunha lista

7
00:00:21,200 --> 00:00:23,390
almacenados nunha matriz, e se precisa acceder

8
00:00:23,390 --> 00:00:25,050
ou modificar o elemento da lista om

9
00:00:25,050 --> 00:00:27,570
por algún índice arbitrario I,

10
00:00:27,570 --> 00:00:29,910
que se pode facer en tempo constante,

11
00:00:29,910 --> 00:00:31,660
pero as matrices presentan desvantaxes, tamén.

12
00:00:31,660 --> 00:00:33,850
>> Cando declaralo los, somos obrigados a dicir

13
00:00:33,850 --> 00:00:35,900
na fronte como son grandes,

14
00:00:35,900 --> 00:00:38,160
é dicir, cantos elementos que poden almacenar

15
00:00:38,160 --> 00:00:40,780
e que o tamaño destes elementos son, que é determinada polo tipo.

16
00:00:40,780 --> 00:00:45,450
Por exemplo, int arr (10)

17
00:00:45,450 --> 00:00:48,220
pode almacenar 10 elementos

18
00:00:48,220 --> 00:00:50,200
que son do tamaño dun int.

19
00:00:50,200 --> 00:00:52,590
>> Non podemos cambiar o tamaño dunha matriz tras a declaración.

20
00:00:52,590 --> 00:00:55,290
Temos que facer unha nova matriz se desexa almacenar máis elementos.

21
00:00:55,290 --> 00:00:57,410
A razón desa limitación existe é que o noso

22
00:00:57,410 --> 00:00:59,040
programa almacena todo o conxunto

23
00:00:59,040 --> 00:01:02,310
como unha peza contiguo de memoria.

24
00:01:02,310 --> 00:01:04,500
Dicir que este é o buffer onde se almacenan na nosa matriz.

25
00:01:04,500 --> 00:01:06,910
Pode haber outras variables

26
00:01:06,910 --> 00:01:08,310
situado ao lado da matriz

27
00:01:08,310 --> 00:01:10,060
na memoria, por iso non podemos

28
00:01:10,060 --> 00:01:12,060
só facer a matriz maior.

29
00:01:12,060 --> 00:01:15,700
>> Ás veces, nós queremos cambiar de velocidade a matriz de acceso rápido de datos

30
00:01:15,700 --> 00:01:17,650
para un pouco máis de flexibilidade.

31
00:01:17,650 --> 00:01:20,380
Escriba unha lista ligada, outra estrutura de datos básica

32
00:01:20,380 --> 00:01:22,360
non pode ser tan familiarizado.

33
00:01:22,360 --> 00:01:24,200
A un nivel elevado,

34
00:01:24,200 --> 00:01:26,840
unha lista ligada almacena os datos nunha secuencia de nodos

35
00:01:26,840 --> 00:01:29,280
que están ligados uns ós outros con ligazóns,

36
00:01:29,280 --> 00:01:31,760
polo tanto, "lista ligada." nome

37
00:01:31,760 --> 00:01:33,840
Como veremos, esta diferencia no proxecto

38
00:01:33,840 --> 00:01:35,500
conduce a diferentes vantaxes e desvantaxes

39
00:01:35,500 --> 00:01:37,000
dunha matriz.

40
00:01:37,000 --> 00:01:39,840
>> Aquí está o código C para unha lista moi sinxelo ligada de enteiros.

41
00:01:39,840 --> 00:01:42,190
Podes ver que temos representado cada nodo

42
00:01:42,190 --> 00:01:45,520
na lista como unha estrutura que contén dúas cousas,

43
00:01:45,520 --> 00:01:47,280
un enteiro para almacenar chamado 'Val'

44
00:01:47,280 --> 00:01:50,460
e un enlace ao seguinte nodo na lista

45
00:01:50,460 --> 00:01:52,990
que representamos como un punteiro chamado 'Seguinte'.

46
00:01:54,120 --> 00:01:56,780
Desta forma, é posible seguir toda a lista

47
00:01:56,780 --> 00:01:58,790
con só un único punteiro para o apartado 1,

48
00:01:58,790 --> 00:02:01,270
e entón podemos seguir os punteiros próximos

49
00:02:01,270 --> 00:02:03,130
para o apartado 2,

50
00:02:03,130 --> 00:02:05,280
para o apartado 3,

51
00:02:05,280 --> 00:02:07,000
ao apartado 4,

52
00:02:07,000 --> 00:02:09,889
e así por diante, ata chegar ao final da lista.

53
00:02:10,520 --> 00:02:12,210
>> Pode ser capaz de ver unha vantaxe que ten

54
00:02:12,210 --> 00:02:14,490
sobre a estrutura array estático - con unha lista ligada,

55
00:02:14,490 --> 00:02:16,450
non necesitamos un gran anaco de memoria completamente.

56
00:02:17,400 --> 00:02:20,530
O apartado 1 da lista podería vivir neste lugar na memoria,

57
00:02:20,530 --> 00:02:23,160
eo apartado 2 podería ser todo o camiño ata aquí.

58
00:02:23,160 --> 00:02:25,780
Podemos chegar a todos os nós, non importa onde eles están na memoria,

59
00:02:25,780 --> 00:02:28,890
porque dende o apartado 1, o punteiro preto de cada nodo

60
00:02:28,890 --> 00:02:31,700
nos di exactamente onde ir.

61
00:02:31,700 --> 00:02:33,670
>> Ademais, non hai que dicir na fronte

62
00:02:33,670 --> 00:02:36,740
como unha grande lista encadeada será a nosa forma de facer arrays estáticos,

63
00:02:36,740 --> 00:02:39,060
unha vez que podemos continuar a engadir nós a unha lista

64
00:02:39,060 --> 00:02:42,600
mentres non hai espazo en algún lugar na memoria para novos nós.

65
00:02:42,600 --> 00:02:45,370
Polo tanto, listas ligadas son fáciles de cambiar o tamaño dinamicamente.

66
00:02:45,370 --> 00:02:47,950
Dicir, máis tarde no programa, cómpre engadir máis nós

67
00:02:47,950 --> 00:02:49,350
na nosa lista.

68
00:02:49,350 --> 00:02:51,480
Para inserir un novo nodo na nosa lista en tempo real,

69
00:02:51,480 --> 00:02:53,740
todo o que temos que facer é reservar memoria para ese nodo,

70
00:02:53,740 --> 00:02:55,630
plop por valor de datos,

71
00:02:55,630 --> 00:02:59,070
e despois poñelas onde quere, axustando os punteiros apropiados.

72
00:02:59,070 --> 00:03:02,310
>> Por exemplo, se quixésemos poñer un nó no medio

73
00:03:02,310 --> 00:03:04,020
os nós 2 e 3 da lista,

74
00:03:04,020 --> 00:03:06,800
 non teriamos para mover os nós de 2 ou 3 en todo.

75
00:03:06,800 --> 00:03:09,190
Dicir que estamos introducindo este nodo vermello.

76
00:03:09,190 --> 00:03:12,890
Todo o que temos que facer é definir punteiro próximo ao novo nodo

77
00:03:12,890 --> 00:03:14,870
para apuntar para o apartado 3

78
00:03:14,870 --> 00:03:18,580
e, a continuación, religar punteiro próximo apartado 2 do

79
00:03:18,580 --> 00:03:20,980
para apuntar para o novo nodo.

80
00:03:22,340 --> 00:03:24,370
Así, podemos cambiar o tamaño nosas listas na Moscova

81
00:03:24,370 --> 00:03:26,090
desde o noso ordenador non dependen de indexación,

82
00:03:26,090 --> 00:03:28,990
pero si na conexión entre o uso de punteiros para almacena-los.

83
00:03:29,120 --> 00:03:31,600
>> Listas No entanto, unha desvantaxe do ligadas

84
00:03:31,600 --> 00:03:33,370
é que, ao contrario dunha matriz estática,

85
00:03:33,370 --> 00:03:36,690
o ordenador non pode simplemente saltar para o medio da lista.

86
00:03:38,040 --> 00:03:40,780
Dende que o ordenador ten que visitar cada nó na lista ligada

87
00:03:40,780 --> 00:03:42,330
para chegar ó seguinte,

88
00:03:42,330 --> 00:03:44,770
que vai levar máis tempo para atopar un nodo específico

89
00:03:44,770 --> 00:03:46,400
do que sería nun array.

90
00:03:46,400 --> 00:03:48,660
Para percorrer a lista enteira leva un tempo proporcional

91
00:03:48,660 --> 00:03:50,580
a lonxitude da lista,

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

93
00:03:54,630 --> 00:03:56,510
En media, alcanzando calquera nodo

94
00:03:56,510 --> 00:03:58,800
tamén leva un tempo proporcional a n.

95
00:03:58,800 --> 00:04:00,700
>> Agora, imos realmente escribir un código

96
00:04:00,700 --> 00:04:02,000
que traballa con listas ligadas.

97
00:04:02,000 --> 00:04:04,220
Imos dicir que queremos unha lista ligada de enteiros.

98
00:04:04,220 --> 00:04:06,140
Podemos representar un nó na nosa lista de novo

99
00:04:06,140 --> 00:04:08,340
como unha estrutura con dous campos,

100
00:04:08,340 --> 00:04:10,750
un valor enteiro chamado 'Val'

101
00:04:10,750 --> 00:04:13,490
e un punteiro próximo ao seguinte nodo da lista.

102
00:04:13,490 --> 00:04:15,660
Ben, parece bastante simple.

103
00:04:15,660 --> 00:04:17,220
>> Imos dicir que queremos escribir unha función

104
00:04:17,220 --> 00:04:19,329
que percorre a lista e imprime o

105
00:04:19,329 --> 00:04:22,150
valor almacenado no último nó da lista.

106
00:04:22,150 --> 00:04:24,850
Ben, iso significa que temos que percorrer todos os nodos da lista

107
00:04:24,850 --> 00:04:27,310
para atopar a última, pero a condición de que non está engadindo

108
00:04:27,310 --> 00:04:29,250
ou borrar nada, non queremos cambiar

109
00:04:29,250 --> 00:04:32,210
a estructura interna dos punteiros seguintes na lista.

110
00:04:32,210 --> 00:04:34,790
>> Entón, imos ter un punteiro especificamente para paso

111
00:04:34,790 --> 00:04:36,940
que chamaremos de "rastreador".

112
00:04:36,940 --> 00:04:38,870
Vai rastexaren a través de todos os elementos da lista

113
00:04:38,870 --> 00:04:41,190
seguindo a cadea de punteiros próximos.

114
00:04:41,190 --> 00:04:43,750
Todo o que temos almacenado é un punteiro para o apartado 1,

115
00:04:43,750 --> 00:04:45,730
ou "cabeza" da lista.

116
00:04:45,730 --> 00:04:47,370
Puntos de cabeza para o apartado 1.

117
00:04:47,370 --> 00:04:49,120
É o tipo de punteiro a nó.

118
00:04:49,120 --> 00:04:51,280
>> Para obter o apartado 1 real na lista,

119
00:04:51,280 --> 00:04:53,250
temos que dereference ese punteiro,

120
00:04:53,250 --> 00:04:55,100
pero antes de que poidamos cancelar a referencia de que é preciso comprobar

121
00:04:55,100 --> 00:04:57,180
o punteiro é nulo primeiro.

122
00:04:57,180 --> 00:04:59,190
Se é nulo, a lista está baleira,

123
00:04:59,190 --> 00:05:01,320
e debemos imprimir unha mensaxe que, porque a lista é baleira,

124
00:05:01,320 --> 00:05:03,250
non hai último nodo.

125
00:05:03,250 --> 00:05:05,190
Pero, imos dicir que a lista non é baleira.

126
00:05:05,190 --> 00:05:08,340
Se non é, entón debemos rastrexar toda a lista

127
00:05:08,340 --> 00:05:10,440
ata chegar ao último nodo da lista,

128
00:05:10,440 --> 00:05:13,030
e como podemos saber se nós estamos mirando para o último nó na lista?

129
00:05:13,670 --> 00:05:16,660
>> Ben, se punteiro próxima dun nodo é nulo,

130
00:05:16,660 --> 00:05:18,320
sabemos que estamos no final

131
00:05:18,320 --> 00:05:22,390
desde o último punteiro seguinte tería ningún no seguinte na lista para apuntar.

132
00:05:22,390 --> 00:05:26,590
É unha boa práctica para manter sempre punteiro preto do no pasado inicializar como nulo

133
00:05:26,590 --> 00:05:30,800
ter unha propiedade estandarizada que nos alerta cando chegamos ao fin da lista.

134
00:05:30,800 --> 00:05:33,510
>> Entón, se rastreador → seguinte é nulo,

135
00:05:34,120 --> 00:05:38,270
Lembre que a sintaxe frecha é un atallo para dereferencing

136
00:05:38,270 --> 00:05:40,010
un punteiro para unha estrutura, a continuación, acceder

137
00:05:40,010 --> 00:05:42,510
seu próximo campo equivalente ao incómodo:

138
00:05:42,510 --> 00:05:48,750
(* Rexistro). Seguinte.

139
00:05:49,820 --> 00:05:51,260
Unha vez que teñamos atopado o último nó,

140
00:05:51,260 --> 00:05:53,830
queremos imprimir rastreador → val,

141
00:05:53,830 --> 00:05:55,000
o valor do nodo actual

142
00:05:55,000 --> 00:05:57,130
que sabemos que é a última.

143
00:05:57,130 --> 00:05:59,740
En caso contrario, se non estamos aínda no último nodo na lista,

144
00:05:59,740 --> 00:06:02,340
temos que seguir adiante para o próximo nó na lista

145
00:06:02,340 --> 00:06:04,750
e comprobar que este é o último.

146
00:06:04,750 --> 00:06:07,010
Para iso, basta con facer o noso punteiro rastreador

147
00:06:07,010 --> 00:06:09,840
para apuntar para o próximo valor do nodo actual,

148
00:06:09,840 --> 00:06:11,680
é dicir, o no seguinte na lista.

149
00:06:11,680 --> 00:06:13,030
Isto faise axustar

150
00:06:13,030 --> 00:06:15,280
rastreador = rastreador → seguinte.

151
00:06:16,050 --> 00:06:18,960
A continuación, repetimos este proceso, con un lazo, por exemplo,

152
00:06:18,960 --> 00:06:20,960
ata atopar o último nodo.

153
00:06:20,960 --> 00:06:23,150
Así, por exemplo, se rastreador estaba apuntando á cabeza,

154
00:06:24,050 --> 00:06:27,710
imos definir rastreador para apuntar para rastreador → seguinte,

155
00:06:27,710 --> 00:06:30,960
que é o mesmo que o seguinte campo da alínea 1.

156
00:06:30,960 --> 00:06:33,620
Entón, agora o noso rastreador está a apuntar cara o apartado 2,

157
00:06:33,620 --> 00:06:35,480
e, de novo, repetir este con un ciclo,

158
00:06:37,220 --> 00:06:40,610
ata que teñamos atopado o último nó, isto é,

159
00:06:40,610 --> 00:06:43,640
onde punteiro preto do nodo está a apuntar cara null.

160
00:06:43,640 --> 00:06:45,070
E aí temos que,

161
00:06:45,070 --> 00:06:47,620
atopamos o último nó na lista, e para imprimir o seu valor,

162
00:06:47,620 --> 00:06:50,800
é só usar rastreador → val.

163
00:06:50,800 --> 00:06:53,130
>> O desprazamento non é tan malo, pero o que sobre a inserción?

164
00:06:53,130 --> 00:06:56,290
Imos dicir que queremos inserir un enteiro na posición 4

165
00:06:56,290 --> 00:06:58,040
nunha lista de enteiros.

166
00:06:58,040 --> 00:07:01,280
Que se atopa entre os nodos de corrente 3 e 4.

167
00:07:01,280 --> 00:07:03,760
Unha vez máis, temos que percorrer a lista só para

168
00:07:03,760 --> 00:07:06,520
chegar ao elemento terceiro, aquel que está inserindo despois.

169
00:07:06,520 --> 00:07:09,300
Entón, creamos un punteiro rastreador de novo para percorrer a lista,

170
00:07:09,300 --> 00:07:11,400
comprobar que o noso punteiro cabeza é nulo,

171
00:07:11,400 --> 00:07:14,810
e se non é, apunta noso punteiro rastreador no nó de cabeza.

172
00:07:16,880 --> 00:07:18,060
Entón, estamos no primeiro elemento.

173
00:07:18,060 --> 00:07:21,020
Temos que ir para adiante dous elementos máis antes de que poidamos introducir,

174
00:07:21,020 --> 00:07:23,390
polo que podemos usar un loop

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

176
00:07:26,430 --> 00:07:28,590
e en cada iteração do loop,

177
00:07:28,590 --> 00:07:31,540
avanzar noso punteiro rastreador fronte por un nodo

178
00:07:31,540 --> 00:07:34,570
comprobando o campo preto do nodo actual é nulo,

179
00:07:34,570 --> 00:07:37,550
e se non é, mover noso punteiro rastreador para o próximo nodo

180
00:07:37,550 --> 00:07:41,810
definíndose o igual ao punteiro preto do nodo actual.

181
00:07:41,810 --> 00:07:45,210
Así, desde que o noso circuíto para facelo, di

182
00:07:45,210 --> 00:07:47,550
dúas veces,

183
00:07:49,610 --> 00:07:51,190
chegamos ao apartado 3,

184
00:07:51,190 --> 00:07:53,110
e unha vez que o noso punteiro rastreador alcanzou o nó despois

185
00:07:53,110 --> 00:07:55,270
que queremos introducir o noso enteiro novo,

186
00:07:55,270 --> 00:07:57,050
como é que nós realmente a inserción?

187
00:07:57,050 --> 00:07:59,440
>> Ben, o noso novo enteiro debe ser inserida na lista

188
00:07:59,440 --> 00:08:01,250
como parte da súa estrutura propio no,

189
00:08:01,250 --> 00:08:03,140
unha vez que esta é realmente unha secuencia de nós.

190
00:08:03,140 --> 00:08:05,690
Entón, imos facer un novo punteiro para o nodo

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

192
00:08:08,910 --> 00:08:11,800
e configure-lo para apuntar para a memoria que agora reservar

193
00:08:11,800 --> 00:08:14,270
sobre a pila para o propio nodo,

194
00:08:14,270 --> 00:08:16,000
ea cantidade de memoria que necesitamos reservar?

195
00:08:16,000 --> 00:08:18,250
Así, o tamaño dun nodo,

196
00:08:20,450 --> 00:08:23,410
e queremos establecer o seu campo val para o número enteiro que desexa inserir.

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

198
00:08:25,590 --> 00:08:27,710
Agora, o nodo contén o seu valor enteiro.

199
00:08:27,710 --> 00:08:30,650
É tamén unha boa práctica para iniciar seguinte campo novo nodo

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

201
00:08:33,690 --> 00:08:35,080
pero e agora?

202
00:08:35,080 --> 00:08:37,179
>> Temos que cambiar a estrutura interna da lista

203
00:08:37,179 --> 00:08:40,409
e os punteiros próximos contida existente da lista

204
00:08:40,409 --> 00:08:42,950
Nós 3 e 4.

205
00:08:42,950 --> 00:08:46,560
Unha vez que os punteiros próximos determinar a orde da lista,

206
00:08:46,560 --> 00:08:48,650
E xa que estamos introducindo o noso novo no

207
00:08:48,650 --> 00:08:50,510
a dereita no medio da lista,

208
00:08:50,510 --> 00:08:52,010
pode ser un pouco complicado.

209
00:08:52,010 --> 00:08:54,250
Isto porque, lembre, o noso ordenador

210
00:08:54,250 --> 00:08:56,250
só sabe a localización de nós na lista

211
00:08:56,250 --> 00:09:00,400
por mor dos punteiros próximos almacenados nos nos anteriores.

212
00:09:00,400 --> 00:09:03,940
Entón, se algunha vez perdeu a noción de calquera destes lugares,

213
00:09:03,940 --> 00:09:06,860
dicir cambiando un dos punteiros próximos na nosa lista,

214
00:09:06,860 --> 00:09:09,880
por exemplo, dicir que cambiou

215
00:09:09,880 --> 00:09:12,920
campo seguinte o apartado 3 é

216
00:09:12,920 --> 00:09:15,610
para apuntar a algún nó aquí.

217
00:09:15,610 --> 00:09:17,920
Nós estariamos fóra de sorte, porque non faría

218
00:09:17,920 --> 00:09:20,940
Ten algunha idea de onde atopar o resto da lista,

219
00:09:20,940 --> 00:09:23,070
e iso é, obviamente, moi malo.

220
00:09:23,070 --> 00:09:25,080
Entón, nós temos que ter moito coidado sobre a orde

221
00:09:25,080 --> 00:09:28,360
en que manipular os punteiros próximas durante a inserción.

222
00:09:28,360 --> 00:09:30,540
>> Entón, para simplificar, imos dicir que

223
00:09:30,540 --> 00:09:32,220
nosos primeiros catro nós

224
00:09:32,220 --> 00:09:36,200
son denominados A, B, C, e D, as frechas que representan a cadea de punteiros

225
00:09:36,200 --> 00:09:38,070
que conectan os nodos.

226
00:09:38,070 --> 00:09:40,050
Entón, necesitamos introducir noso novo nodo

227
00:09:40,050 --> 00:09:42,070
entre os nós C e D.

228
00:09:42,070 --> 00:09:45,060
É fundamental facelo na orde correcta, e eu vou amosar-lle por que.

229
00:09:45,060 --> 00:09:47,500
>> Imos ollar para a forma incorrecta de facelo primeiro.

230
00:09:47,500 --> 00:09:49,490
Ola, sabemos que o novo nó ten que vir despois C,

231
00:09:49,490 --> 00:09:51,910
entón imos definir punteiro preto do C

232
00:09:51,910 --> 00:09:54,700
para apuntar para new_node.

233
00:09:56,530 --> 00:09:59,180
Todo ben, parece todo ben, só temos que rematar agora por

234
00:09:59,180 --> 00:10:01,580
facendo punto o novo nó do punteiro ao lado D,

235
00:10:01,580 --> 00:10:03,250
pero espera, como podemos facer iso?

236
00:10:03,250 --> 00:10:05,170
O único que podería dicir onde era D,

237
00:10:05,170 --> 00:10:07,630
o punteiro próximo foi previamente almacenado en C,

238
00:10:07,630 --> 00:10:09,870
pero nós só reescreveu o punteiro

239
00:10:09,870 --> 00:10:11,170
para apuntar para o novo nodo,

240
00:10:11,170 --> 00:10:14,230
así xa non temos ningún pista onde D é na memoria,

241
00:10:14,230 --> 00:10:17,020
e nós perdemos o resto da lista.

242
00:10:17,020 --> 00:10:19,000
Non é bo en todo.

243
00:10:19,000 --> 00:10:21,090
>> Entón, como imos facelo certo?

244
00:10:22,360 --> 00:10:25,090
En primeiro lugar, apuntar punteiro seguinte, o novo nó no D.

245
00:10:26,170 --> 00:10:28,990
Agora, os punteiros tanto o novo nó e C do próximo

246
00:10:28,990 --> 00:10:30,660
están apuntando para o mesmo nodo, D,

247
00:10:30,660 --> 00:10:32,290
pero iso é bo.

248
00:10:32,290 --> 00:10:35,680
Agora podemos apuntar punteiro próximo ao C o novo nodo.

249
00:10:37,450 --> 00:10:39,670
Entón, nós fixemos iso sen perder os datos.

250
00:10:39,670 --> 00:10:42,280
No código, C é o nó actual

251
00:10:42,280 --> 00:10:45,540
que a travesía punteiro rastreador está a apuntar,

252
00:10:45,540 --> 00:10:50,400
e D é representada polo nodo apuntado polo campo seguinte do nodo actual,

253
00:10:50,400 --> 00:10:52,600
ou rastreador → seguinte.

254
00:10:52,600 --> 00:10:55,460
Entón, primeiro definir punteiro seguinte, o novo nodo

255
00:10:55,460 --> 00:10:57,370
para apuntar para rastreador → seguinte,

256
00:10:57,370 --> 00:11:00,880
do mesmo xeito que dixo punteiro próxima new_node debería

257
00:11:00,880 --> 00:11:02,780
apuntar D na figura.

258
00:11:02,780 --> 00:11:04,540
Entón, podemos definir punteiro preto do nodo actual

259
00:11:04,540 --> 00:11:06,330
para o noso novo nodo,

260
00:11:06,330 --> 00:11:10,980
así como nós tivo que esperar ata o punto C para new_node no deseño.

261
00:11:10,980 --> 00:11:12,250
Agora todo está en orde, e non perdemos

262
00:11:12,250 --> 00:11:14,490
o control de todos os datos, e fomos capaces de só

263
00:11:14,490 --> 00:11:16,200
furar o noso novo nó no medio da lista

264
00:11:16,200 --> 00:11:19,330
sen reconstruír a cousa toda ou incluso desprazando todos os elementos

265
00:11:19,330 --> 00:11:22,490
do xeito que tería que ter unha matriz de lonxitude fixa.

266
00:11:22,490 --> 00:11:26,020
>> Entón, listas ligadas son un básico, pero importante, estrutura de datos dinámica

267
00:11:26,020 --> 00:11:29,080
que teñen vantaxes e inconvenientes

268
00:11:29,080 --> 00:11:31,260
en comparación coas matrices e outras estruturas de datos,

269
00:11:31,260 --> 00:11:33,350
e, como é frecuentemente o caso en ciencia da computación,

270
00:11:33,350 --> 00:11:35,640
é importante saber cando usar cada ferramenta,

271
00:11:35,640 --> 00:11:37,960
para que poida elixir a ferramenta certa para o traballo correcto.

272
00:11:37,960 --> 00:11:40,060
>> Para máis práctica, proba escribir funcións para

273
00:11:40,060 --> 00:11:42,080
eliminar nós unha lista ligada -

274
00:11:42,080 --> 00:11:44,050
Lembre-se de ter coidado coa orde en que reorganizar

275
00:11:44,050 --> 00:11:47,430
os punteiros próximos para garantir que non perda unha peza da súa lista -

276
00:11:47,430 --> 00:11:50,200
ou unha función para contar os nós nunha lista ligada,

277
00:11:50,200 --> 00:11:53,280
ou un divertimento, para inverter a orde de todos os nós nunha lista ligada.

278
00:11:53,280 --> 00:11:56,090
>> O meu nome é Jackson Steinkamp, ​​este é CS50.