1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] En la programación, a menudo necesitamos para representar listas de valores,

2
00:00:10,050 --> 00:00:12,840
tales como los nombres de los estudiantes de una sección

3
00:00:12,840 --> 00:00:15,100
o sus puntuaciones en la última prueba.

4
00:00:15,100 --> 00:00:17,430
>> En el lenguaje C, declaró matrices pueden utilizarse

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

6
00:00:19,160 --> 00:00:21,200
Es fácil enumerar los elementos de una lista

7
00:00:21,200 --> 00:00:23,390
almacenados en una matriz, y si usted necesita para acceder a

8
00:00:23,390 --> 00:00:25,050
o modificar el elemento de la lista ith

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 puede hacer en un tiempo constante,

11
00:00:29,910 --> 00:00:31,660
pero las matrices tienen desventajas, también.

12
00:00:31,660 --> 00:00:33,850
>> Cuando les declaro, estamos obligados a decir

13
00:00:33,850 --> 00:00:35,900
desde el principio lo grandes que son,

14
00:00:35,900 --> 00:00:38,160
es decir, cuántos elementos se pueden almacenar

15
00:00:38,160 --> 00:00:40,780
y lo grande que estos elementos son, que se determina por su tipo.

16
00:00:40,780 --> 00:00:45,450
Por ejemplo, arreglo de int (10)

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

18
00:00:48,220 --> 00:00:50,200
que tienen el tamaño de un int.

19
00:00:50,200 --> 00:00:52,590
>> No podemos cambiar el tamaño de una matriz después de la declaración.

20
00:00:52,590 --> 00:00:55,290
Tenemos que hacer una nueva matriz si queremos almacenar más elementos.

21
00:00:55,290 --> 00:00:57,410
La razón de esta limitación que existe es que nuestro

22
00:00:57,410 --> 00:00:59,040
programa almacena toda la matriz

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

24
00:01:02,310 --> 00:01:04,500
Decir esto es el buffer donde se almacena en nuestra matriz.

25
00:01:04,500 --> 00:01:06,910
Puede haber otras variables

26
00:01:06,910 --> 00:01:08,310
situado justo al lado de la matriz

27
00:01:08,310 --> 00:01:10,060
en la memoria, por lo que no puede

28
00:01:10,060 --> 00:01:12,060
sólo que la matriz más grande.

29
00:01:12,060 --> 00:01:15,700
>> A veces nos gustaría que el comercio de la matriz rápida velocidad de acceso a datos

30
00:01:15,700 --> 00:01:17,650
para un poco más de flexibilidad.

31
00:01:17,650 --> 00:01:20,380
Introduzca la lista enlazada, otra estructura de datos básicos

32
00:01:20,380 --> 00:01:22,360
usted podría no ser tan familiarizados.

33
00:01:22,360 --> 00:01:24,200
En un nivel alto,

34
00:01:24,200 --> 00:01:26,840
una lista enlazada almacena los datos en una secuencia de nodos

35
00:01:26,840 --> 00:01:29,280
que están conectados entre sí con enlaces,

36
00:01:29,280 --> 00:01:31,760
por lo tanto "lista enlazada. 'el nombre

37
00:01:31,760 --> 00:01:33,840
Como veremos, esta diferencia en el diseño

38
00:01:33,840 --> 00:01:35,500
conduce a distintas ventajas y desventajas

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

40
00:01:37,000 --> 00:01:39,840
>> Aquí hay un código C para una lista muy simple enlazada de números enteros.

41
00:01:39,840 --> 00:01:42,190
Se puede ver que hemos representado a cada nodo

42
00:01:42,190 --> 00:01:45,520
en la lista como una estructura que contiene dos cosas,

43
00:01:45,520 --> 00:01:47,280
un entero para almacenar llamado 'val'

44
00:01:47,280 --> 00:01:50,460
y un enlace para el nodo siguiente en la lista

