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

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, así que al
este punto en el curso,

4
00:00:08,560 --> 00:00:15,300
hemos cubierto muchos de los conceptos básicos de la C.
Sabemos mucho acerca de variables, matrices,

5
00:00:15,300 --> 00:00:17,610
punteros, todas esas cosas buenas.

6
00:00:17,610 --> 00:00:21,610
Esos son todo tipo de construido
para ver como los fundamentos,

7
00:00:21,610 --> 00:00:23,880
pero podemos hacer más, ¿no?

8
00:00:23,880 --> 00:00:27,930
Podemos combinar cosas
juntos en formas interesantes.

9
00:00:27,930 --> 00:00:31,010
>> Y así vamos a hacer eso, vamos a empezar
diversificarse de lo C nos da,

10
00:00:31,010 --> 00:00:35,270
y empezar a crear nuestros propios datos
estructuras que utilizan estos edificios

11
00:00:35,270 --> 00:00:40,590
bloques juntos para hacer algo
realmente valioso, útil.

12
00:00:40,590 --> 00:00:43,420
Una forma de hacerlo es
para hablar sobre las colecciones.

13
00:00:43,420 --> 00:00:48,360
Así que hasta ahora hemos tenido un tipo de datos
estructura para representar colecciones

14
00:00:48,360 --> 00:00:51,030
de recibir los valores, valores similares.

15
00:00:51,030 --> 00:00:52,350
Eso sería una matriz.

16
00:00:52,350 --> 00:00:57,020
Disponemos de colecciones de números enteros, o
colecciones de personajes y así sucesivamente.

17
00:00:57,020 --> 00:01:00,890
>> Estructuras también una especie de datos
estructura para la recopilación de información,

18
00:01:00,890 --> 00:01:03,220
pero no lo es para recoger como valores.

19
00:01:03,220 --> 00:01:08,090
Por lo general, se mezcla diferentes tipos de datos
juntos dentro de una sola caja.

20
00:01:08,090 --> 00:01:10,750
Pero no es en sí
utilizado para encadenar

21
00:01:10,750 --> 00:01:16,920
o conecte juntas similares
artículos, como una matriz.

22
00:01:16,920 --> 00:01:20,960
Las matrices son grandes para
elemento de mirar hacia arriba, pero el recuerdo

23
00:01:20,960 --> 00:01:24,262
que es muy difícil
para insertar en una matriz,

24
00:01:24,262 --> 00:01:26,470
a menos que estamos insertando en
el final de esa matriz.

25
00:01:26,470 --> 00:01:29,730
>> Y el mejor ejemplo que tiene
para eso es la ordenación por inserción.

26
00:01:29,730 --> 00:01:31,650
Si usted recuerda nuestro video
de ordenación por inserción,

27
00:01:31,650 --> 00:01:34,110
había una gran cantidad de
gastos involucrados en tener

28
00:01:34,110 --> 00:01:37,970
para recoger elementos, y desplazarlos
fuera del camino para adaptarse a algo

29
00:01:37,970 --> 00:01:41,290
en el centro de su matriz.

30
00:01:41,290 --> 00:01:44,690
Las matrices también sufren de otra
problema, que es la inflexibilidad.

31
00:01:44,690 --> 00:01:47,150
Cuando declaramos una matriz,
tenemos una oportunidad en él.

32
00:01:47,150 --> 00:01:49,790
Tenemos que decir, quiero
esta cantidad de elementos.

33
00:01:49,790 --> 00:01:51,940
Podría ser 100, podría
ser 1000, podría

34
00:01:51,940 --> 00:01:55,930
ser x, donde x es un número que el usuario
nos dio en el símbolo o en el comando

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

36
00:01:56,630 --> 00:01:59,905
>> Pero sólo tenemos una oportunidad por ella,
no llego a decir a continuación, oh, en realidad yo

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

38
00:02:04,360 --> 00:02:07,910
Demasiado tarde, ya hemos declarado la
matriz, y si queremos obtener 101 ó x

39
00:02:07,910 --> 00:02:12,050
más 20, tenemos que declarar
un conjunto completamente diferente,

40
00:02:12,050 --> 00:02:15,540
copiar todos los elementos de la matriz
terminado, y entonces tenemos suficiente.

41
00:02:15,540 --> 00:02:19,880
¿Y si nos equivocamos de nuevo, lo que
si en realidad necesitamos 102, o x más de 40 años,

42
00:02:19,880 --> 00:02:21,970
tenemos que hacer esto de nuevo.

43
00:02:21,970 --> 00:02:26,250
Así que son muy inflexibles
para cambiar el tamaño de nuestros datos,

44
00:02:26,250 --> 00:02:29,360
pero si combinamos a algunos
de los conceptos básicos que ya hemos

45
00:02:29,360 --> 00:02:33,230
aprendido acerca de los punteros y estructuras,
en particular, el uso de memoria dinámica

46
00:02:33,230 --> 00:02:36,180
asignación con malloc, que
puede poner estas piezas juntas

47
00:02:36,180 --> 00:02:40,960
para crear un un nuevo dato structure--
lista podríamos decir-- enlazada

48
00:02:40,960 --> 00:02:45,400
que nos permite crecer y
reducir una colección de valores

49
00:02:45,400 --> 00:02:48,800
y no vamos a tener ningún espacio perdido.

50
00:02:48,800 --> 00:02:53,320
>> Así que de nuevo, llamamos a esta idea,
esta noción, una lista enlazada.

51
00:02:53,320 --> 00:02:56,320
En particular, en este video estamos
hablando de lista enlazada,

52
00:02:56,320 --> 00:02:59,185
y luego otro video hablaremos
listas sobre doblemente enlazadas, que

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

54
00:03:01,560 --> 00:03:05,200
Sin embargo, una lista enlazada
se compone de nodos,

55
00:03:05,200 --> 00:03:08,559
nodos sólo ser un term-- abstracta
es sólo algo que estoy llamando

56
00:03:08,559 --> 00:03:10,350
eso es una especie de
estructura, básicamente, estoy?

57
00:03:10,350 --> 00:03:16,190
Sólo va a llamar a un node-- y esto
nodo tiene dos miembros, o dos campos.

58
00:03:16,190 --> 00:03:20,300
Tiene datos, por lo general una
número entero, un flotador carácter,

59
00:03:20,300 --> 00:03:23,790
o podría ser algún otro tipo de datos
que ha definido con un tipo def.

60
00:03:23,790 --> 00:03:29,290
Y contiene un puntero a
otro nodo del mismo tipo.

61
00:03:29,290 --> 00:03:34,710
>> Así que tenemos dos cosas en el interior de
este nodo, los datos y un puntero

