>> [REPRODUCCIÓN DE MÚSICA]
>> DOUG LLOYD: OK, así que al este punto en el curso,
hemos cubierto muchos de los conceptos básicos de la C. Sabemos mucho acerca de variables, matrices,
punteros, todas esas cosas buenas.
Esos son todo tipo de construido para ver como los fundamentos,
pero podemos hacer más, ¿no?
Podemos combinar cosas juntos en formas interesantes.
>> Y así vamos a hacer eso, vamos a empezar diversificarse de lo C nos da,
y empezar a crear nuestros propios datos estructuras que utilizan estos edificios
bloques juntos para hacer algo realmente valioso, útil.
Una forma de hacerlo es para hablar sobre las colecciones.
Así que hasta ahora hemos tenido un tipo de datos estructura para representar colecciones
de recibir los valores, valores similares.
Eso sería una matriz.
Disponemos de colecciones de números enteros, o colecciones de personajes y así sucesivamente.
>> Estructuras también una especie de datos estructura para la recopilación de información,
pero no lo es para recoger como valores.
Por lo general, se mezcla diferentes tipos de datos juntos dentro de una sola caja.
Pero no es en sí utilizado para encadenar
o conecte juntas similares artículos, como una matriz.
Las matrices son grandes para elemento de mirar hacia arriba, pero el recuerdo
que es muy difícil para insertar en una matriz,
a menos que estamos insertando en el final de esa matriz.
>> Y el mejor ejemplo que tiene para eso es la ordenación por inserción.
Si usted recuerda nuestro video de ordenación por inserción,
había una gran cantidad de gastos involucrados en tener
para recoger elementos, y desplazarlos fuera del camino para adaptarse a algo
en el centro de su matriz.
Las matrices también sufren de otra problema, que es la inflexibilidad.
Cuando declaramos una matriz, tenemos una oportunidad en él.
Tenemos que decir, quiero esta cantidad de elementos.
Podría ser 100, podría ser 1000, podría
ser x, donde x es un número que el usuario nos dio en el símbolo o en el comando
la línea.
>> Pero sólo tenemos una oportunidad por ella, no llego a decir a continuación, oh, en realidad yo
necesitaba 101, o que necesitaba x más 20.
Demasiado tarde, ya hemos declarado la matriz, y si queremos obtener 101 ó x
más 20, tenemos que declarar un conjunto completamente diferente,
copiar todos los elementos de la matriz terminado, y entonces tenemos suficiente.
¿Y si nos equivocamos de nuevo, lo que si en realidad necesitamos 102, o x más de 40 años,
tenemos que hacer esto de nuevo.
Así que son muy inflexibles para cambiar el tamaño de nuestros datos,
pero si combinamos a algunos de los conceptos básicos que ya hemos
aprendido acerca de los punteros y estructuras, en particular, el uso de memoria dinámica
asignación con malloc, que puede poner estas piezas juntas
para crear un un nuevo dato structure-- lista podríamos decir-- enlazada
que nos permite crecer y reducir una colección de valores
y no vamos a tener ningún espacio perdido.
>> Así que de nuevo, llamamos a esta idea, esta noción, una lista enlazada.
En particular, en este video estamos hablando de lista enlazada,
y luego otro video hablaremos listas sobre doblemente enlazadas, que
es sólo una variación sobre un tema aquí.
Sin embargo, una lista enlazada se compone de nodos,
nodos sólo ser un term-- abstracta es sólo algo que estoy llamando
eso es una especie de estructura, básicamente, estoy?
Sólo va a llamar a un node-- y esto nodo tiene dos miembros, o dos campos.
Tiene datos, por lo general una número entero, un flotador carácter,
o podría ser algún otro tipo de datos que ha definido con un tipo def.
Y contiene un puntero a otro nodo del mismo tipo.
>> Así que tenemos dos cosas en el interior de este nodo, los datos y un puntero
a otro nodo.
Y si usted comienza a visualizar esto, se puede pensar en ello
como una cadena de nodos que están conectados entre sí.
Tenemos el primer nodo, contiene datos, y un puntero
al segundo nodo, que contiene de datos, y un puntero a la tercera nodo.
Y por eso lo llamamos un lista enlazada, están unidos entre sí.
>> ¿Qué hace este especial estructura de nodos parece?
Bueno, si usted recuerda de nuestro video en la definición de tipos personalizados, con el tipo de definición,
podemos definir un structure-- y escriba definir una estructura como esta.
tyepdef struct sllist, y entonces estoy utilizando el valor de la palabra aquí arbitrariamente
para indicar cualquier tipo de datos realmente.
Usted podría pasar un entero o flotante, usted podría tener lo que quieras.
No está restringido a solo enteros, ni nada de eso.
Así que el valor es sólo una arbitraria tipo de datos, y luego un puntero
a otro nodo del mismo tipo.
>> Ahora, hay un poco de capturas aquí con la definición de una estructura de
cuando es una estructura auto referencial.
Tengo que tener un temporal nombrar por mi estructura.
Al final del día I claramente quieren llamarlo
nodo sll, que es en última instancia, el nuevo nombrar parte de mi tipo de definición,
pero no puedo utilizar el nodo sll en el medio de esto.
La razón es que no lo he hecho creado un nodo SLL tipo llamado
hasta que llegué a este punto final aquí.
Hasta ese momento, tengo que tener otra manera de referirse a este tipo de datos.
>> Y este es un auto tipo de datos referencial.
Es, es un tipo de datos de un estructura que contiene un dato,
y un puntero a otro estructura del mismo tipo.
Así que tengo que ser capaz de referirse a este tipo de datos al menos temporalmente,
por lo que le da un temporal nombre del struct sllist
me permite entonces digo que quiero un puntero a otra estructura sllist,
una estrella struct sllist, y luego después de haber completado la definición,
Ahora puedo llamar a este tipo de un nodo sll.
>> Así que por eso se ve que hay un nombre temporal aquí,
sino un nombre permanente aquí.
A veces es posible que vea las definiciones de la estructura,
por ejemplo, que no son auto referencial, que
no tienen un nombre especificador aquí.
Simplemente diría typedef struct, abrir corchete y luego definirlo.
Pero si usted es struct es auto referencial, como ésta es,
es necesario especificar un nombre de tipo temporal.
Pero en última instancia, ahora que hemos hecho esto,
acabamos de hacer referencia a estos nodos, estas unidades,
como nodos SLL propósitos del resto de este video.
>> Muy bien, así que sabemos cómo crear un nodo de lista enlazada.
Sabemos cómo definir un nodo de lista enlazada.
Ahora, si vamos a empezar usarlas para recopilar información,
hay un par de operaciones que necesidad de entender y trabajar con ellos.
Tenemos que saber cómo crear una lista enlazada de la nada.
Si no hay ninguna lista ya, queremos empezar una.
Así que tenemos que ser capaces de para crear una lista enlazada,
tenemos que probablemente buscar a través de la lista de enlaces
para encontrar un elemento que estamos buscando.
Tenemos que ser capaces de insertar nuevas cosas en la lista,
queremos que nuestra lista para poder crecer.
Y del mismo modo, queremos ser capaces eliminar cosas de nuestra lista,
queremos que nuestra lista para ser capaz de reducir el tamaño.
Y al final de nuestra programas, especialmente
si usted recuerda que somos asignación dinámica de memoria
para construir estas listas normalmente, queremos liberar a toda la que la memoria
cuando hayamos terminado de trabajar con él.
Y así tenemos que ser capaces de borrar una toda lista enlazada en un fallo de la redada.
Así que vamos a ir a través algunas de estas operaciones
y cómo podemos visualizarlos, hablando en código pseudocódigo específicamente.
Así que queremos crear un lista enlazada, así que tal vez
desee definir una función con este prototipo.
sll estrellas nodo, cree, y yo estoy pasando en un argumento, algunos datos arbitrarios
escriba de nuevo, de algún tipo de datos arbitrario.
Pero estoy returning-- esta función debería volverá a mí un puntero, a un solitario
nodo de lista enlazada.
Una vez más, estamos tratando de crear una lista enlazada de la nada,
así que necesito un puntero a esa lista cuando he terminado.
>> ¿Cuáles son los pasos a seguir aquí?
Bueno, primero que estoy vamos a hacer es dinámicamente
asignar espacio para un nuevo nodo.
Una vez más, estamos creando fuera de fina aire, por lo que necesitamos el espacio malloc para ello.
Y, por supuesto, de inmediato después de que malloc,
siempre comprobar para asegurarse de que nuestra pointer-- no conseguimos volver nulo.
Porque si tratamos de deferencia un puntero nulo,
vamos a sufrir un violación de segmento y no queremos eso.
>> Entonces queremos llenar el campo, queremos inicializar el campo de valor
e inicializar el siguiente campo.
Y luego queremos a-- finalmente como el prototipo de función indicates-- queremos
para devolver un puntero a un nodo sll.
Entonces, ¿qué hace este parecer visualmente?
Bueno, primero vamos a dinámicamente asignar espacio para un nuevo nodo SLL,
así que eso es malloc-- una representación visual
del nodo que acabamos de crear.
Y comprobamos que asegurarse no es null-- en este caso,
la imagen no tendría aparecido si era nulo,
nos habríamos quedado sin memoria, así que estamos bien para ir allí.
Así que ahora estamos en el paso C, inicializar el campo de valor nodos.
Pues bien, en base a esta función llamo estoy usando aquí,
parece que quiero pasar en 6, Así que voy a 6 en el campo de valor.
Ahora, inicializar el siguiente campo.
Bueno, ¿qué voy a hacer allí, no hay nada al lado, a la derecha,
esta es la única cosa en la lista.
Entonces, ¿qué es lo próximo en la lista?
>> No debe apuntar a nada, claro.
No hay nada más allí, así que lo que es el concepto que conocemos que es nothing--
punteros a nada?
Debe ser tal que queremos poner un puntero nulo allí,
y voy a representar a la nula puntero sólo como una caja roja,
no podemos ir más allá.
Como veremos un poco más adelante, tendremos eventualmente cadenas
de flechas que conectan estos nodos juntos,
pero cuando se pulsa el caja roja, que es nula,
no podemos ir más lejos, ese es el final de la lista.
>> Y por último, sólo queremos devolver un puntero a este nodo.
Así que lo vamos a llamar nueva, y volverá nueva
por lo que se puede utilizar en cualquier función creó.
Así que ahí vamos, Hemos creado una individualmente nodo de lista enlazada de la nada,
y ahora tenemos una lista que podemos trabajar.
>> Ahora, vamos a decir que ya tienen una gran cadena,
y queremos encontrar algo en ella.
Y queremos una función que está pasando para devolver verdadero o falso, dependiendo
sobre si existe un valor en esa lista.
Un prototipo de función, o declaración para esa función,
podría parecer esto-- Bool encontrar, y entonces queremos pasar en dos argumentos.
>> El primero, es un puntero a la primer elemento de la lista enlazada.
Esto es realmente algo que usted siempre quieren perder de vista,
y en realidad podría ser algo que incluso se pone en una variable global.
Una vez creada una lista, siempre, siempre
quiero hacer un seguimiento de la misma primer elemento de la lista.
De esa manera usted puede hacer referencia a todos los demás elementos por sólo siguiendo la cadena,
sin tener que mantener punteros intacto para cada elemento.
Sólo es necesario hacer un seguimiento de la primera uno si todos están encadenados juntos.
>> Y luego la segunda cosa estamos pasando de nuevo
es some-- arbitrariamente cualquiera que sea el tipo de datos que estamos
buscando que hay dentro de con suerte uno de los nodos de la lista.
¿Cuáles son los pasos?
Bueno, lo primero que hacemos es creamos un puntero transversal
apuntando a la cabeza de las listas.
Bueno, ¿por qué lo hacemos, ya tener un puntero a la cabeza listas,
¿por qué no simplemente movemos que nadie alrededor?
Bueno, como acabo de decir, que es muy importante para nosotros
siempre mantener un seguimiento de la muy primer elemento en la lista.
Y lo que es en realidad mejor para crear un duplicado de que,
y el uso que para moverse por lo que nunca mover accidentalmente de distancia, o siempre
tener un puntero en algún momento que es a la derecha en el primer elemento de la lista.
Así que es mejor crear un segundo que utilizamos para moverse.
>> Entonces sólo si comparamos el campo de valor en ese nodo
es lo que estamos buscando, y si es No, simplemente movemos al siguiente nodo.
Y seguimos haciendo eso Una y otra vez,
hasta que nos encontremos, ya sea el elemento, o golpeamos
null-- que hemos llegado al final de la lista y no está allí.
Esto debería sonar una campana a usted como acaba de búsqueda lineal,
sólo estamos replicando en una estructura de lista enlazada
en lugar de utilizar una matriz para hacerlo.
>> Así que aquí está un ejemplo de una lista simplemente enlazada.
Éste consiste en cinco nodos, y tenemos
un puntero a la cabeza de la lista, que se llama lista.
Lo primero que queremos hacer es de nuevo, crear ese puntero recorrido.
Así que tenemos ahora dos punteros que apuntan a lo mismo.
>> Ahora, note aquí también, no lo hice que malloc cualquier espacio para trav.
Yo no he dicho trav es igual a malloc algo, ese nodo ya existe,
que el espacio en la memoria ya existe.
Así que todo lo que en realidad estoy haciendo es creando otro puntero a él.
No estoy mallocing adicionales espacio, sólo hay ahora dos punteros
apuntando a la misma cosa.
>> Así es 2 lo que estoy buscando?
Bueno, no, así que en vez estoy va a pasar a la siguiente.
Así que, básicamente, yo diría, trav es igual a trav siguiente.
Es de 3 lo que estoy buscando, no.
Así que sigo ir a través, hasta que al final
llego a 6 que es lo que estoy buscando para en base a la llamada a la función
Tengo en la parte superior allí, y lo he terminado.
>> Ahora, ¿qué pasa si el elemento que soy buscando no está en la lista,
está todavía va a funcionar?
Bueno, notará que la lista aquí es sutilmente diferente,
y esto es otra cosa que es importante con listas enlazadas,
usted no tiene que preservar en cualquier orden particular.
Usted puede si lo desea, pero es posible que ya haya notado
que no estamos hacer el seguimiento de lo que el elemento número estamos.
>> Y eso es una especie de un comercio que tener con lista enlazada versos matrices,
es que no tenemos acceso aleatorio más.
No podemos decir, que quiero para ir al elemento 0 ª,
o el sexto elemento de mi matriz, que puedo hacer en una matriz.
No puedo decir que me quiero ir a la Elemento 0 ª, o el sexto elemento,
o el elemento 25a de mi lista enlazada, no hay índice asociado con ellos.
Y por lo que en realidad no importa si preservamos nuestra lista en orden.
Si desea usted ciertamente puede, pero hay
ninguna razón por la que necesitan para preservarse en cualquier orden.
Así que de nuevo, vamos a tratar de encontrar 6 en esta lista.
Bueno, empezamos por el empezando, no encontramos 6,
y entonces no seguimos encontrando 6, hasta que finalmente llegamos a aquí.
Así correctas puntos ahora trav al nodo contiene 8, y seis no está ahí.
>> Así que el siguiente paso sería para ir al siguiente puntero,
lo dicen trav es igual a trav siguiente.
Bueno, trav siguiente, indicado por la caja roja allí, es nulo.
Así que no hay ningún otro lugar a ir, y lo que en este punto
podemos concluir que hemos llegado al final de la lista enlazada,
y 6 no está ahí.
Y sería devuelto falsa en este caso.
>> OK, ¿cómo nos insertamos una nueva nodo en la lista enlazada?
Así que hemos sido capaces de crear una lista enlazada de la nada,
pero probablemente queremos construir una cadena y no
crear un montón de listas distintas.
Queremos tener una sola lista que tiene un grupo de nodos en el mismo,
no un montón de listas con un único nodo.
Así no podemos seguir utilizando el Crear función que definimos antes, ahora nos
quiere insertar en un lista que ya existe.
>> Así que este caso, vamos Aconteció en dos argumentos,
el puntero a la cabeza de ese lista que queremos añadir a la vinculada.
Una vez más, es por eso que es tan importante que siempre
no perder de vista, porque es la única manera en que realmente
que se refieren a toda la lista es con sólo un puntero al primer elemento.
Así que queremos transmitir en un puntero a ese primer elemento,
y cualquiera que sea el valor que que desee agregar a la lista.
Y, finalmente, esta función va a devolver un puntero
a la nueva cabeza de una lista enlazada.
>> ¿Cuáles son los pasos a seguir aquí?
Bueno, al igual que con crear, tenemos que asignar dinámicamente
espacio para un nuevo nodo, y comprobar para asegurarse de que no se quede sin memoria, de nuevo,
porque estamos usando malloc.
Entonces queremos poblar e insertar el nodo,
a fin de poner el número, lo que sea val es, en el nodo.
Queremos insertar el nodo en el inicio de la lista enlazada.
>> Hay una razón por la que querer hacer esto, y
valdría la pena tomar un segundo para pausar el video aquí,
y pensar acerca de por qué querría insertar al comienzo de una ligado
lista.
Una vez más, he mencionado antes que en realidad no
importa si preservamos de ninguna orden, así que tal vez eso es una pista.
Y viste lo que pasaría si nos querido a-- o desde un segundo
hace cuando nos íbamos a través de búsqueda
podría ver lo que podría pasaría si tratábamos
para insertar al final de la lista.
Porque no tenemos un puntero al final de la lista.
>> Así que la razón por la que yo querría para insertar al principio,
es porque puedo hacerlo inmediatamente.
Tengo un puntero al comienzo, y vamos a ver esto en un visual en un segundo.
Pero si quiero insertar al final, Tengo que empezar por el principio,
recorrer todo el camino hasta la final, y luego virar a encenderlo.
Así que eso significaría que insertar al final de la lista
se convertiría en un o de n operación, que se remonta
a nuestra discusión de complejidad computacional.
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,
y más grande, que va a ser más y más difícil de virar algo
en al final.
Pero siempre es muy fácil virar algo en al principio,
siempre estás al principio.
>> Y vamos a ver una representación visual de este nuevo.
Y luego, una vez que hayamos terminado, una vez hemos insertado el nuevo nodo,
queremos volver nuestra puntero a el nuevo jefe de una lista enlazada, que
ya que estamos insertando en el comenzando, será realmente
un puntero al nodo que acabamos de crear.
Vamos a visualizar esto, porque creo que va a ayudar.
>> Así que aquí está nuestra lista, que consiste en cuatro elementos, un nodo que contiene 15,
lo que apunta a un nodo que contiene 9, que
apunta a un nodo que contiene 13, que apunta a un nodo que contiene
10, que tiene la hipótesis nula puntero como próximo puntero
de manera que es el final de la lista.
Así que queremos insertar un nuevo nodo con el valor 12
al inicio de esta lista, ¿qué hacemos?
Bueno, primero que malloc espacio para el nodo, y luego ponemos 12 en ese país.
>> Así que ahora hemos llegado a un punto de decisión, ¿no?
Tenemos un par de punteros que pudimos
movemos, cuál debemos pasar primero?
¿Hay que hacer 12 puntos para el nuevo jefe de la películas--
o perdón, debemos hacer 12 apuntar a la vieja cabeza de la lista?
¿O deberíamos decir que la lista ahora comienza a las 12.
Hay una distinción allí, y vamos a ver
a lo que sucede con los dos en un segundo.
>> Pero esto conduce a una gran tema de la barra lateral,
que es que una de las las cosas más difíciles con listas enlazadas
es el de organizar los punteros en el orden correcto.
Si mueve las cosas fuera de orden, usted puede terminar accidentalmente
orfandad el resto de la lista.
Y aquí es un ejemplo de eso.
Así que vamos a ir con la idea de-- así, hemos acabamos de crear 12.
Sabemos 12 va a ser el nuevo jefe de la lista,
y así que ¿por qué no nos movemos el puntero de la lista para que apunte allí.
>> OK, así que eso es bueno.
Así que ahora, ¿dónde 12 siguiente punto?
Quiero decir, visualmente podemos ver que apuntará a 15,
como seres humanos es muy obvio para nosotros.
¿Cómo sabe el equipo?
Nosotros no tenemos nada señalando a 15 más, ¿no?
>> Hemos perdido toda capacidad para hacer referencia a 15.
No podemos decir nueva flecha próximos iguales algo, no hay nada allí.
De hecho, hemos huérfanos el resto de la lista
al hacerlo, tenemos roto accidentalmente la cadena.
Y ciertamente no queremos hacer eso.
>> Así que vamos a volver y probar de nuevo.
Tal vez lo que hay que hacer es establecer de 12 siguiente puntero
al antiguo jefe de la primera lista, entonces podemos mover la lista más.
Y de hecho, ese es el orden correcto que nosotros
debe seguir cuando estamos trabajar con lista enlazada.
Siempre queremos conectar el nuevo elemento en la lista,
antes de tomar ese tipo de importante paso de cambiar
donde la cabeza de la lista enlazada es.
Una vez más, eso es una cosa tan fundamental, no queremos perder la pista de él.
>> Así que queremos asegurarnos de que todo está encadenado juntos,
antes de pasar ese puntero.
Y por lo que este sería el orden correcto, que es conectar 12 a la lista,
luego decir que la lista comienza un 12.
Si nos dijo que la lista empieza a las 12 y luego trató de conectar 12 a la lista,
ya hemos visto lo que pasa.
Perdemos la lista por error.
>> OK, así que una cosa más que hablar.
¿Qué pasa si queremos deshacernos de toda una lista ligada a la vez?
Una vez más, estamos mallocing todo este espacio, por lo que
necesario para liberarlo cuando hayamos terminado.
Así que ahora queremos eliminar la lista enlazada entero.
Bueno, ¿qué es lo que queremos hacer?
>> Si hemos llegado al puntero nulo, nos quiere dejar, de lo contrario, simplemente borre
el resto de la lista y luego me libera.
Elimine el resto de la lista, y luego liberar el nodo actual.
Lo que hace que el sonido como, qué técnica tenemos que hablamos
acerca previamente suena eso?
Eliminar todos los demás, a continuación, volver y me eliminar.
>> Esa es la recursividad, hemos hecho la problema un poco más pequeño,
estamos diciendo borrar todo el mundo persona, entonces usted me puede eliminar.
Y más por el camino, ese nodo dirán, borrar todos los demás.
Pero con el tiempo vamos a llegar a la punto en el que la lista es nulo,
y ese es nuestro caso base.
>> Así que vamos a echar un vistazo a esto, y cómo esto podría funcionar.
Así que aquí está nuestra lista, que es el mismo Enumeramos sólo estábamos hablando,
y hay los pasos.
Hay una gran cantidad de texto aquí, pero esperemos que la visualización le ayudará.
>> Así que tener-- y también detuvimos nuestra marcos de pila ilustración
de nuestro video en pilas de llamadas, y espero que todo esto
juntos le mostrará lo que está pasando.
Así que aquí está nuestro código pseudocódigo.
Si llegamos a un nulo puntero, parada, de lo contrario,
eliminar el resto de la lista, a continuación, liberar el nodo actual.
Así que ahora mismo, películas-- el puntero que estamos
pasando para destruir puntos a 12.
12 no es un puntero nulo, así que estamos va a eliminar el resto de la lista.
>> Lo que está borrando el resto de nosotros involucrados?
Bueno, significa hacer una llamar para destruir, diciendo:
15 que es el comienzo de la resto de la lista que queremos destruir.
Y así la llamada a destruir 12 es tipo de en espera.
Ha congelado allí, esperando el llamar para destruir 15, para terminar su trabajo.
>> Bueno, 15 no es un puntero nulo, y por lo que va a decir, está bien,
así, elimine el resto de la lista.
El resto de la lista comienza a las 9, por lo que sólo tendremos que
espere hasta que se elimine todo lo que cosas, y luego volver y me eliminar.
Bueno 9 que va a decir, bueno, Yo no soy un puntero nulo,
así eliminar el resto de la lista de aquí.
Y así tratar de destruir 13.
13 dice: Yo no soy puntero nulo, lo mismo, pasa la pelota.
10 no es puntero nulo, 10 contiene un puntero nulo,
pero 10 no es en sí misma una puntero nulo en este momento,
y por lo que pasa el dinero también.
>> Y ahora una lista de los puntos allí, Realmente sería apuntar a some--
si tuviera más espacio en la imagen, sería apuntar a un cierto espacio al azar
que no sabemos lo que es.
Es el puntero nulo, sin embargo, la lista se establece ahora, literalmente, es valores nulos.
Se señala a la derecha dentro de esa caja roja.
Llegamos a un puntero nulo, por lo que podemos parar, y estamos hecho.
>> Y para que el marco púrpura es ahora-- en el parte superior de stack-- que es el marco activo,
pero se hace.
Si hemos llegado a un puntero nulo, para.
Nosotros no hacemos nada, no se puede liberar un puntero nulo,
que no malloc cualquiera espacio, y así hemos terminado.
Así que marco de función se destruye, y nosotros
resume-- recogemos donde lo dejamos con la siguiente más alta, lo cual
Es este marco azul oscuro aquí.
Así que tomamos justo donde lo dejamos.
Hemos suprimido el resto de la lista ya, por lo que ahora estamos
va a liberar a los nodos actuales.
Así que ahora podemos liberar este nodo, y ahora hemos llegado al final de la función.
Y para que marco de función se destruye, y nosotros recogemos en el azul claro.
>> Así que says-- ya he done-- suprimir el resto de la lista, por lo
liberar el nodo actual.
Y ahora el cuadro amarillo es volver a la cima de la pila.
Y así como ves, ahora estamos la destrucción de la lista de derecha a izquierda.
>> ¿Qué hubiera pasado, sin embargo, si hubiéramos hecho las cosas de manera equivocada?
Al igual que cuando intentamos para agregar un elemento.
Si mal estado de la cadena, en caso no nos conectamos los punteros
en el orden correcto, si liberado al primer elemento,
si nos liberamos de la cabeza de la lista, ahora
no hay manera de referirse a el resto de la lista.
Y así tendríamos todo huérfanos,
hubiéramos tenido lo que hay llama una pérdida de memoria.
Si usted recuerda de nuestro video en la asignación de memoria dinámica,
eso no es muy bueno.
>> Así que como ya he dicho, hay son varias operaciones
que tenemos que usar para trabajar con lista vinculada efectivamente.
Y te habrás dado cuenta omití uno, la eliminación de un solo elemento de una ligado
lista.
La razón por la que hice es que es en realidad un poco
difícil de pensar acerca de cómo eliminar un solo elemento de una individualmente
lista enlazada.
Tenemos que ser capaces de pasar por alto algo en la lista, que
significa que lleguemos a un nosotros point-- quieres borrar este node--
pero a fin de que sea así que no pierda ninguna información,
tenemos que conectar este nodo de aquí, aquí.
>> Así que probablemente hice mal desde una perspectiva visual.
Así que estamos en el comienzo de nuestra lista, estamos procediendo a través,
queremos eliminar este nodo.
Si nos limitamos a borrarlo, hemos roto la cadena.
Este nodo aquí se refiere a todo lo demás,
que contiene la cadena de aquí en adelante.
>> Así que lo que tenemos que hacer realidad después de llegar a este punto,
es que tenemos que dar un paso atrás uno, y conectar este nodo a través de este nodo,
así entonces podemos eliminar el uno en el centro.
Pero las listas por separado enlazados no hacen nos proporcionan una manera de ir hacia atrás.
Así que tenemos que mantener cualquiera dos punteros, y moverlos
especie de paso fuera, una detrás de la otra medida que avanzamos, o llegar a un punto
y luego enviar a través de otro puntero.
Y como se puede ver, puede ser un poco desordenado.
Afortunadamente, tenemos otra manera de resolver esto,
cuando hablamos de listas doblemente enlazadas.
>> Soy Doug Lloyd, esto es CS50.