45
00:01:50,460 --> 00:01:52,990
que representamos como un puntero llamado 'next'.

46
00:01:54,120 --> 00:01:56,780
De esta manera, podemos seguir la lista entera

47
00:01:56,780 --> 00:01:58,790
con sólo un único puntero al nodo primero,

48
00:01:58,790 --> 00:02:01,270
y luego podemos seguir los siguientes consejos

49
00:02:01,270 --> 00:02:03,130
para el segundo nodo,

50
00:02:03,130 --> 00:02:05,280
al nodo tercero,

51
00:02:05,280 --> 00:02:07,000
para el cuarto nodo,

52
00:02:07,000 --> 00:02:09,889
y así sucesivamente, hasta llegar a la final de la lista.

53
00:02:10,520 --> 00:02:12,210
>> Usted puede ser capaz de ver una ventaja que esto tiene

54
00:02:12,210 --> 00:02:14,490
sobre la estructura matriz estática - con una lista enlazada,

55
00:02:14,490 --> 00:02:16,450
no necesitamos una gran parte de la memoria por completo.

56
00:02:17,400 --> 00:02:20,530
El nodo 1 de la lista podría vivir en este lugar en la memoria,

57
00:02:20,530 --> 00:02:23,160
y el segundo nodo podría ser todo el camino hasta aquí.

58
00:02:23,160 --> 00:02:25,780
Podemos llegar a todos los nodos no importa donde en la memoria son,

59
00:02:25,780 --> 00:02:28,890
porque a partir de la primera nodo, el puntero siguiente de cada nodo

60
00:02:28,890 --> 00:02:31,700
nos dice exactamente dónde ir después.

61
00:02:31,700 --> 00:02:33,670
>> Además, no tienes que decir por adelantado

62
00:02:33,670 --> 00:02:36,740
lo grande que una lista enlazada será el camino que hacemos con arrays estáticos,

63
00:02:36,740 --> 00:02:39,060
ya que podemos seguir añadiendo nodos a una lista

64
00:02:39,060 --> 00:02:42,600
siempre y cuando no hay espacio en algún lugar de la memoria de los nuevos nodos.

65
00:02:42,600 --> 00:02:45,370
Por lo tanto, las listas enlazadas son fáciles de cambiar el tamaño de forma dinámica.

66
00:02:45,370 --> 00:02:47,950
Digamos, más tarde en el programa tenemos que añadir más nodos

67
00:02:47,950 --> 00:02:49,350
a nuestra lista.

68
00:02:49,350 --> 00:02:51,480
Para insertar un nuevo nodo en la lista sobre la marcha,

69
00:02:51,480 --> 00:02:53,740
todo lo que tenemos que hacer es asignar memoria para ese nodo,

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

71
00:02:55,630 --> 00:02:59,070
y luego colocarlo donde queramos mediante el ajuste de los indicadores apropiados.

72
00:02:59,070 --> 00:03:02,310
>> Por ejemplo, si quisiéramos poner un nodo en el medio

73
00:03:02,310 --> 00:03:04,020
los nodos 2 y 3 de la lista,

74
00:03:04,020 --> 00:03:06,800
 no tendríamos que mover los nodos segundo o tercero en absoluto.

75
00:03:06,800 --> 00:03:09,190
Digamos que vas a insertar este nodo rojo.

76
00:03:09,190 --> 00:03:12,890
Todo lo que tendría que hacer es configurar puntero siguiente del nuevo nodo

77
00:03:12,890 --> 00:03:14,870
para que apunte al nodo tercera

78
00:03:14,870 --> 00:03:18,580
y luego volver a colocar el puntero siguiente nodo de segundo

79
00:03:18,580 --> 00:03:20,980
para que apunte a nuestro nuevo nodo.

80
00:03:22,340 --> 00:03:24,370
Por lo tanto, podemos cambiar el tamaño de nuestras listas sobre la marcha

81
00:03:24,370 --> 00:03:26,090
ya que nuestro equipo no depende de la indexación,