62
00:03:34,710 --> 00:03:36,380
a otro nodo.

63
00:03:36,380 --> 00:03:39,370
Y si usted comienza a visualizar
esto, se puede pensar en ello

64
00:03:39,370 --> 00:03:42,280
como una cadena de nodos que
están conectados entre sí.

65
00:03:42,280 --> 00:03:45,070
Tenemos el primer nodo,
contiene datos, y un puntero

66
00:03:45,070 --> 00:03:49,110
al segundo nodo, que contiene
de datos, y un puntero a la tercera nodo.

67
00:03:49,110 --> 00:03:52,940
Y por eso lo llamamos un
lista enlazada, están unidos entre sí.

68
00:03:52,940 --> 00:03:56,070
>> ¿Qué hace este especial
estructura de nodos parece?

69
00:03:56,070 --> 00:04:01,120
Bueno, si usted recuerda de nuestro video en
la definición de tipos personalizados, con el tipo de definición,

70
00:04:01,120 --> 00:04:05,400
podemos definir un structure-- y
escriba definir una estructura como esta.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, y entonces estoy
utilizando el valor de la palabra aquí arbitrariamente

72
00:04:11,240 --> 00:04:13,891
para indicar cualquier tipo de datos realmente.

73
00:04:13,891 --> 00:04:16,890
Usted podría pasar un entero o flotante,
usted podría tener lo que quieras.

74
00:04:16,890 --> 00:04:19,389
No está restringido a solo
enteros, ni nada de eso.

75
00:04:19,389 --> 00:04:22,790
Así que el valor es sólo una arbitraria
tipo de datos, y luego un puntero

76
00:04:22,790 --> 00:04:26,310
a otro nodo del mismo tipo.

77
00:04:26,310 --> 00:04:29,690
>> Ahora, hay un poco de capturas
aquí con la definición de una estructura de

78
00:04:29,690 --> 00:04:33,030
cuando es una estructura auto referencial.

79
00:04:33,030 --> 00:04:35,340
Tengo que tener un temporal
nombrar por mi estructura.

80
00:04:35,340 --> 00:04:37,640
Al final del día I
claramente quieren llamarlo

81
00:04:37,640 --> 00:04:43,030
nodo sll, que es en última instancia, el nuevo
nombrar parte de mi tipo de definición,

82
00:04:43,030 --> 00:04:47,450
pero no puedo utilizar el nodo sll
en el medio de esto.

83
00:04:47,450 --> 00:04:51,430
La razón es que no lo he hecho
creado un nodo SLL tipo llamado

84
00:04:51,430 --> 00:04:55,200
hasta que llegué a este punto final aquí.

85
00:04:55,200 --> 00:04:59,720
Hasta ese momento, tengo que tener
otra manera de referirse a este tipo de datos.

86
00:04:59,720 --> 00:05:02,440
>> Y este es un auto
tipo de datos referencial.

87
00:05:02,440 --> 00:05:06,314
Es, es un tipo de datos de un
estructura que contiene un dato,

88
00:05:06,314 --> 00:05:08,480
y un puntero a otro
estructura del mismo tipo.

89
00:05:08,480 --> 00:05:11,750
Así que tengo que ser capaz de referirse a
este tipo de datos al menos temporalmente,

90
00:05:11,750 --> 00:05:14,910
por lo que le da un temporal
nombre del struct sllist

91
00:05:14,910 --> 00:05:18,540
me permite entonces digo que quiero un
puntero a otra estructura sllist,

92
00:05:18,540 --> 00:05:24,690
una estrella struct sllist, y luego
después de haber completado la definición,

93
00:05:24,690 --> 00:05:27,220
Ahora puedo llamar a este tipo de un nodo sll.

94
00:05:27,220 --> 00:05:30,520
>> Así que por eso se ve que hay
un nombre temporal aquí,

95
00:05:30,520 --> 00:05:31,879
sino un nombre permanente aquí.

96
00:05:31,879 --> 00:05:33,920
A veces es posible que vea
las definiciones de la estructura,

97
00:05:33,920 --> 00:05:36,570
por ejemplo, que no son
auto referencial, que

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

99
00:05:39,390 --> 00:05:43,040
Simplemente diría typedef struct,
abrir corchete y luego definirlo.

100
00:05:43,040 --> 00:05:45,620
Pero si usted es struct es auto
referencial, como ésta es,

101
00:05:45,620 --> 00:05:49,010
es necesario especificar un
nombre de tipo temporal.

102
00:05:49,010 --> 00:05:51,310
Pero en última instancia, ahora
que hemos hecho esto,

103
00:05:51,310 --> 00:05:53,620
acabamos de hacer referencia a
estos nodos, estas unidades,

104
00:05:53,620 --> 00:05:57,900
como nodos SLL propósitos
del resto de este video.

105
00:05:57,900 --> 00:06:00,900
>> Muy bien, así que sabemos cómo
crear un nodo de lista enlazada.

106
00:06:00,900 --> 00:06:03,240
Sabemos cómo definir
un nodo de lista enlazada.

107
00:06:03,240 --> 00:06:06,670
Ahora, si vamos a empezar
usarlas para recopilar información,

108
00:06:06,670 --> 00:06:10,360
hay un par de operaciones que
necesidad de entender y trabajar con ellos.

109
00:06:10,360 --> 00:06:12,860
Tenemos que saber cómo crear
una lista enlazada de la nada.

110
00:06:12,860 --> 00:06:14,901
Si no hay ninguna lista ya,
queremos empezar una.

111
00:06:14,901 --> 00:06:16,960
Así que tenemos que ser capaces de
para crear una lista enlazada,

112
00:06:16,960 --> 00:06:19,130
tenemos que probablemente buscar
a través de la lista de enlaces

113
00:06:19,130 --> 00:06:21,830
para encontrar un elemento que estamos buscando.

114
00:06:21,830 --> 00:06:24,430
Tenemos que ser capaces de insertar
nuevas cosas en la lista,

115
00:06:24,430 --> 00:06:25,930
queremos que nuestra lista para poder crecer.

116
00:06:25,930 --> 00:06:28,638
Y del mismo modo, queremos ser capaces
eliminar cosas de nuestra lista,

117
00:06:28,638 --> 00:06:30,250
queremos que nuestra lista para ser capaz de reducir el tamaño.

118
00:06:30,250 --> 00:06:32,160
Y al final de nuestra
programas, especialmente

119
00:06:32,160 --> 00:06:34,550
si usted recuerda que somos
asignación dinámica de memoria

120
00:06:34,550 --> 00:06:38,337
para construir estas listas normalmente,
queremos liberar a toda la que la memoria

