[REPRODUCCIÓN DE MÚSICA] DOUG LLOYD: De acuerdo. Así que si usted acaba de terminar que de vídeo en las listas por separado vinculados sorry Te dejé en un poco de un cliffhanger. Pero me alegro de que estés aquí para terminar la historia de las listas doblemente enlazadas. 

Así que si usted recuerda de ese video, hablamos acerca de cómo ligado individualmente- listas hacen asistir a nuestra capacidad para hacer frente a la información donde el número de elementos o el número de artículos en una lista puede crecer o encogerse. Ahora podemos hacer frente a algo así como que, cuando no podíamos tratar con él con matrices. 

Pero ellos sufren de un limitación crítica que es que con vinculados por separado, una lista, podemos solamente siempre moverse en una sola dirección a través de la lista. Y la única situación real donde eso puede convertirse en un problema fue cuando estábamos tratando de eliminar un solo elemento. Y ni siquiera discutimos cómo hacerlo en una lista simplemente enlazada en pseudocódigo. Sin duda, es factible, pero que puede ser un poco complicado. Así que si usted se encuentra en una situación donde usted está tratando de eliminar elementos individuales de la lista o que va a ser necesario que se le borrando elementos individuales de la lista, es posible que desee considerar el uso ligada doblemente un lista en lugar de una lista simplemente enlazada. Porque las listas doblemente enlazadas, que permiten para mover hacia adelante y hacia atrás a través de la lista en lugar de justo delante a través de la películas-- sólo mediante la adición de un elemento extra a nuestra definición de la estructura para el nodo de la lista doblemente enlazada. 

Una vez más, si no vas a ser borrado de elementos individuales Del películas-- porque estamos añadiendo un campo adicional a nuestra estructura definición, los propios nodos para las listas doblemente enlazadas- van a ser más grande. Ellos van a tener hasta más bytes de memoria. Y por lo que si esto no es algo usted va a tener que hacer, usted puede decidir que es No vale la pena el trade off a tener que pasar el extra bytes de memoria necesarios para obtener una lista doblemente enlazada si no estás va a ser borrado de elementos individuales. Pero también son fresco para otras cosas también. 

Así como he dicho, sólo tenemos que añadir un solo campo para nuestra estructura definition-- esta noción de un puntero anterior. Así que con una lista simplemente enlazada, nos tener el valor y el puntero siguiente, por lo que la lista doblemente enlazada solo tiene una manera de mover hacia atrás también. 

Ahora en ligadas individualmente-la lista de vídeos, hablamos sobre estos están cinco de la cosas principales que necesita para ser capaz de hacer para trabajar con listas enlazadas. Y para la mayoría de ellos, el hecho de que se trata de una lista doblemente enlazada no es realmente un gran salto. Podemos todavía buscar a través de apenas avanzando desde el principio hasta el final. Todavía podemos crear un nodo de la nada, más o menos la misma manera. Podemos eliminar listas bastante de la misma manera también. Las únicas cosas que son sutilmente diferentes, Realmente, se inserta nuevos nodos en la lista, y finalmente hablaremos acerca de la eliminación un solo elemento de la lista también. Una vez más, más o menos los otros tres, que estamos no voy a hablar de ellos en este momento porque son justo ajustes muy de menor importancia en las ideas discutidas en la lista de vídeo simplemente enlazada. 

Así que vamos a insertar un nuevo nodo en una lista doblemente enlazada. Hablamos sobre hacer esto para listas simplemente enlazada, así, pero hay un par de adicional las capturas con las listas doblemente enlazadas. Fueron [? pasando?] en la cabeza de la enumerar aquí y un poco de valor arbitrario, y queremos que el nuevo jefe de la lista de esta función. Es por eso que vuelve una estrella dllnode. ¿Cuáles son los pasos? Ellos son, de nuevo, muy similar a las listas ligadas individualmente- con una adición extra. Queremos asigna espacio para un nuevo nodo y de verificación para asegurarse de que es válido. Queremos llenar ese nodo hasta con cualquier información que quiere poner en él. La última cosa que necesitamos hacer-- el cosa extra que tenemos que hacer, rather-- es fijar el puntero Anterior del antiguo jefe de la lista. Recuerde que debido listas de enlaces doblemente, podemos avanzar y backwards-- que significa que cada nodo señala en realidad a otros dos nodos en lugar de uno solo. Y así tenemos que arreglar el antiguo jefe de la lista apuntar hacia atrás para el nuevo jefe de la lista enlazada, que era algo que no teníamos que hacer antes. Y como antes, sólo volvemos un puntero a la nueva cabeza de la lista. 

