1 00:00:00,000 --> 00:00:03,381 >> [REPRODUCCIÓN DE MÚSICA] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: De acuerdo. 4 00:00:05,520 --> 00:00:07,860 Así que si usted acaba de terminar que de vídeo en las listas por separado vinculados sorry 5 00:00:07,860 --> 00:00:09,568 Te dejé en un poco de un cliffhanger. 6 00:00:09,568 --> 00:00:12,790 Pero me alegro de que estés aquí para terminar la historia de las listas doblemente enlazadas. 7 00:00:12,790 --> 00:00:15,250 >> Así que si usted recuerda de ese video, hablamos 8 00:00:15,250 --> 00:00:18,500 acerca de cómo ligado individualmente- listas hacen asistir a nuestra capacidad 9 00:00:18,500 --> 00:00:22,090 para hacer frente a la información donde el número de elementos 10 00:00:22,090 --> 00:00:24,442 o el número de artículos en una lista puede crecer o encogerse. 11 00:00:24,442 --> 00:00:26,400 Ahora podemos hacer frente a algo así como que, cuando 12 00:00:26,400 --> 00:00:28,310 no podíamos tratar con él con matrices. 13 00:00:28,310 --> 00:00:30,560 >> Pero ellos sufren de un limitación crítica que 14 00:00:30,560 --> 00:00:33,790 es que con vinculados por separado, una lista, podemos solamente siempre moverse 15 00:00:33,790 --> 00:00:36,200 en una sola dirección a través de la lista. 16 00:00:36,200 --> 00:00:39,010 Y la única situación real donde eso puede convertirse en un problema 17 00:00:39,010 --> 00:00:41,250 fue cuando estábamos tratando de eliminar un solo elemento. 18 00:00:41,250 --> 00:00:46,000 Y ni siquiera discutimos cómo hacerlo en una lista simplemente enlazada en pseudocódigo. 19 00:00:46,000 --> 00:00:48,797 Sin duda, es factible, pero que puede ser un poco complicado. 20 00:00:48,797 --> 00:00:50,630 Así que si usted se encuentra en una situación donde 21 00:00:50,630 --> 00:00:53,175 usted está tratando de eliminar elementos individuales de la lista 22 00:00:53,175 --> 00:00:55,430 o que va a ser necesario que se le borrando 23 00:00:55,430 --> 00:00:57,970 elementos individuales de la lista, es posible que desee 24 00:00:57,970 --> 00:01:02,090 considerar el uso ligada doblemente un lista en lugar de una lista simplemente enlazada. 25 00:01:02,090 --> 00:01:06,320 Porque las listas doblemente enlazadas, que permiten para mover hacia adelante y hacia atrás 26 00:01:06,320 --> 00:01:09,340 a través de la lista en lugar de justo delante a través de la películas-- 27 00:01:09,340 --> 00:01:13,950 sólo mediante la adición de un elemento extra a nuestra definición de la estructura 28 00:01:13,950 --> 00:01:16,690 para el nodo de la lista doblemente enlazada. 29 00:01:16,690 --> 00:01:19,770 >> Una vez más, si no vas a ser borrado de elementos individuales 30 00:01:19,770 --> 00:01:24,810 Del películas-- porque estamos añadiendo un campo adicional a nuestra estructura 31 00:01:24,810 --> 00:01:28,340 definición, los propios nodos para las listas doblemente enlazadas- 32 00:01:28,340 --> 00:01:29,550 van a ser más grande. 33 00:01:29,550 --> 00:01:31,600 Ellos van a tener hasta más bytes de memoria. 34 00:01:31,600 --> 00:01:34,160 Y por lo que si esto no es algo usted va a tener que hacer, 35 00:01:34,160 --> 00:01:36,300 usted puede decidir que es No vale la pena el trade off 36 00:01:36,300 --> 00:01:39,360 a tener que pasar el extra bytes de memoria necesarios 37 00:01:39,360 --> 00:01:43,940 para obtener una lista doblemente enlazada si no estás va a ser borrado de elementos individuales. 38 00:01:43,940 --> 00:01:46,760 Pero también son fresco para otras cosas también. 39 00:01:46,760 --> 00:01:51,260 >> Así como he dicho, sólo tenemos que añadir un solo campo para nuestra estructura 40 00:01:51,260 --> 00:01:55,360 definition-- esta noción de un puntero anterior. 41 00:01:55,360 --> 00:01:58,620 Así que con una lista simplemente enlazada, nos tener el valor y el puntero siguiente, 42 00:01:58,620 --> 00:02:02,850 por lo que la lista doblemente enlazada solo tiene una manera de mover hacia atrás también. 43 00:02:02,850 --> 00:02:04,960 >> Ahora en ligadas individualmente-la lista de vídeos, hablamos 44 00:02:04,960 --> 00:02:07,210 sobre estos están cinco de la cosas principales que necesita para ser 45 00:02:07,210 --> 00:02:09,449 capaz de hacer para trabajar con listas enlazadas. 46 00:02:09,449 --> 00:02:12,880 Y para la mayoría de ellos, el hecho de que se trata de una lista doblemente enlazada 47 00:02:12,880 --> 00:02:14,130 no es realmente un gran salto. 48 00:02:14,130 --> 00:02:17,936 Podemos todavía buscar a través de apenas avanzando desde el principio hasta el final. 49 00:02:17,936 --> 00:02:20,810 Todavía podemos crear un nodo de la nada, más o menos la misma manera. 50 00:02:20,810 --> 00:02:23,591 Podemos eliminar listas bastante de la misma manera también. 51 00:02:23,591 --> 00:02:25,340 Las únicas cosas que son sutilmente diferentes, 52 00:02:25,340 --> 00:02:28,970 Realmente, se inserta nuevos nodos en la lista, 53 00:02:28,970 --> 00:02:33,722 y finalmente hablaremos acerca de la eliminación un solo elemento de la lista también. 54 00:02:33,722 --> 00:02:35,430 Una vez más, más o menos los otros tres, que estamos 55 00:02:35,430 --> 00:02:37,888 no voy a hablar de ellos en este momento porque son justo 56 00:02:37,888 --> 00:02:43,920 ajustes muy de menor importancia en las ideas discutidas en la lista de vídeo simplemente enlazada. 57 00:02:43,920 --> 00:02:46,292 >> Así que vamos a insertar un nuevo nodo en una lista doblemente enlazada. 58 00:02:46,292 --> 00:02:48,750 Hablamos sobre hacer esto para listas simplemente enlazada, así, 59 00:02:48,750 --> 00:02:52,020 pero hay un par de adicional las capturas con las listas doblemente enlazadas. 60 00:02:52,020 --> 00:02:55,280 Fueron [? pasando?] en la cabeza de la enumerar aquí y un poco de valor arbitrario, 61 00:02:55,280 --> 00:02:58,600 y queremos que el nuevo jefe de la lista de esta función. 62 00:02:58,600 --> 00:03:01,414 Es por eso que vuelve una estrella dllnode. 63 00:03:01,414 --> 00:03:02,330 ¿Cuáles son los pasos? 64 00:03:02,330 --> 00:03:04,496 Ellos son, de nuevo, muy similar a las listas ligadas individualmente- 65 00:03:04,496 --> 00:03:05,670 con una adición extra. 66 00:03:05,670 --> 00:03:08,900 Queremos asigna espacio para un nuevo nodo y de verificación para asegurarse de que es válido. 67 00:03:08,900 --> 00:03:11,510 Queremos llenar ese nodo hasta con cualquier información que 68 00:03:11,510 --> 00:03:12,564 quiere poner en él. 69 00:03:12,564 --> 00:03:15,480 La última cosa que necesitamos hacer-- el cosa extra que tenemos que hacer, rather-- 70 00:03:15,480 --> 00:03:19,435 es fijar el puntero Anterior del antiguo jefe de la lista. 71 00:03:19,435 --> 00:03:21,310 Recuerde que debido listas de enlaces doblemente, 72 00:03:21,310 --> 00:03:23,110 podemos avanzar y backwards-- que 73 00:03:23,110 --> 00:03:27,080 significa que cada nodo señala en realidad a otros dos nodos en lugar de uno solo. 74 00:03:27,080 --> 00:03:29,110 Y así tenemos que arreglar el antiguo jefe de la lista 75 00:03:29,110 --> 00:03:32,151 apuntar hacia atrás para el nuevo jefe de la lista enlazada, que era algo 76 00:03:32,151 --> 00:03:33,990 que no teníamos que hacer antes. 77 00:03:33,990 --> 00:03:37,420 Y como antes, sólo volvemos un puntero a la nueva cabeza de la lista. 78 00:03:37,420 --> 00:03:38,220 >> Así que aquí está una lista. 79 00:03:38,220 --> 00:03:40,144 Queremos insertar 12 en esta lista. 80 00:03:40,144 --> 00:03:42,060 Observe que el diagrama es ligeramente diferente. 81 00:03:42,060 --> 00:03:47,710 Cada nodo contiene tres fields-- datos y un puntero Siguiente en rojo, 82 00:03:47,710 --> 00:03:50,170 y un puntero anterior en azul. 83 00:03:50,170 --> 00:03:54,059 Nada viene antes que el nodo 15, por lo que su puntero anterior es nulo. 84 00:03:54,059 --> 00:03:55,350 Es el principio de la lista. 85 00:03:55,350 --> 00:03:56,560 No hay nada antes. 86 00:03:56,560 --> 00:04:03,350 Y nada viene después de que el nodo 10 y por lo que es Siguiente puntero es nulo también. 87 00:04:03,350 --> 00:04:05,616 >> Así que vamos a añadir 12 a esta lista. 88 00:04:05,616 --> 00:04:08,070 Necesitamos [inaudible] espacio para el nodo. 89 00:04:08,070 --> 00:04:11,480 Ponemos 12 en el interior de la misma. 90 00:04:11,480 --> 00:04:14,840 Y, de nuevo, tenemos que ser muy cuidado de no romper la cadena. 91 00:04:14,840 --> 00:04:17,144 Queremos cambiar el punteros en el orden correcto. 92 00:04:17,144 --> 00:04:19,519 Y a veces eso puede decir-- como veremos en particular 93 00:04:19,519 --> 00:04:24,120 con delete-- que tenemos algunos punteros redundantes, pero eso está bien. 94 00:04:24,120 --> 00:04:25,750 >> Entonces, ¿qué es lo que queremos hacer primero? 95 00:04:25,750 --> 00:04:28,290 Yo recomendaría el Cosas que usted debe, probablemente, 96 00:04:28,290 --> 00:04:35,350 hacer son para llenar los punteros del 12 nodo antes de tocar a nadie más. 97 00:04:35,350 --> 00:04:38,640 Entonces, ¿qué está pasando 12 para señalar a continuación? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 ¿Qué viene antes de los 12? 100 00:04:42,430 --> 00:04:43,640 Nada. 101 00:04:43,640 --> 00:04:46,280 Ahora hemos llenado el Información adicional en 12 102 00:04:46,280 --> 00:04:49,320 por lo que tiene Anterior, Siguiente, y valor. 103 00:04:49,320 --> 00:04:53,505 >> Ahora podemos tener 15-- este accesorio paso que estábamos hablando sobre-- nos 104 00:04:53,505 --> 00:04:56,590 puede tener 15 puntos de nuevo a 12. 105 00:04:56,590 --> 00:04:59,634 Y ahora podemos mover la cabeza de la lista enlazada a ser también 12. 106 00:04:59,634 --> 00:05:02,550 Así que es bastante similar a lo que estaban haciendo con las listas simplemente enlazada, 107 00:05:02,550 --> 00:05:06,940 excepto por el paso adicional de que conecta el antiguo jefe de la lista 108 00:05:06,940 --> 00:05:09,810 respaldar a la nueva cabeza de la lista. 109 00:05:09,810 --> 00:05:12,170 >> Ahora vamos a por fin eliminar un nodo de una lista enlazada. 110 00:05:12,170 --> 00:05:14,350 Así que vamos a decir que tenemos alguna otra función que 111 00:05:14,350 --> 00:05:18,080 es encontrar un nodo que queremos eliminar y nos ha dado un puntero a exactamente 112 00:05:18,080 --> 00:05:19,710 el nodo que queremos eliminar. 113 00:05:19,710 --> 00:05:22,360 Ni siquiera need-- decimos la cabeza está todavía a nivel mundial declaró. 114 00:05:22,360 --> 00:05:23,590 No necesitamos la cabeza aquí. 115 00:05:23,590 --> 00:05:26,830 Toda esta función está haciendo es que hemos encontrado un puntero a exactamente el que el nodo 116 00:05:26,830 --> 00:05:28,090 quiere deshacerse de. 117 00:05:28,090 --> 00:05:28,940 Vamos a deshacerse de él. 118 00:05:28,940 --> 00:05:31,859 Es mucho más fácil con listas doblemente enlazada. 119 00:05:31,859 --> 00:05:33,650 Primero-- en realidad sólo un par de cosas. 120 00:05:33,650 --> 00:05:38,760 Sólo tenemos que fijar la rodea punteros nodos 'para que se saltan más 121 00:05:38,760 --> 00:05:40,240 el nodo que desea eliminar. 122 00:05:40,240 --> 00:05:43,484 Y entonces podemos eliminar ese nodo. 123 00:05:43,484 --> 00:05:45,150 Así que de nuevo, sólo vamos por aquí. 124 00:05:45,150 --> 00:05:49,625 Aparentemente Hemos decidido que queremos eliminar el nodo X. 125 00:05:49,625 --> 00:05:51,500 Y de nuevo, lo que estoy haciendo aquí-- por el manera-- 126 00:05:51,500 --> 00:05:54,580 es un caso general de una nodo que se encuentra en el medio. 127 00:05:54,580 --> 00:05:56,547 Hay un par de advertencias adicionales que usted 128 00:05:56,547 --> 00:05:59,380 que considerar cuando se está borrando el principio de la lista 129 00:05:59,380 --> 00:06:01,040 o el final de la lista. 130 00:06:01,040 --> 00:06:03,730 Hay un par de especiales casos de esquina para hacer frente a allí. 131 00:06:03,730 --> 00:06:07,960 >> Así que esto funciona para borrar cualquier nodo en el medio de la que películas-- 132 00:06:07,960 --> 00:06:11,550 tiene un puntero legítima hacia adelante y un puntero legítima hacia atrás, 133 00:06:11,550 --> 00:06:14,460 legítimo puntero anterior y siguiente. 134 00:06:14,460 --> 00:06:16,530 Una vez más, si usted está trabajando con los extremos, que 135 00:06:16,530 --> 00:06:18,500 necesario para manejar los ligeramente diferente, 136 00:06:18,500 --> 00:06:19,570 y nosotros no vamos a hablar de eso ahora. 137 00:06:19,570 --> 00:06:21,319 Pero usted puede probablemente averiguar lo que necesita 138 00:06:21,319 --> 00:06:24,610 que hacer con sólo mirar este video. 139 00:06:24,610 --> 00:06:28,910 >> Así que nos hemos aislado X. X es el nodo queremos eliminar de la lista. 140 00:06:28,910 --> 00:06:30,140 ¿Qué hacemos? 141 00:06:30,140 --> 00:06:32,800 En primer lugar, tenemos que reorganizar los punteros fuera. 142 00:06:32,800 --> 00:06:35,815 Tenemos que reorganizar 9 del próximo para saltar más de 13 143 00:06:35,815 --> 00:06:38,030 y apuntan a 10-- que es lo que acabamos de hacer. 144 00:06:38,030 --> 00:06:41,180 Y también tenemos que reorganizar 10 Anterior 145 00:06:41,180 --> 00:06:44,610 para señalar a 9 en lugar de apuntar a 13. 146 00:06:44,610 --> 00:06:46,490 >> Así que de nuevo, esta fue la diagrama para empezar. 147 00:06:46,490 --> 00:06:47,730 Esta fue nuestra cadena. 148 00:06:47,730 --> 00:06:51,027 Tenemos que saltar sobre 13, pero necesitamos también preservar 149 00:06:51,027 --> 00:06:52,110 la integridad de la lista. 150 00:06:52,110 --> 00:06:54,680 No queremos perder ninguna información en cualquier dirección. 151 00:06:54,680 --> 00:06:59,620 Así que tenemos que reordenar los punteros cuidadosamente 152 00:06:59,620 --> 00:07:02,240 por lo que no rompamos la cadena en absoluto. 153 00:07:02,240 --> 00:07:05,710 >> Así que podemos decir de 9 Siguiente puntero apunta al mismo lugar 154 00:07:05,710 --> 00:07:08,040 que de los trece Siguiente puntero apunta ahora. 155 00:07:08,040 --> 00:07:10,331 Porque somos el tiempo va a querer saltar sobre 13. 156 00:07:10,331 --> 00:07:13,750 Así que donde quiera 13 puntos siguiente, quieren nueve a punto no lugar. 157 00:07:13,750 --> 00:07:15,200 Así que eso es todo. 158 00:07:15,200 --> 00:07:20,370 Y a continuación, siempre que sea 13 puntos atrás a, lo que viene antes de los 13, 159 00:07:20,370 --> 00:07:24,800 queremos señalar 10 para que en lugar de 13. 160 00:07:24,800 --> 00:07:29,290 Ahora note, si usted sigue las flechas, que pueden caer 13 161 00:07:29,290 --> 00:07:32,380 sin llegar a perder la información. 162 00:07:32,380 --> 00:07:36,002 Hemos mantenido la integridad de la lista, moviéndose hacia adelante y hacia atrás. 163 00:07:36,002 --> 00:07:38,210 Y entonces podemos sólo una especie de limpiarlo un poco 164 00:07:38,210 --> 00:07:40,930 tirando de la lista juntos. 165 00:07:40,930 --> 00:07:43,270 Así que reorganizó la punteros a cada lado. 166 00:07:43,270 --> 00:07:46,231 Y entonces nos liberamos X el nodo que contenía 13, 167 00:07:46,231 --> 00:07:47,480 y no nos rompemos la cadena. 168 00:07:47,480 --> 00:07:50,980 Así lo hicimos bien. 169 00:07:50,980 --> 00:07:53,000 >> Nota final aquí en listas enlazadas. 170 00:07:53,000 --> 00:07:55,990 Así pues, tanto singly- y doblemente enlazada listas, como hemos visto, 171 00:07:55,990 --> 00:07:58,959 apoyo inserción realmente eficiente y cancelación de sus elementos. 172 00:07:58,959 --> 00:08:00,750 Usted puede casi hacer a tiempo constante. 173 00:08:00,750 --> 00:08:03,333 ¿Qué teníamos que hacer para eliminar un elemento sólo un segundo atrás? 174 00:08:03,333 --> 00:08:04,440 Nos mudamos de un puntero. 175 00:08:04,440 --> 00:08:05,920 Nos mudamos otro puntero. 176 00:08:05,920 --> 00:08:07,915 Nos liberamos X-- tomó tres operaciones. 177 00:08:07,915 --> 00:08:14,500 Siempre lleva tres operaciones a eliminar esa node-- para liberar a un nodo. 178 00:08:14,500 --> 00:08:15,280 >> ¿Cómo nos insertamos? 179 00:08:15,280 --> 00:08:17,280 Bueno, estamos simplemente siempre viradas en el comienzo 180 00:08:17,280 --> 00:08:19,400 si estamos insertando de manera eficiente. 181 00:08:19,400 --> 00:08:21,964 Así que tenemos que rearrange-- dependiendo de si se trata de 182 00:08:21,964 --> 00:08:24,380 un singly- o doblemente enlazada lista, puede ser que tenga que hacer de tres 183 00:08:24,380 --> 00:08:26,824 o max cuatro operaciones. 184 00:08:26,824 --> 00:08:28,365 Pero, de nuevo, siempre es tres o cuatro. 185 00:08:28,365 --> 00:08:30,531 No importa cuántos elementos están en nuestra lista, 186 00:08:30,531 --> 00:08:33,549 siempre tres o cuatro operations-- al igual que la eliminación es siempre 187 00:08:33,549 --> 00:08:35,320 tres o cuatro operaciones. 188 00:08:35,320 --> 00:08:36,919 Es tiempo constante. 189 00:08:36,919 --> 00:08:38,169 Así que eso es realmente genial. 190 00:08:38,169 --> 00:08:40,620 >> Con los arreglos, que estábamos haciendo algo así como la ordenación por inserción. 191 00:08:40,620 --> 00:08:44,739 Usted probablemente recordará que la inserción especie no es un algoritmo de tiempo constante. 192 00:08:44,739 --> 00:08:46,030 En realidad es bastante caro. 193 00:08:46,030 --> 00:08:48,840 Así que esto es mucho mejor para la inserción. 194 00:08:48,840 --> 00:08:51,840 Pero como he mencionado en el individualmente ligada lista de vídeos, 195 00:08:51,840 --> 00:08:54,030 tenemos una desventaja aquí también, ¿verdad? 196 00:08:54,030 --> 00:08:57,580 Hemos perdido la capacidad de acceder aleatoriamente elementos. 197 00:08:57,580 --> 00:09:02,310 No podemos decir, quiero elemento número cuatro o el elemento número 10 de una lista enlazada 198 00:09:02,310 --> 00:09:04,990 de la misma manera que podemos hacer eso con una matriz 199 00:09:04,990 --> 00:09:08,630 o podemos simplemente directamente índice en el elemento de nuestra matriz. 200 00:09:08,630 --> 00:09:10,930 >> Y así, tratando de encontrar una elemento de una películas-- vinculados 201 00:09:10,930 --> 00:09:15,880 si la búsqueda es important-- Ahora puede tomar tiempo lineal. 202 00:09:15,880 --> 00:09:18,330 Como la lista se alarga, se podría dar un paso adicional 203 00:09:18,330 --> 00:09:22,644 para cada elemento en la lista de Para encontrar lo que estamos buscando. 204 00:09:22,644 --> 00:09:23,560 Así que no hay compensaciones. 205 00:09:23,560 --> 00:09:25,780 Hay un poco de un profesional y el elemento aire aquí. 206 00:09:25,780 --> 00:09:29,110 >> Y las listas doblemente enlazadas, no la hay último tipo de estructura de datos de combinación 207 00:09:29,110 --> 00:09:32,840 que vamos a hablar, teniendo todo el edificio básico 208 00:09:32,840 --> 00:09:34,865 bloques de C una armando. 209 00:09:34,865 --> 00:09:37,900 Porque, de hecho, podemos incluso algo mejor que esto 210 00:09:37,900 --> 00:09:41,970 para crear una estructura de datos que usted podría ser capaz de buscar a través de 211 00:09:41,970 --> 00:09:43,360 en tiempo constante también. 212 00:09:43,360 --> 00:09:46,080 Pero más sobre esto en otro video. 213 00:09:46,080 --> 00:09:47,150 >> Soy Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Esto es CS50. 215 00:09:49,050 --> 00:09:50,877