121
00:06:38,337 --> 00:06:39,670
cuando hayamos terminado de trabajar con él.

122
00:06:39,670 --> 00:06:44,627
Y así tenemos que ser capaces de borrar una
toda lista enlazada en un fallo de la redada.

123
00:06:44,627 --> 00:06:46,460
Así que vamos a ir a través
algunas de estas operaciones

124
00:06:46,460 --> 00:06:51,192
y cómo podemos visualizarlos,
hablando en código pseudocódigo específicamente.

125
00:06:51,192 --> 00:06:53,150
Así que queremos crear un
lista enlazada, así que tal vez

126
00:06:53,150 --> 00:06:56,480
desee definir una función
con este prototipo.

127
00:06:56,480 --> 00:07:01,690
sll estrellas nodo, cree, y yo estoy pasando
en un argumento, algunos datos arbitrarios

128
00:07:01,690 --> 00:07:05,530
escriba de nuevo, de algún tipo de datos arbitrario.

129
00:07:05,530 --> 00:07:10,482
Pero estoy returning-- esta función debería
volverá a mí un puntero, a un solitario

130
00:07:10,482 --> 00:07:11,190
nodo de lista enlazada.

131
00:07:11,190 --> 00:07:14,050
Una vez más, estamos tratando de crear
una lista enlazada de la nada,

132
00:07:14,050 --> 00:07:17,900
así que necesito un puntero a
esa lista cuando he terminado.

133
00:07:17,900 --> 00:07:19,420
>> ¿Cuáles son los pasos a seguir aquí?

134
00:07:19,420 --> 00:07:20,960
Bueno, primero que estoy
vamos a hacer es dinámicamente

135
00:07:20,960 --> 00:07:22,550
asignar espacio para un nuevo nodo.

136
00:07:22,550 --> 00:07:26,689
Una vez más, estamos creando fuera de fina
aire, por lo que necesitamos el espacio malloc para ello.

137
00:07:26,689 --> 00:07:28,480
Y, por supuesto, de inmediato
después de que malloc,

138
00:07:28,480 --> 00:07:31,692
siempre comprobar para asegurarse de que nuestra
pointer-- no conseguimos volver nulo.

139
00:07:31,692 --> 00:07:33,650
Porque si tratamos de
deferencia un puntero nulo,

140
00:07:33,650 --> 00:07:36,190
vamos a sufrir un
violación de segmento y no queremos eso.

141
00:07:36,190 --> 00:07:39,510
>> Entonces queremos llenar el campo,
queremos inicializar el campo de valor

142
00:07:39,510 --> 00:07:41,690
e inicializar el siguiente campo.

143
00:07:41,690 --> 00:07:45,450
Y luego queremos a-- finalmente como el
prototipo de función indicates-- queremos

144
00:07:45,450 --> 00:07:49,940
para devolver un puntero a un nodo sll.

145
00:07:49,940 --> 00:07:51,710
Entonces, ¿qué hace este parecer visualmente?

146
00:07:51,710 --> 00:07:55,230
Bueno, primero vamos a dinámicamente
asignar espacio para un nuevo nodo SLL,

147
00:07:55,230 --> 00:07:58,320
así que eso es malloc--
una representación visual

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

149
00:08:00,020 --> 00:08:02,757
Y comprobamos que asegurarse
no es null-- en este caso,

150
00:08:02,757 --> 00:08:04,840
la imagen no tendría
aparecido si era nulo,

151
00:08:04,840 --> 00:08:07,298
nos habríamos quedado sin memoria,
así que estamos bien para ir allí.

152
00:08:07,298 --> 00:08:10,200
Así que ahora estamos en el paso C,
inicializar el campo de valor nodos.

153
00:08:10,200 --> 00:08:12,280
Pues bien, en base a esta función
llamo estoy usando aquí,

154
00:08:12,280 --> 00:08:16,700
parece que quiero pasar en 6,
Así que voy a 6 en el campo de valor.

155
00:08:16,700 --> 00:08:18,865
Ahora, inicializar el siguiente campo.

156
00:08:18,865 --> 00:08:21,640
Bueno, ¿qué voy a hacer allí,
no hay nada al lado, a la derecha,

157
00:08:21,640 --> 00:08:23,600
esta es la única cosa en la lista.

158
00:08:23,600 --> 00:08:27,206
Entonces, ¿qué es lo próximo en la lista?

159
00:08:27,206 --> 00:08:29,660
>> No debe apuntar a nada, claro.

160
00:08:29,660 --> 00:08:33,600
No hay nada más allí, así que lo que es
el concepto que conocemos que es nothing--

161
00:08:33,600 --> 00:08:35,638
punteros a nada?

162
00:08:35,638 --> 00:08:37,929
Debe ser tal que queremos
poner un puntero nulo allí,

163
00:08:37,929 --> 00:08:40,178
y voy a representar a la nula
puntero sólo como una caja roja,

164
00:08:40,178 --> 00:08:41,559
no podemos ir más allá.

165
00:08:41,559 --> 00:08:44,430
Como veremos un poco más adelante,
tendremos eventualmente cadenas

166
00:08:44,430 --> 00:08:46,330
de flechas que conectan
estos nodos juntos,

167
00:08:46,330 --> 00:08:48,480
pero cuando se pulsa el
caja roja, que es nula,

168
00:08:48,480 --> 00:08:51,150
no podemos ir más lejos,
ese es el final de la lista.

169
00:08:51,150 --> 00:08:53,960
>> Y por último, sólo queremos
devolver un puntero a este nodo.

170
00:08:53,960 --> 00:08:56,160
Así que lo vamos a llamar nueva,
y volverá nueva

171
00:08:56,160 --> 00:08:59,370
por lo que se puede utilizar en
cualquier función creó.

172
00:08:59,370 --> 00:09:03,100
Así que ahí vamos, Hemos creado una individualmente
nodo de lista enlazada de la nada,

173
00:09:03,100 --> 00:09:05,920
y ahora tenemos una lista que podemos trabajar.

174
00:09:05,920 --> 00:09:08,260
>> Ahora, vamos a decir que ya
tienen una gran cadena,

175
00:09:08,260 --> 00:09:09,800
y queremos encontrar algo en ella.

176
00:09:09,800 --> 00:09:12,716
Y queremos una función que está pasando
para devolver verdadero o falso, dependiendo

177
00:09:12,716 --> 00:09:15,840
sobre si existe un valor en esa lista.

178
00:09:15,840 --> 00:09:18,160
Un prototipo de función, o
declaración para esa función,