82
00:03:26,090 --> 00:03:28,990
sino más bien en vincular el uso de punteros para almacenarlos.

83
00:03:29,120 --> 00:03:31,600
>> Listas Sin embargo, una desventaja de vinculados

84
00:03:31,600 --> 00:03:33,370
es que, a diferencia de una matriz estática,

85
00:03:33,370 --> 00:03:36,690
el ordenador no sólo puede saltar a la mitad de la lista.

86
00:03:38,040 --> 00:03:40,780
Dado que el equipo tiene que visitar cada nodo en la lista enlazada

87
00:03:40,780 --> 00:03:42,330
para llegar a la siguiente,

88
00:03:42,330 --> 00:03:44,770
que va a tomar más tiempo para encontrar un nodo particular

89
00:03:44,770 --> 00:03:46,400
lo que lo haría en una matriz.

90
00:03:46,400 --> 00:03:48,660
Para recorrer toda la lista toma tiempo proporcional

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

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

93
00:03:54,630 --> 00:03:56,510
En promedio, alcanzando cualquier nodo

94
00:03:56,510 --> 00:03:58,800
También se necesita tiempo proporcional a n.

95
00:03:58,800 --> 00:04:00,700
>> Ahora, vamos a realmente escribir código

96
00:04:00,700 --> 00:04:02,000
que trabaja con listas enlazadas.

97
00:04:02,000 --> 00:04:04,220
Digamos que queremos una lista enlazada de enteros.

98
00:04:04,220 --> 00:04:06,140
Podemos representar un nodo en la lista de nuevo

99
00:04:06,140 --> 00:04:08,340
como una estructura con dos campos,

100
00:04:08,340 --> 00:04:10,750
un valor entero llamado 'val'

101
00:04:10,750 --> 00:04:13,490
y un puntero próximo al siguiente nodo de la lista.

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

103
00:04:15,660 --> 00:04:17,220
>> Supongamos que queremos escribir una función

104
00:04:17,220 --> 00:04:19,329
que recorre la lista e imprime el

105
00:04:19,329 --> 00:04:22,150
valor almacenado en el último nodo de la lista.

106
00:04:22,150 --> 00:04:24,850
Bueno, eso significa que tendremos que recorrer todos los nodos de la lista

107
00:04:24,850 --> 00:04:27,310
para encontrar la última, pero ya no estamos añadiendo

108
00:04:27,310 --> 00:04:29,250
o borrar nada, no queremos cambiar

109
00:04:29,250 --> 00:04:32,210
la estructura interna de los punteros siguientes en la lista.

110
00:04:32,210 --> 00:04:34,790
>> Por lo tanto, vamos a necesitar un puntero específicamente para traversal

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

112
00:04:36,940 --> 00:04:38,870
Se arrastran a través de todos los elementos de la lista

113
00:04:38,870 --> 00:04:41,190
siguiendo la cadena de punteros próximos.

114
00:04:41,190 --> 00:04:43,750
Todos hemos almacenado es un puntero al nodo primero,

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

116
00:04:45,730 --> 00:04:47,370
Puntos de la cabeza a la primera nodo.

117
00:04:47,370 --> 00:04:49,120
Es de tipo puntero a nodo.

118
00:04:49,120 --> 00:04:51,280
>> Para obtener la actual primera nodo en la lista,

119
00:04:51,280 --> 00:04:53,250
tenemos que eliminar la referencia este indicador,

120
00:04:53,250 --> 00:04:55,100
pero antes de que podamos deferenciarlo, tenemos que comprobar

121
00:04:55,100 --> 00:04:57,180
si el puntero es nulo en primer lugar.

122
00:04:57,180 --> 00:04:59,190
Si es nulo, la lista está vacía,

123
00:04:59,190 --> 00:05:01,320
y debemos imprimir un mensaje que, debido a que la lista está vacía,

124
00:05:01,320 --> 00:05:03,250
no hay último nodo.