Así que aquí está una lista. Queremos insertar 12 en esta lista. Observe que el diagrama es ligeramente diferente. Cada nodo contiene tres fields-- datos y un puntero Siguiente en rojo, y un puntero anterior en azul. Nada viene antes que el nodo 15, por lo que su puntero anterior es nulo. Es el principio de la lista. No hay nada antes. Y nada viene después de que el nodo 10 y por lo que es Siguiente puntero es nulo también. 

Así que vamos a añadir 12 a esta lista. Necesitamos [inaudible] espacio para el nodo. Ponemos 12 en el interior de la misma. Y, de nuevo, tenemos que ser muy cuidado de no romper la cadena. Queremos cambiar el punteros en el orden correcto. Y a veces eso puede decir-- como veremos en particular con delete-- que tenemos algunos punteros redundantes, pero eso está bien. 

Entonces, ¿qué es lo que queremos hacer primero? Yo recomendaría el Cosas que usted debe, probablemente, hacer son para llenar los punteros del 12 nodo antes de tocar a nadie más. Entonces, ¿qué está pasando 12 para señalar a continuación? 15. ¿Qué viene antes de los 12? Nada. Ahora hemos llenado el Información adicional en 12 por lo que tiene Anterior, Siguiente, y valor. 

Ahora podemos tener 15-- este accesorio paso que estábamos hablando sobre-- nos puede tener 15 puntos de nuevo a 12. Y ahora podemos mover la cabeza de la lista enlazada a ser también 12. Así que es bastante similar a lo que estaban haciendo con las listas simplemente enlazada, excepto por el paso adicional de que conecta el antiguo jefe de la lista respaldar a la nueva cabeza de la lista. 

Ahora vamos a por fin eliminar un nodo de una lista enlazada. Así que vamos a decir que tenemos alguna otra función que es encontrar un nodo que queremos eliminar y nos ha dado un puntero a exactamente el nodo que queremos eliminar. Ni siquiera need-- decimos la cabeza está todavía a nivel mundial declaró. No necesitamos la cabeza aquí. Toda esta función está haciendo es que hemos encontrado un puntero a exactamente el que el nodo quiere deshacerse de. Vamos a deshacerse de él. Es mucho más fácil con listas doblemente enlazada. Primero-- en realidad sólo un par de cosas. Sólo tenemos que fijar la rodea punteros nodos 'para que se saltan más el nodo que desea eliminar. Y entonces podemos eliminar ese nodo. Así que de nuevo, sólo vamos por aquí. Aparentemente Hemos decidido que queremos eliminar el nodo X. Y de nuevo, lo que estoy haciendo aquí-- por el manera-- es un caso general de una nodo que se encuentra en el medio. Hay un par de advertencias adicionales que usted que considerar cuando se está borrando el principio de la lista o el final de la lista. Hay un par de especiales casos de esquina para hacer frente a allí. 

Así que esto funciona para borrar cualquier nodo en el medio de la que películas-- tiene un puntero legítima hacia adelante y un puntero legítima hacia atrás, legítimo puntero anterior y siguiente. Una vez más, si usted está trabajando con los extremos, que necesario para manejar los ligeramente diferente, y nosotros no vamos a hablar de eso ahora. Pero usted puede probablemente averiguar lo que necesita que hacer con sólo mirar este video. 