179
00:09:18,160 --> 00:09:23,320
podría parecer esto-- Bool encontrar, y
entonces queremos pasar en dos argumentos.

180
00:09:23,320 --> 00:09:26,996
>> El primero, es un puntero a la
primer elemento de la lista enlazada.

181
00:09:26,996 --> 00:09:29,620
Esto es realmente algo que usted
siempre quieren perder de vista,

182
00:09:29,620 --> 00:09:33,110
y en realidad podría ser algo que
incluso se pone en una variable global.

183
00:09:33,110 --> 00:09:35,360
Una vez creada una lista,
siempre, siempre

184
00:09:35,360 --> 00:09:38,990
quiero hacer un seguimiento de la misma
primer elemento de la lista.

185
00:09:38,990 --> 00:09:43,690
De esa manera usted puede hacer referencia a todos los demás
elementos por sólo siguiendo la cadena,

186
00:09:43,690 --> 00:09:47,300
sin tener que mantener punteros
intacto para cada elemento.

187
00:09:47,300 --> 00:09:50,920
Sólo es necesario hacer un seguimiento de la primera
uno si todos están encadenados juntos.

188
00:09:50,920 --> 00:09:52,460
>> Y luego la segunda cosa
estamos pasando de nuevo

189
00:09:52,460 --> 00:09:54,376
es some-- arbitrariamente
cualquiera que sea el tipo de datos que estamos

190
00:09:54,376 --> 00:09:59,640
buscando que hay dentro de
con suerte uno de los nodos de la lista.

191
00:09:59,640 --> 00:10:00,980
¿Cuáles son los pasos?

192
00:10:00,980 --> 00:10:04,250
Bueno, lo primero que hacemos es
creamos un puntero transversal

193
00:10:04,250 --> 00:10:06,015
apuntando a la cabeza de las listas.

194
00:10:06,015 --> 00:10:08,890
Bueno, ¿por qué lo hacemos, ya
tener un puntero a la cabeza listas,

195
00:10:08,890 --> 00:10:10,974
¿por qué no simplemente movemos que nadie alrededor?

196
00:10:10,974 --> 00:10:13,140
Bueno, como acabo de decir,
que es muy importante para nosotros

197
00:10:13,140 --> 00:10:17,580
siempre mantener un seguimiento de la
muy primer elemento en la lista.

198
00:10:17,580 --> 00:10:21,270
Y lo que es en realidad mejor
para crear un duplicado de que,

199
00:10:21,270 --> 00:10:25,350
y el uso que para moverse por lo que nunca
mover accidentalmente de distancia, o siempre

200
00:10:25,350 --> 00:10:30,430
tener un puntero en algún momento que es
a la derecha en el primer elemento de la lista.

201
00:10:30,430 --> 00:10:33,290
Así que es mejor crear un
segundo que utilizamos para moverse.

202
00:10:33,290 --> 00:10:35,877
>> Entonces sólo si comparamos
el campo de valor en ese nodo

203
00:10:35,877 --> 00:10:38,960
es lo que estamos buscando, y si es
No, simplemente movemos al siguiente nodo.

204
00:10:38,960 --> 00:10:41,040
Y seguimos haciendo eso
Una y otra vez,

205
00:10:41,040 --> 00:10:44,811
hasta que nos encontremos, ya sea
el elemento, o golpeamos

206
00:10:44,811 --> 00:10:47,310
null-- que hemos llegado al final
de la lista y no está allí.

207
00:10:47,310 --> 00:10:50,540
Esto debería sonar una campana
a usted como acaba de búsqueda lineal,

208
00:10:50,540 --> 00:10:54,430
sólo estamos replicando en
una estructura de lista enlazada

209
00:10:54,430 --> 00:10:56,280
en lugar de utilizar una matriz para hacerlo.

210
00:10:56,280 --> 00:10:58,210
>> Así que aquí está un ejemplo de
una lista simplemente enlazada.

211
00:10:58,210 --> 00:11:00,043
Éste consiste en
cinco nodos, y tenemos

212
00:11:00,043 --> 00:11:04,330
un puntero a la cabeza de la
lista, que se llama lista.

213
00:11:04,330 --> 00:11:07,385
Lo primero que queremos hacer es
de nuevo, crear ese puntero recorrido.

214
00:11:07,385 --> 00:11:09,760
Así que tenemos ahora dos punteros
que apuntan a lo mismo.

215
00:11:09,760 --> 00:11:15,025
>> Ahora, note aquí también, no lo hice
que malloc cualquier espacio para trav.

216
00:11:15,025 --> 00:11:18,970
Yo no he dicho trav es igual a malloc
algo, ese nodo ya existe,

217
00:11:18,970 --> 00:11:21,160
que el espacio en la memoria ya existe.

218
00:11:21,160 --> 00:11:24,290
Así que todo lo que en realidad estoy haciendo es
creando otro puntero a él.

219
00:11:24,290 --> 00:11:28,210
No estoy mallocing adicionales
espacio, sólo hay ahora dos punteros

220
00:11:28,210 --> 00:11:31,370
apuntando a la misma cosa.

221
00:11:31,370 --> 00:11:33,710
>> Así es 2 lo que estoy buscando?

222
00:11:33,710 --> 00:11:37,220
Bueno, no, así que en vez estoy
va a pasar a la siguiente.

223
00:11:37,220 --> 00:11:41,740
Así que, básicamente, yo diría,
trav es igual a trav siguiente.

224
00:11:41,740 --> 00:11:43,630
Es de 3 lo que estoy buscando, no.

225
00:11:43,630 --> 00:11:45,780
Así que sigo ir
a través, hasta que al final

226
00:11:45,780 --> 00:11:48,690
llego a 6 que es lo que estoy buscando
para en base a la llamada a la función

227
00:11:48,690 --> 00:11:51,600
Tengo en la parte superior
allí, y lo he terminado.

228
00:11:51,600 --> 00:11:54,150
>> Ahora, ¿qué pasa si el elemento que soy
buscando no está en la lista,

229
00:11:54,150 --> 00:11:55,510
está todavía va a funcionar?

230
00:11:55,510 --> 00:11:57,120
Bueno, notará que la lista
aquí es sutilmente diferente,

231
00:11:57,120 --> 00:11:59,410
y esto es otra cosa que es
importante con listas enlazadas,

232
00:11:59,410 --> 00:12:01,780
usted no tiene que preservar
en cualquier orden particular.

233
00:12:01,780 --> 00:12:05,390
Usted puede si lo desea, pero
es posible que ya haya notado

234
00:12:05,390 --> 00:12:09,310
que no estamos hacer el seguimiento de
lo que el elemento número estamos.