125
00:05:03,250 --> 00:05:05,190
Pero, supongamos que la lista no está vacía.

126
00:05:05,190 --> 00:05:08,340
Si no es así, entonces tenemos que gatear por toda la lista

127
00:05:08,340 --> 00:05:10,440
hasta llegar al último nodo de la lista,

128
00:05:10,440 --> 00:05:13,030
y ¿cómo podemos saber si estamos ante el último nodo en la lista?

129
00:05:13,670 --> 00:05:16,660
>> Bueno, si el puntero siguiente de un nodo es nulo,

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

131
00:05:18,320 --> 00:05:22,390
desde el siguiente puntero última no tendría ningún nodo siguiente en la lista para apuntar.

132
00:05:22,390 --> 00:05:26,590
Es una buena práctica para mantener siempre puntero siguiente del último nodo de inicializan a null

133
00:05:26,590 --> 00:05:30,800
tener una propiedad estándar que nos avisa cuando hemos llegado al final de la lista.

134
00:05:30,800 --> 00:05:33,510
>> Por lo tanto, si crawler → siguiente es nulo,

135
00:05:34,120 --> 00:05:38,270
recordar que la sintaxis de flecha es un acceso directo para eliminar la referencia

136
00:05:38,270 --> 00:05:40,010
un puntero a una estructura, a continuación, acceder a

137
00:05:40,010 --> 00:05:42,510
su siguiente campo equivalente al torpe:

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

139
00:05:49,820 --> 00:05:51,260
Una vez que hayas encontrado el último nodo,

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

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

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

143
00:05:57,130 --> 00:05:59,740
De lo contrario, si no estamos todavía en el último nodo de la lista,

144
00:05:59,740 --> 00:06:02,340
tenemos que pasar a la siguiente nodo en la lista

145
00:06:02,340 --> 00:06:04,750
y comprobar si ese es el último.

146
00:06:04,750 --> 00:06:07,010
Para ello, se acaba de establecer nuestro puntero sobre orugas

147
00:06:07,010 --> 00:06:09,840
para apuntar al siguiente valor del nodo actual,

148
00:06:09,840 --> 00:06:11,680
es decir, el nodo siguiente en la lista.

149
00:06:11,680 --> 00:06:13,030
Esto se hace mediante el establecimiento

150
00:06:13,030 --> 00:06:15,280
crawler = crawler → siguiente.

151
00:06:16,050 --> 00:06:18,960
Luego repetimos este proceso, con un lazo por ejemplo,

152
00:06:18,960 --> 00:06:20,960
hasta encontrar el último nodo.

153
00:06:20,960 --> 00:06:23,150
Así, por ejemplo, si rastreador estaba apuntando a la cabeza,

154
00:06:24,050 --> 00:06:27,710
nos propusimos rastreador para que apunte a orugas → siguiente,

155
00:06:27,710 --> 00:06:30,960
que es el mismo que el campo próximo de la primera nodo.

156
00:06:30,960 --> 00:06:33,620
Así que, ahora que nuestro rastreador está apuntando al nodo 2,

157
00:06:33,620 --> 00:06:35,480
y, de nuevo, se repite esto con un bucle,

158
00:06:37,220 --> 00:06:40,610
hasta que hayamos encontrado el último nodo, es decir,

159
00:06:40,610 --> 00:06:43,640
donde puntero siguiente del nodo apunta a null.

160
00:06:43,640 --> 00:06:45,070
Y ahí lo tenemos,

161
00:06:45,070 --> 00:06:47,620
hemos encontrado el último nodo de la lista, y la impresión de su valor,

162
00:06:47,620 --> 00:06:50,800
sólo tiene que utilizar crawler → val.

163
00:06:50,800 --> 00:06:53,130
>> Atravesando no es tan malo, pero ¿qué pasa con la inserción?

164
00:06:53,130 --> 00:06:56,290
Digamos que queremos insertar un número entero en la 4 ª posición