Así que nos hemos aislado X. X es el nodo queremos eliminar de la lista. ¿Qué hacemos? En primer lugar, tenemos que reorganizar los punteros fuera. Tenemos que reorganizar 9 del próximo para saltar más de 13 y apuntan a 10-- que es lo que acabamos de hacer. Y también tenemos que reorganizar 10 Anterior para señalar a 9 en lugar de apuntar a 13. 

Así que de nuevo, esta fue la diagrama para empezar. Esta fue nuestra cadena. Tenemos que saltar sobre 13, pero necesitamos también preservar la integridad de la lista. No queremos perder ninguna información en cualquier dirección. Así que tenemos que reordenar los punteros cuidadosamente por lo que no rompamos la cadena en absoluto. 

Así que podemos decir de 9 Siguiente puntero apunta al mismo lugar que de los trece Siguiente puntero apunta ahora. Porque somos el tiempo va a querer saltar sobre 13. Así que donde quiera 13 puntos siguiente, quieren nueve a punto no lugar. Así que eso es todo. Y a continuación, siempre que sea 13 puntos atrás a, lo que viene antes de los 13, queremos señalar 10 para que en lugar de 13. Ahora note, si usted sigue las flechas, que pueden caer 13 sin llegar a perder la información. Hemos mantenido la integridad de la lista, moviéndose hacia adelante y hacia atrás. Y entonces podemos sólo una especie de limpiarlo un poco tirando de la lista juntos. Así que reorganizó la punteros a cada lado. Y entonces nos liberamos X el nodo que contenía 13, y no nos rompemos la cadena. Así lo hicimos bien. 

Nota final aquí en listas enlazadas. Así pues, tanto singly- y doblemente enlazada listas, como hemos visto, apoyo inserción realmente eficiente y cancelación de sus elementos. Usted puede casi hacer a tiempo constante. ¿Qué teníamos que hacer para eliminar un elemento sólo un segundo atrás? Nos mudamos de un puntero. Nos mudamos otro puntero. Nos liberamos X-- tomó tres operaciones. Siempre lleva tres operaciones a eliminar esa node-- para liberar a un nodo. 

¿Cómo nos insertamos? Bueno, estamos simplemente siempre viradas en el comienzo si estamos insertando de manera eficiente. Así que tenemos que rearrange-- dependiendo de si se trata de un singly- o doblemente enlazada lista, puede ser que tenga que hacer de tres o max cuatro operaciones. Pero, de nuevo, siempre es tres o cuatro. No importa cuántos elementos están en nuestra lista, siempre tres o cuatro operations-- al igual que la eliminación es siempre tres o cuatro operaciones. Es tiempo constante. Así que eso es realmente genial. 

Con los arreglos, que estábamos haciendo algo así como la ordenación por inserción. Usted probablemente recordará que la inserción especie no es un algoritmo de tiempo constante. En realidad es bastante caro. Así que esto es mucho mejor para la inserción. Pero como he mencionado en el individualmente ligada lista de vídeos, tenemos una desventaja aquí también, ¿verdad? Hemos perdido la capacidad de acceder aleatoriamente elementos. No podemos decir, quiero elemento número cuatro o el elemento número 10 de una lista enlazada de la misma manera que podemos hacer eso con una matriz o podemos simplemente directamente índice en el elemento de nuestra matriz. 

Y así, tratando de encontrar una elemento de una películas-- vinculados si la búsqueda es important-- Ahora puede tomar tiempo lineal. Como la lista se alarga, se podría dar un paso adicional para cada elemento en la lista de Para encontrar lo que estamos buscando. Así que no hay compensaciones. Hay un poco de un profesional y el elemento aire aquí. 

Y las listas doblemente enlazadas, no la hay último tipo de estructura de datos de combinación que vamos a hablar, teniendo todo el edificio básico bloques de C una armando. Porque, de hecho, podemos incluso algo mejor que esto para crear una estructura de datos que usted podría ser capaz de buscar a través de en tiempo constante también. Pero más sobre esto en otro video. 

Soy Doug Lloyd. Esto es CS50.