235
00:12:09,310 --> 00:12:13,150
>> Y eso es una especie de un comercio que
tener con lista enlazada versos matrices,

236
00:12:13,150 --> 00:12:15,300
es que no tenemos
acceso aleatorio más.

237
00:12:15,300 --> 00:12:18,150
No podemos decir, que quiero
para ir al elemento 0 ª,

238
00:12:18,150 --> 00:12:21,410
o el sexto elemento de mi matriz,
que puedo hacer en una matriz.

239
00:12:21,410 --> 00:12:25,080
No puedo decir que me quiero ir a la
Elemento 0 ª, o el sexto elemento,

240
00:12:25,080 --> 00:12:30,360
o el elemento 25a de mi lista enlazada,
no hay índice asociado con ellos.

241
00:12:30,360 --> 00:12:33,660
Y por lo que en realidad no importa
si preservamos nuestra lista en orden.

242
00:12:33,660 --> 00:12:36,080
Si desea usted
ciertamente puede, pero hay

243
00:12:36,080 --> 00:12:38,567
ninguna razón por la que necesitan para
preservarse en cualquier orden.

244
00:12:38,567 --> 00:12:40,400
Así que de nuevo, vamos a tratar de
encontrar 6 en esta lista.

245
00:12:40,400 --> 00:12:43,200
Bueno, empezamos por el
empezando, no encontramos 6,

246
00:12:43,200 --> 00:12:47,690
y entonces no seguimos encontrando
6, hasta que finalmente llegamos a aquí.

247
00:12:47,690 --> 00:12:52,790
Así correctas puntos ahora trav al nodo
contiene 8, y seis no está ahí.

248
00:12:52,790 --> 00:12:55,250
>> Así que el siguiente paso sería
para ir al siguiente puntero,

249
00:12:55,250 --> 00:12:57,440
lo dicen trav es igual a trav siguiente.

250
00:12:57,440 --> 00:13:00,750
Bueno, trav siguiente, indicado por
la caja roja allí, es nulo.

251
00:13:00,750 --> 00:13:03,020
Así que no hay ningún otro lugar a
ir, y lo que en este punto

252
00:13:03,020 --> 00:13:06,120
podemos concluir que hemos llegado
al final de la lista enlazada,

253
00:13:06,120 --> 00:13:07,190
y 6 no está ahí.

254
00:13:07,190 --> 00:13:10,980
Y sería devuelto
falsa en este caso.

255
00:13:10,980 --> 00:13:14,540
>> OK, ¿cómo nos insertamos una nueva
nodo en la lista enlazada?

256
00:13:14,540 --> 00:13:17,310
Así que hemos sido capaces de crear
una lista enlazada de la nada,

257
00:13:17,310 --> 00:13:19,370
pero probablemente queremos
construir una cadena y no

258
00:13:19,370 --> 00:13:22,620
crear un montón de listas distintas.

259
00:13:22,620 --> 00:13:25,700
Queremos tener una sola lista que
tiene un grupo de nodos en el mismo,

260
00:13:25,700 --> 00:13:28,040
no un montón de listas con un único nodo.

261
00:13:28,040 --> 00:13:31,260
Así no podemos seguir utilizando el Crear
función que definimos antes, ahora nos

262
00:13:31,260 --> 00:13:33,860
quiere insertar en un
lista que ya existe.

263
00:13:33,860 --> 00:13:36,499
>> Así que este caso, vamos
Aconteció en dos argumentos,

264
00:13:36,499 --> 00:13:39,290
el puntero a la cabeza de ese
lista que queremos añadir a la vinculada.

265
00:13:39,290 --> 00:13:40,910
Una vez más, es por eso que es tan
importante que siempre

266
00:13:40,910 --> 00:13:43,400
no perder de vista, porque
es la única manera en que realmente

267
00:13:43,400 --> 00:13:46,690
que se refieren a toda la lista es
con sólo un puntero al primer elemento.

268
00:13:46,690 --> 00:13:49,360
Así que queremos transmitir en un
puntero a ese primer elemento,

269
00:13:49,360 --> 00:13:52,226
y cualquiera que sea el valor que
que desee agregar a la lista.

270
00:13:52,226 --> 00:13:54,600
Y, finalmente, esta función
va a devolver un puntero

271
00:13:54,600 --> 00:13:57,980
a la nueva cabeza de una lista enlazada.

272
00:13:57,980 --> 00:13:59,700
>> ¿Cuáles son los pasos a seguir aquí?

273
00:13:59,700 --> 00:14:02,249
Bueno, al igual que con crear,
tenemos que asignar dinámicamente

274
00:14:02,249 --> 00:14:05,540
espacio para un nuevo nodo, y comprobar para
asegurarse de que no se quede sin memoria, de nuevo,

275
00:14:05,540 --> 00:14:07,150
porque estamos usando malloc.

276
00:14:07,150 --> 00:14:09,080
Entonces queremos poblar
e insertar el nodo,

277
00:14:09,080 --> 00:14:12,730
a fin de poner el número, lo que sea
val es, en el nodo.

278
00:14:12,730 --> 00:14:17,310
Queremos insertar el nodo en
el inicio de la lista enlazada.

279
00:14:17,310 --> 00:14:19,619
>> Hay una razón por la que
querer hacer esto, y

280
00:14:19,619 --> 00:14:21,910
valdría la pena tomar un segundo
para pausar el video aquí,

281
00:14:21,910 --> 00:14:25,860
y pensar acerca de por qué querría
insertar al comienzo de una ligado

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

283
00:14:26,589 --> 00:14:28,630
Una vez más, he mencionado antes
que en realidad no

284
00:14:28,630 --> 00:14:33,020
importa si preservamos de ninguna
orden, así que tal vez eso es una pista.

285
00:14:33,020 --> 00:14:36,040
Y viste lo que pasaría si nos
querido a-- o desde un segundo

286
00:14:36,040 --> 00:14:37,360
hace cuando nos íbamos
a través de búsqueda

287
00:14:37,360 --> 00:14:39,235
podría ver lo que podría
pasaría si tratábamos

288
00:14:39,235 --> 00:14:41,330
para insertar al final de la lista.

289
00:14:41,330 --> 00:14:44,750
Porque no tenemos un
puntero al final de la lista.

290
00:14:44,750 --> 00:14:47,490
>> Así que la razón por la que yo querría
para insertar al principio,

291
00:14:47,490 --> 00:14:49,380
es porque puedo hacerlo inmediatamente.

292
00:14:49,380 --> 00:14:52,730
Tengo un puntero al comienzo, y
vamos a ver esto en un visual en un segundo.

293
00:14:52,730 --> 00:14:55,605
Pero si quiero insertar al final,
Tengo que empezar por el principio,