165
00:06:56,290 --> 00:06:58,040
en una lista de números enteros.

166
00:06:58,040 --> 00:07:01,280
Que está entre los nodos actuales tercero y cuarto.

167
00:07:01,280 --> 00:07:03,760
Una vez más, tenemos que recorrer la lista sólo para

168
00:07:03,760 --> 00:07:06,520
llegar a la tercera parte, la que estamos insertando después.

169
00:07:06,520 --> 00:07:09,300
Así, creamos un puntero rastreador de nuevo para recorrer la lista,

170
00:07:09,300 --> 00:07:11,400
comprobar si nuestra cabeza puntero es nulo,

171
00:07:11,400 --> 00:07:14,810
y si no lo es, apuntar con el puntero sobre orugas en el nodo principal.

172
00:07:16,880 --> 00:07:18,060
Por lo tanto, estamos en el elemento primero.

173
00:07:18,060 --> 00:07:21,020
Tenemos que ir hacia adelante 2 elementos más antes de que podamos insertar,

174
00:07:21,020 --> 00:07:23,390
por lo que podemos utilizar 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
y en cada iteración del bucle,

177
00:07:28,590 --> 00:07:31,540
avanzar en el puntero sobre orugas presentadas por un nodo

178
00:07:31,540 --> 00:07:34,570
comprobando si el campo próximo del nodo actual es nula,

179
00:07:34,570 --> 00:07:37,550
y si no es así, mover nuestro rastreador puntero al siguiente nodo

180
00:07:37,550 --> 00:07:41,810
fijándolo igual al siguiente puntero del nodo actual.

181
00:07:41,810 --> 00:07:45,210
Por lo tanto, desde nuestro bucle para hacer eso, dice

182
00:07:45,210 --> 00:07:47,550
dos veces,

183
00:07:49,610 --> 00:07:51,190
hemos llegado al nodo 3,

184
00:07:51,190 --> 00:07:53,110
y una vez que nuestro puntero rastreador ha alcanzado el nodo después de

185
00:07:53,110 --> 00:07:55,270
que queremos insertar nuestro nuevo entero,

186
00:07:55,270 --> 00:07:57,050
¿cómo es en realidad la inserción?

187
00:07:57,050 --> 00:07:59,440
>> Pues bien, nuestro nuevo entero tiene que ser insertado en la lista

188
00:07:59,440 --> 00:08:01,250
como parte de su propia estructura de nodo,

189
00:08:01,250 --> 00:08:03,140
ya que esto es realmente una secuencia de nodos.

190
00:08:03,140 --> 00:08:05,690
Por lo tanto, vamos a hacer un nuevo puntero al nodo

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

192
00:08:08,910 --> 00:08:11,800
y configurarlo para que apunte a la memoria que ahora asignar

193
00:08:11,800 --> 00:08:14,270
en el montón para el nodo en sí,

194
00:08:14,270 --> 00:08:16,000
y la cantidad de memoria tenemos que asignar?

195
00:08:16,000 --> 00:08:18,250
Pues bien, el tamaño de un nodo,

196
00:08:20,450 --> 00:08:23,410
y queremos establecer su campo val al entero que queremos insertar.

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

198
00:08:25,590 --> 00:08:27,710
Ahora, el nodo contiene nuestro valor entero.

199
00:08:27,710 --> 00:08:30,650
También es una buena práctica para inicializar campo próximo del nuevo nodo

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

201
00:08:33,690 --> 00:08:35,080
pero ¿ahora qué?

202
00:08:35,080 --> 00:08:37,179
>> Hay que cambiar la estructura interna de la lista

203
00:08:37,179 --> 00:08:40,409
y los indicadores contenidos en los siguientes de la lista

204
00:08:40,409 --> 00:08:42,950
Los nodos 3 y 4.

205
00:08:42,950 --> 00:08:46,560
Dado que los punteros próximos determinar el orden de la lista,

206
00:08:46,560 --> 00:08:48,650
y ya que estamos introduciendo nuestro nuevo nodo

207
00:08:48,650 --> 00:08:50,510
a la derecha en el medio de la lista,

208
00:08:50,510 --> 00:08:52,010
que puede ser un poco complicado.

209
00:08:52,010 --> 00:08:54,250
Esto es porque, recuerde, nuestro equipo

210
00:08:54,250 --> 00:08:56,250
sólo conoce la ubicación de los nodos en la lista

211
00:08:56,250 --> 00:09:00,400
porque de los punteros próximos almacenados en los nodos anteriores.

212
00:09:00,400 --> 00:09:03,940
Por lo tanto, si alguna vez perdido el rastro de ninguno de estos lugares,

213
00:09:03,940 --> 00:09:06,860
dicen que al cambiar uno de los punteros siguientes en la lista,

214
00:09:06,860 --> 00:09:09,880
Por ejemplo, digamos que cambiamos

215
00:09:09,880 --> 00:09:12,920
campo siguiente nodo de la tercera de

216
00:09:12,920 --> 00:09:15,610
para que apunte a algún nodo por aquí.

217
00:09:15,610 --> 00:09:17,920
Nos gustaría estar fuera de suerte, ya que no lo haría

218
00:09:17,920 --> 00:09:20,940
Tiene alguna idea de dónde encontrar el resto de la lista,

219
00:09:20,940 --> 00:09:23,070
y eso es, obviamente, muy mal.

220
00:09:23,070 --> 00:09:25,080
Por lo tanto, tenemos que tener mucho cuidado con el fin de

221
00:09:25,080 --> 00:09:28,360
en el que manipulamos nuestros punteros próximos durante la inserción.

222
00:09:28,360 --> 00:09:30,540
>> Así que, para simplificar esto, vamos a decir que

223
00:09:30,540 --> 00:09:32,220
nuestros primeros 4 nodos

224
00:09:32,220 --> 00:09:36,200
se denominan A, B, C, y D, con las flechas que representan la cadena de punteros

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

226
00:09:38,070 --> 00:09:40,050
Por lo tanto, tenemos que insertar nuestro nuevo nodo

227
00:09:40,050 --> 00:09:42,070
entre los nodos C y D.

228
00:09:42,070 --> 00:09:45,060
Es muy importante hacerlo en el orden correcto, y yo te mostraré por qué.

229
00:09:45,060 --> 00:09:47,500
>> Echemos un vistazo a la forma incorrecta de hacerlo en primer lugar.

230
00:09:47,500 --> 00:09:49,490
Hey, sabemos que el nuevo nodo tiene que venir a la derecha después de C,

231
00:09:49,490 --> 00:09:51,910
así que vamos a establecer el puntero próximo C

232
00:09:51,910 --> 00:09:54,700
para que apunte a new_node.

233
00:09:56,530 --> 00:09:59,180
De acuerdo, parece estar bien, sólo tenemos que terminar ahora por

234
00:09:59,180 --> 00:10:01,580
hacer punto del nuevo nodo puntero próximo a D,

235
00:10:01,580 --> 00:10:03,250
pero espera, ¿cómo podemos hacer esto?

236
00:10:03,250 --> 00:10:05,170
Lo único que nos puede decir donde D es,

237
00:10:05,170 --> 00:10:07,630
fue el siguiente puntero almacenado previamente en C,

238
00:10:07,630 --> 00:10:09,870
pero nos volvió a escribir ese puntero

239
00:10:09,870 --> 00:10:11,170
para que apunte al nuevo nodo,

240
00:10:11,170 --> 00:10:14,230
por lo que ya no tenemos ni idea de donde D es en la memoria,

241
00:10:14,230 --> 00:10:17,020
y hemos perdido el resto de la lista.

242
00:10:17,020 --> 00:10:19,000
No es bueno en absoluto.