294
00:14:55,605 --> 00:14:58,760
recorrer todo el camino hasta la
final, y luego virar a encenderlo.

295
00:14:58,760 --> 00:15:01,420
Así que eso significaría que
insertar al final de la lista

296
00:15:01,420 --> 00:15:04,140
se convertiría en un o de n
operación, que se remonta

297
00:15:04,140 --> 00:15:06,720
a nuestra discusión de
complejidad computacional.

298
00:15:06,720 --> 00:15:10,140
Se había convertido en un o de la operación n, donde
como la lista se hizo más grande y más grande,

299
00:15:10,140 --> 00:15:13,310
y más grande, que va a ser más y
más difícil de virar algo

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

301
00:15:14,661 --> 00:15:17,410
Pero siempre es muy fácil
virar algo en al principio,

302
00:15:17,410 --> 00:15:19,060
siempre estás al principio.

303
00:15:19,060 --> 00:15:21,620
>> Y vamos a ver una representación visual de este nuevo.

304
00:15:21,620 --> 00:15:24,100
Y luego, una vez que hayamos terminado, una vez
hemos insertado el nuevo nodo,

305
00:15:24,100 --> 00:15:26,880
queremos volver nuestra puntero a
el nuevo jefe de una lista enlazada, que

306
00:15:26,880 --> 00:15:29,213
ya que estamos insertando en el
comenzando, será realmente

307
00:15:29,213 --> 00:15:31,060
un puntero al nodo que acabamos de crear.

308
00:15:31,060 --> 00:15:33,280
Vamos a visualizar esto,
porque creo que va a ayudar.

309
00:15:33,280 --> 00:15:36,661
>> Así que aquí está nuestra lista, que consiste en
cuatro elementos, un nodo que contiene 15,

310
00:15:36,661 --> 00:15:38,410
lo que apunta a un nodo
que contiene 9, que

311
00:15:38,410 --> 00:15:41,370
apunta a un nodo que contiene 13,
que apunta a un nodo que contiene

312
00:15:41,370 --> 00:15:44,840
10, que tiene la hipótesis nula
puntero como próximo puntero

313
00:15:44,840 --> 00:15:47,010
de manera que es el final de la lista.

314
00:15:47,010 --> 00:15:50,200
Así que queremos insertar un
nuevo nodo con el valor 12

315
00:15:50,200 --> 00:15:52,720
al inicio de esta
lista, ¿qué hacemos?

316
00:15:52,720 --> 00:15:58,770
Bueno, primero que malloc espacio para el
nodo, y luego ponemos 12 en ese país.

317
00:15:58,770 --> 00:16:02,211
>> Así que ahora hemos llegado a un
punto de decisión, ¿no?

318
00:16:02,211 --> 00:16:03,960
Tenemos un par de
punteros que pudimos

319
00:16:03,960 --> 00:16:06,770
movemos, cuál debemos pasar primero?

320
00:16:06,770 --> 00:16:09,250
¿Hay que hacer 12 puntos para
el nuevo jefe de la películas--

321
00:16:09,250 --> 00:16:13,020
o perdón, debemos hacer 12
apuntar a la vieja cabeza de la lista?

322
00:16:13,020 --> 00:16:15,319
¿O deberíamos decir que la
lista ahora comienza a las 12.

323
00:16:15,319 --> 00:16:17,110
Hay una distinción
allí, y vamos a ver

324
00:16:17,110 --> 00:16:19,870
a lo que sucede con los dos en un segundo.

325
00:16:19,870 --> 00:16:23,350
>> Pero esto conduce a una
gran tema de la barra lateral,

326
00:16:23,350 --> 00:16:26,280
que es que una de las
las cosas más difíciles con listas enlazadas

327
00:16:26,280 --> 00:16:30,980
es el de organizar los punteros
en el orden correcto.

328
00:16:30,980 --> 00:16:34,520
Si mueve las cosas fuera de orden,
usted puede terminar accidentalmente

329
00:16:34,520 --> 00:16:36,050
orfandad el resto de la lista.

330
00:16:36,050 --> 00:16:37,300
Y aquí es un ejemplo de eso.

331
00:16:37,300 --> 00:16:40,540
Así que vamos a ir con la idea de--
así, hemos acabamos de crear 12.

332
00:16:40,540 --> 00:16:43,180
Sabemos 12 va a ser
el nuevo jefe de la lista,

333
00:16:43,180 --> 00:16:47,660
y así que ¿por qué no nos movemos
el puntero de la lista para que apunte allí.

334
00:16:47,660 --> 00:16:49,070
>> OK, así que eso es bueno.

335
00:16:49,070 --> 00:16:51,560
Así que ahora, ¿dónde 12 siguiente punto?

336
00:16:51,560 --> 00:16:54,580
Quiero decir, visualmente podemos ver
que apuntará a 15,

337
00:16:54,580 --> 00:16:57,250
como seres humanos es muy obvio para nosotros.

338
00:16:57,250 --> 00:17:00,300
¿Cómo sabe el equipo?

339
00:17:00,300 --> 00:17:02,720
Nosotros no tenemos nada
señalando a 15 más, ¿no?

340
00:17:02,720 --> 00:17:05,869
>> Hemos perdido toda capacidad para hacer referencia a 15.

341
00:17:05,869 --> 00:17:11,460
No podemos decir nueva flecha próximos iguales
algo, no hay nada allí.

342
00:17:11,460 --> 00:17:13,510
De hecho, hemos huérfanos
el resto de la lista

343
00:17:13,510 --> 00:17:16,465
al hacerlo, tenemos
roto accidentalmente la cadena.

344
00:17:16,465 --> 00:17:18,089
Y ciertamente no queremos hacer eso.

345
00:17:18,089 --> 00:17:20,000
>> Así que vamos a volver y probar de nuevo.

346
00:17:20,000 --> 00:17:24,060
Tal vez lo que hay que hacer
es establecer de 12 siguiente puntero

347
00:17:24,060 --> 00:17:28,290
al antiguo jefe de la primera lista,
entonces podemos mover la lista más.

348
00:17:28,290 --> 00:17:30,420
Y de hecho, ese es el
orden correcto que nosotros

349
00:17:30,420 --> 00:17:32,836
debe seguir cuando estamos
trabajar con lista enlazada.

350
00:17:32,836 --> 00:17:36,460
Siempre queremos conectar el
nuevo elemento en la lista,

351
00:17:36,460 --> 00:17:41,010
antes de tomar ese tipo de
importante paso de cambiar

352
00:17:41,010 --> 00:17:43,360
donde la cabeza de la lista enlazada es.

353
00:17:43,360 --> 00:17:46,740
Una vez más, eso es una cosa tan fundamental,
no queremos perder la pista de él.

354
00:17:46,740 --> 00:17:49,310
>> Así que queremos asegurarnos de que
todo está encadenado juntos,

355
00:17:49,310 --> 00:17:52,040
antes de pasar ese puntero.

356
00:17:52,040 --> 00:17:55,300
Y por lo que este sería el orden correcto,
que es conectar 12 a la lista,

357
00:17:55,300 --> 00:17:57,630
luego decir que la lista comienza un 12.

358
00:17:57,630 --> 00:18:00,860
Si nos dijo que la lista empieza a las 12 y
luego trató de conectar 12 a la lista,

359
00:18:00,860 --> 00:18:02,193
ya hemos visto lo que pasa.

360
00:18:02,193 --> 00:18:04,920
Perdemos la lista por error.

361
00:18:04,920 --> 00:18:06,740
>> OK, así que una cosa más que hablar.

362
00:18:06,740 --> 00:18:09,750
¿Qué pasa si queremos deshacernos de
toda una lista ligada a la vez?

363
00:18:09,750 --> 00:18:11,750
Una vez más, estamos mallocing
todo este espacio, por lo que

364
00:18:11,750 --> 00:18:13,351
necesario para liberarlo cuando hayamos terminado.

365
00:18:13,351 --> 00:18:15,350
Así que ahora queremos eliminar
la lista enlazada entero.

366
00:18:15,350 --> 00:18:16,850
Bueno, ¿qué es lo que queremos hacer?

367
00:18:16,850 --> 00:18:20,460
>> Si hemos llegado al puntero nulo, nos
quiere dejar, de lo contrario, simplemente borre

368
00:18:20,460 --> 00:18:23,420
el resto de la lista y luego me libera.

369
00:18:23,420 --> 00:18:28,890
Elimine el resto de la lista,
y luego liberar el nodo actual.

370
00:18:28,890 --> 00:18:32,850
Lo que hace que el sonido como,
qué técnica tenemos que hablamos

371
00:18:32,850 --> 00:18:35,440
acerca previamente suena eso?

372
00:18:35,440 --> 00:18:39,560
Eliminar todos los demás, a continuación,
volver y me eliminar.

373
00:18:39,560 --> 00:18:42,380
>> Esa es la recursividad, hemos hecho la
problema un poco más pequeño,

374
00:18:42,380 --> 00:18:46,910
estamos diciendo borrar todo el mundo
persona, entonces usted me puede eliminar.

375
00:18:46,910 --> 00:18:50,940
Y más por el camino, ese nodo
dirán, borrar todos los demás.

376
00:18:50,940 --> 00:18:53,940
Pero con el tiempo vamos a llegar a la
punto en el que la lista es nulo,

377
00:18:53,940 --> 00:18:55,310
y ese es nuestro caso base.

378
00:18:55,310 --> 00:18:57,010
>> Así que vamos a echar un vistazo a esto,
y cómo esto podría funcionar.

379
00:18:57,010 --> 00:18:59,759
Así que aquí está nuestra lista, que es el mismo
Enumeramos sólo estábamos hablando,

380
00:18:59,759 --> 00:19:00,980
y hay los pasos.

381
00:19:00,980 --> 00:19:04,200
Hay una gran cantidad de texto aquí, pero
esperemos que la visualización le ayudará.

382
00:19:04,200 --> 00:19:08,557
>> Así que tener-- y también detuvimos
nuestra marcos de pila ilustración

383
00:19:08,557 --> 00:19:10,890
de nuestro video en pilas de llamadas,
y espero que todo esto

384
00:19:10,890 --> 00:19:13,260
juntos le mostrará lo que está pasando.

385
00:19:13,260 --> 00:19:14,510
Así que aquí está nuestro código pseudocódigo.

386
00:19:14,510 --> 00:19:17,830
Si llegamos a un nulo
puntero, parada, de lo contrario,

387
00:19:17,830 --> 00:19:21,320
eliminar el resto de la lista,
a continuación, liberar el nodo actual.

388
00:19:21,320 --> 00:19:25,700
Así que ahora mismo, películas--
el puntero que estamos

389
00:19:25,700 --> 00:19:28,410
pasando para destruir puntos a 12.

390
00:19:28,410 --> 00:19:33,340
12 no es un puntero nulo, así que estamos
va a eliminar el resto de la lista.

391
00:19:33,340 --> 00:19:35,450
>> Lo que está borrando el
resto de nosotros involucrados?

392
00:19:35,450 --> 00:19:37,950
Bueno, significa hacer una
llamar para destruir, diciendo:

393
00:19:37,950 --> 00:19:42,060
15 que es el comienzo de la
resto de la lista que queremos destruir.

394
00:19:42,060 --> 00:19:47,480
Y así la llamada a destruir
12 es tipo de en espera.

395
00:19:47,480 --> 00:19:52,690
Ha congelado allí, esperando el
llamar para destruir 15, para terminar su trabajo.

396
00:19:52,690 --> 00:19:56,280
>> Bueno, 15 no es un puntero nulo, y
por lo que va a decir, está bien,

397
00:19:56,280 --> 00:19:58,450
así, elimine el resto de la lista.

398
00:19:58,450 --> 00:20:00,760
El resto de la lista comienza
a las 9, por lo que sólo tendremos que

399
00:20:00,760 --> 00:20:04,514
espere hasta que se elimine todo lo que
cosas, y luego volver y me eliminar.

400
00:20:04,514 --> 00:20:06,680
Bueno 9 que va a decir, bueno,
Yo no soy un puntero nulo,

401
00:20:06,680 --> 00:20:09,020
así eliminar el resto de la lista de aquí.

402
00:20:09,020 --> 00:20:11,805
Y así tratar de destruir 13.

403
00:20:11,805 --> 00:20:15,550
13 dice: Yo no soy puntero nulo,
lo mismo, pasa la pelota.

404
00:20:15,550 --> 00:20:17,930
10 no es puntero nulo, 10
contiene un puntero nulo,

405
00:20:17,930 --> 00:20:20,200
pero 10 no es en sí misma una
puntero nulo en este momento,

406
00:20:20,200 --> 00:20:22,470
y por lo que pasa el dinero también.

407
00:20:22,470 --> 00:20:25,560
>> Y ahora una lista de los puntos allí,
Realmente sería apuntar a some--

408
00:20:25,560 --> 00:20:28,710
si tuviera más espacio en la imagen,
sería apuntar a un cierto espacio al azar

409
00:20:28,710 --> 00:20:29,960
que no sabemos lo que es.