243
00:10:19,000 --> 00:10:21,090
>> Así que, ¿cómo podemos hacer esto bien?

244
00:10:22,360 --> 00:10:25,090
En primer lugar, señalar puntero siguiente del nuevo nodo a D.

245
00:10:26,170 --> 00:10:28,990
Ahora, tanto el nuevo nodo y la de C próximos punteros

246
00:10:28,990 --> 00:10:30,660
apuntan hacia el mismo nodo, D,

247
00:10:30,660 --> 00:10:32,290
pero eso está bien.

248
00:10:32,290 --> 00:10:35,680
Ahora podemos señalar siguiente puntero de C en el nuevo nodo.

249
00:10:37,450 --> 00:10:39,670
Por lo tanto, hemos hecho esto sin perder ningún dato.

250
00:10:39,670 --> 00:10:42,280
En el código, C es el nodo actual

251
00:10:42,280 --> 00:10:45,540
que el recorrido puntero rastreador hace referencia,

252
00:10:45,540 --> 00:10:50,400
y D está representado por el nodo al que apunta el campo siguiente nodo actual,

253
00:10:50,400 --> 00:10:52,600
o rastreador → siguiente.

254
00:10:52,600 --> 00:10:55,460
Así, en primer lugar establecer el puntero siguiente del nuevo nodo

255
00:10:55,460 --> 00:10:57,370
para que apunte a orugas → siguiente,

256
00:10:57,370 --> 00:11:00,880
de la misma manera que dijimos puntero próximo new_node deben tener por

257
00:11:00,880 --> 00:11:02,780
apuntar a D en la ilustración.

258
00:11:02,780 --> 00:11:04,540
Entonces, podemos establecer el puntero siguiente del nodo actual

259
00:11:04,540 --> 00:11:06,330
a nuestro nuevo nodo,

260
00:11:06,330 --> 00:11:10,980
del mismo modo que tuvo que esperar al punto C new_node en el dibujo.

261
00:11:10,980 --> 00:11:12,250
Ahora todo está en orden, y no perdió

262
00:11:12,250 --> 00:11:14,490
realizar un seguimiento de los datos, y fuimos capaces de simplemente

263
00:11:14,490 --> 00:11:16,200
pegarse nuestro nuevo nodo en el medio de la lista

264
00:11:16,200 --> 00:11:19,330
sin reconstruir toda la cosa, o incluso cambiando los elementos

265
00:11:19,330 --> 00:11:22,490
la forma en que se han tenido que con una matriz de longitud fija.

266
00:11:22,490 --> 00:11:26,020
>> Por lo tanto, las listas enlazadas son un básico, pero importante, la estructura de datos dinámica

267
00:11:26,020 --> 00:11:29,080
que tienen ventajas y desventajas

268
00:11:29,080 --> 00:11:31,260
en comparación con las matrices y otras estructuras de datos,

269
00:11:31,260 --> 00:11:33,350
y como es a menudo el caso en informática,

270
00:11:33,350 --> 00:11:35,640
es importante saber cuando usar cada herramienta,

271
00:11:35,640 --> 00:11:37,960
para que pueda elegir la herramienta adecuada para el trabajo correcto.

272
00:11:37,960 --> 00:11:40,060
>> Si desea practicar más, intente escribir funciones para

273
00:11:40,060 --> 00:11:42,080
eliminar nodos de una lista enlazada -

274
00:11:42,080 --> 00:11:44,050
recuerde tener cuidado con el orden en el que se reorganizan

275
00:11:44,050 --> 00:11:47,430
los punteros siguientes para asegurarse de que no pierda una buena parte de su lista -

276
00:11:47,430 --> 00:11:50,200
o una función para contar los nodos en una lista enlazada,

277
00:11:50,200 --> 00:11:53,280
o una diversión, para invertir el orden de todos los nodos de una lista enlazada.

278
00:11:53,280 --> 00:11:56,090
>> Mi nombre es Jackson Steinkamp, ​​esto es CS50.