410
00:20:29,960 --> 00:20:34,680
Es el puntero nulo, sin embargo, la lista
se establece ahora, literalmente, es valores nulos.

411
00:20:34,680 --> 00:20:36,820
Se señala a la derecha dentro de esa caja roja.

412
00:20:36,820 --> 00:20:39,960
Llegamos a un puntero nulo, por lo que
podemos parar, y estamos hecho.

413
00:20:39,960 --> 00:20:46,230
>> Y para que el marco púrpura es ahora-- en el
parte superior de stack-- que es el marco activo,

414
00:20:46,230 --> 00:20:47,017
pero se hace.

415
00:20:47,017 --> 00:20:48,600
Si hemos llegado a un puntero nulo, para.

416
00:20:48,600 --> 00:20:51,290
Nosotros no hacemos nada,
no se puede liberar un puntero nulo,

417
00:20:51,290 --> 00:20:55,070
que no malloc cualquiera
espacio, y así hemos terminado.

418
00:20:55,070 --> 00:20:57,590
Así que marco de función
se destruye, y nosotros

419
00:20:57,590 --> 00:21:00,930
resume-- recogemos donde lo dejamos
con la siguiente más alta, lo cual

420
00:21:00,930 --> 00:21:02,807
Es este marco azul oscuro aquí.

421
00:21:02,807 --> 00:21:04,390
Así que tomamos justo donde lo dejamos.

422
00:21:04,390 --> 00:21:06,598
Hemos suprimido el resto de la
lista ya, por lo que ahora estamos

423
00:21:06,598 --> 00:21:08,000
va a liberar a los nodos actuales.

424
00:21:08,000 --> 00:21:12,920
Así que ahora podemos liberar este nodo, y ahora
hemos llegado al final de la función.

425
00:21:12,920 --> 00:21:16,810
Y para que marco de función se destruye,
y nosotros recogemos en el azul claro.

426
00:21:16,810 --> 00:21:20,650
>> Así que says-- ya he done--
suprimir el resto de la lista, por lo

427
00:21:20,650 --> 00:21:23,140
liberar el nodo actual.

428
00:21:23,140 --> 00:21:26,520
Y ahora el cuadro amarillo es
volver a la cima de la pila.

429
00:21:26,520 --> 00:21:29,655
Y así como ves, ahora estamos
la destrucción de la lista de derecha a izquierda.

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

431
00:21:33,710 --> 00:21:37,280
>> ¿Qué hubiera pasado, sin embargo,
si hubiéramos hecho las cosas de manera equivocada?

432
00:21:37,280 --> 00:21:39,410
Al igual que cuando intentamos
para agregar un elemento.

433
00:21:39,410 --> 00:21:41,909
Si mal estado de la cadena, en caso
no nos conectamos los punteros

434
00:21:41,909 --> 00:21:44,690
en el orden correcto, si
liberado al primer elemento,

435
00:21:44,690 --> 00:21:47,420
si nos liberamos de la
cabeza de la lista, ahora

436
00:21:47,420 --> 00:21:49,642
no hay manera de referirse a
el resto de la lista.

437
00:21:49,642 --> 00:21:51,350
Y así tendríamos
todo huérfanos,

438
00:21:51,350 --> 00:21:53,880
hubiéramos tenido lo que hay
llama una pérdida de memoria.

439
00:21:53,880 --> 00:21:56,800
Si usted recuerda de nuestro video
en la asignación de memoria dinámica,

440
00:21:56,800 --> 00:21:58,650
eso no es muy bueno.

441
00:21:58,650 --> 00:22:00,810
>> Así que como ya he dicho, hay
son varias operaciones

442
00:22:00,810 --> 00:22:04,010
que tenemos que usar para trabajar
con lista vinculada efectivamente.

443
00:22:04,010 --> 00:22:08,430
Y te habrás dado cuenta omití uno,
la eliminación de un solo elemento de una ligado

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

445
00:22:09,064 --> 00:22:10,980
La razón por la que hice
es que es en realidad un poco

446
00:22:10,980 --> 00:22:14,360
difícil de pensar acerca de cómo eliminar
un solo elemento de una individualmente

447
00:22:14,360 --> 00:22:15,600
lista enlazada.

448
00:22:15,600 --> 00:22:19,950
Tenemos que ser capaces de pasar por alto
algo en la lista, que

449
00:22:19,950 --> 00:22:22,975
significa que lleguemos a un nosotros point--
quieres borrar este node--

450
00:22:22,975 --> 00:22:25,350
pero a fin de que sea así que
no pierda ninguna información,

451
00:22:25,350 --> 00:22:30,530
tenemos que conectar este
nodo de aquí, aquí.

452
00:22:30,530 --> 00:22:33,390
>> Así que probablemente hice mal
desde una perspectiva visual.

453
00:22:33,390 --> 00:22:36,830
Así que estamos en el comienzo de nuestra
lista, estamos procediendo a través,

454
00:22:36,830 --> 00:22:40,510
queremos eliminar este nodo.

455
00:22:40,510 --> 00:22:43,440
Si nos limitamos a borrarlo,
hemos roto la cadena.

456
00:22:43,440 --> 00:22:45,950
Este nodo aquí
se refiere a todo lo demás,

457
00:22:45,950 --> 00:22:48,260
que contiene la cadena de aquí en adelante.

458
00:22:48,260 --> 00:22:51,190
>> Así que lo que tenemos que hacer realidad
después de llegar a este punto,

459
00:22:51,190 --> 00:22:56,670
es que tenemos que dar un paso atrás uno, y
conectar este nodo a través de este nodo,

460
00:22:56,670 --> 00:22:58,590
así entonces podemos eliminar
el uno en el centro.

461
00:22:58,590 --> 00:23:02,120
Pero las listas por separado enlazados no hacen
nos proporcionan una manera de ir hacia atrás.

462
00:23:02,120 --> 00:23:05,160
Así que tenemos que mantener cualquiera
dos punteros, y moverlos

463
00:23:05,160 --> 00:23:09,527
especie de paso fuera, una detrás de la
otra medida que avanzamos, o llegar a un punto

464
00:23:09,527 --> 00:23:11,110
y luego enviar a través de otro puntero.

465
00:23:11,110 --> 00:23:13,150
Y como se puede ver,
puede ser un poco desordenado.

466
00:23:13,150 --> 00:23:15,360
Afortunadamente, tenemos
otra manera de resolver esto,

467
00:23:15,360 --> 00:23:17,810
cuando hablamos de listas doblemente enlazadas.

468
00:23:17,810 --> 00:23:20,720
>> Soy Doug Lloyd, esto es CS50.

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