[Música tocando] Doug LLOYD: Todo ben. Entón, se acaba de rematar que vídeo en listas individualmente ligados pesaroso Eu deixei vostede fóra nun pouco dun cliffhanger. Pero eu estou feliz que está aquí para rematar a historia de listas dobremente ligadas. 

Entón, se lembrar de que o vídeo, falamos sobre como individualmente conectado Listas de facer participar a nosa capacidade para xestionar información en que o número de elementos ou o número de elementos nas unha lista pode aumentar ou diminuír. Agora podemos xestionar algo así como que, cando non poderiamos tratar con isto con matrices. 

Pero padecen unha limitación crítica que é que, cun conectado illadamente lista, só podemos mover nunha única dirección a través da lista. E a única situación real onde que pode chegar a ser un problema foi cando estabamos intentando eliminar un único elemento. E nós nin sequera discutir como facelo nunha lista illadamente ligada en pseudocódigo. É certamente factible, pero pode ser un pouco de un problema. Entón, se atopa-se nunha situación onde estás eliminar elementos únicos da lista ou que vai ser esixido que vai ser a exclusión elementos únicos de a lista, pode querer considerar o uso dun conectado dobremente lista en lugar dunha lista illadamente conectado. Como as listas dobremente vinculadas permiten que para mover ambos adiante e cara atrás a través da lista no canto de só para adiante a través da lista-- só engadindo un elemento extra a nosa definición de estrutura ao nó de lista dobremente vinculada. 

De novo, se non está indo a ser exclusión elementos únicos do lista-- porque estamos engadindo un campo extra para a nosa estrutura definición, os propios nós para listas dobremente ligadas será maior. Eles van leva Se máis bytes de memoria. E por iso, se iso non é algo vai ter facer, pode decidir que é Non paga a pena o trade off ter que pasar o extra bytes de memoria Para obter unha lista dobremente vinculada se non está será apagando elementos individuais. Pero tamén é legal para outras cousas tamén. 

Entón, como dixen, nós só temos que engadir un único campo para a nosa estrutura definition-- esta noción dun punteiro anterior. Así, con unha lista illadamente conectado, nós ten o valor eo punteiro Logo así que a lista dobremente vinculada só ten un xeito de moverse cara atrás tamén. 

Agora, no individualmente conectado lista de vídeos, falamos sobre estes son cinco dos principais cousas que ten que estar capaz de facer para traballar con listas ligadas. E para a maioría destas, o feito que é unha lista dobremente vinculada non é realmente un gran salto. Aínda pode buscar por só fronte do principio ao final. Aínda os podemos crear un nodo aire, practicamente do mesmo xeito. Podemos eliminar listas fermosa do mesmo xeito tamén. As únicas cousas que son sutilmente diferentes, realmente, está introducindo novos nós na lista, e nós imos rematar falar da exclusión un único elemento da lista ben. Unha vez máis, moi bonito os outros tres, somos non vai falar sobre eles agora, porque son só axustes moito menores sobre as ideas discutidas no video lista illadamente conectado. 

Entón, imos introducir un novo nodo nunha lista dobremente vinculada. Nós falamos sobre como facelo para listas illadamente ligada, así como, pero hai un par de extras colle con listas dobremente ligadas. Estamos [? pasando?] na cabeza da listar aquí e algún valor arbitrario, e queremos comezar o novo xefe fóra da lista desta función. É por iso que amosa unha estrela dllnode. Entón, cales son os pasos? Son, de novo, moi semellante a listas ligadas individualmente- con un engadido adicional. Queremos aloca espazo para un novo nó e de verificación para que seguro que é válido. Queremos encher ese nó up con toda a información que quero poñer nel. A última cousa que necesitamos para o fazer-- extra que necesitamos facer, rather-- é para corrixir o punteiro Anterior do antigo xefe da lista. Lembre que, debido listas de dobremente vinculadas, podemos avanzar e que backwards-- significa que cada nodo realmente apunta a dous outros nós no canto de só un. E así temos que corrixir o antigo xefe da lista para apuntar cara atrás, para o novo xefe da a lista ligada, o que era algo nós non temos que facer antes. E, como antes, nós só voltar un Punteiro do novo cabeza da lista. 

Entón aquí está a lista. Queremos introducir 12 desta lista. Teña en conta que o diagrama é un pouco diferente. Cada nodo contén tres fields-- de datos, e un punteiro de continuación no vermello, e un punteiro anterior en azul. Nada vén antes do nodo 15, polo que a súa anterior punteiro é nulo. É o inicio da lista. Non hai nada antes dela. E nada vén despois do nodo 10, e polo que é punteiro continuación é nula tamén. 

Entón, imos engadir 12 a esta lista. Necesitamos [inaudível] espazo para o no. Poñemos 12 dentro do mesmo. E entón, de novo, hai que ser realmente coidado de non romper a cadea. Queremos reorganizar a punteiros na orde correcta. E ás veces iso pode dizer-- como veremos particularmente con delete-- que temos algún punteiros redundante, pero está todo OK. 

Entón, o que queremos facer primeiro? Eu recomenda o Cousas que ten que, probablemente, facer son para cubrir os punteiros dos 12 nó antes de tocar en calquera outra persoa. Entón, o que é 12 vai apuntar ao seguinte? 15. O que vén antes de 12? Nada. Agora nós encheu o información extra en 12 polo que ten Anterior, Seguinte e valor. 

Agora podemos ter 15-- este adicional paso que estaban falando about-- nós pode ter 15 puntos ao 12. E agora podemos mover a cabeza de a lista encadeada ser 12. Entón é moi semellante ao que estaban facendo listas individualmente ligados, agás para o paso adicional de conectando o vello cabeza de lista volta para a nova cabeza da lista. 

Agora imos finalmente borrar un nó dunha lista ligada. Entón, digamos que temos algunha outra función que é atopar un nó que quere eliminar e nos deu un punteiro para exactamente o no que desexa eliminar. Nós nin sequera dicir o need-- cabeza aínda está globalmente declarado. Non necesitamos cabeza aquí. Todo esta función está a facer é que temos atopar un punteiro para o que nó quere se librar de. Imos librar-se del. É moito máis doado con listas dobremente vinculada. First-- é realmente só un par de cousas. Nós só necesitamos corrixir torno punteiros dos nós de xeito que xa Saltar o no que desexa eliminar. E entón podemos eliminar este nodo. Entón, de novo, estamos só pasando por aquí. Nós aparentemente decidiron que queremos eliminar o nodo X. E, de novo, o que eu son facendo aqui-- polo maneira-- é un proceso xeral para unha nó que está no medio. Hai un par de caveats extras que cómpre considerar cando está excluíndo o inicio da lista ou o fin da lista. Hai un par de especial casos de canto ao manexar alí. 

Entón, iso funciona para eliminar calquera nodo no medio do que un lista-- ten un punteiro lexítimo para adiante e un punteiro lexítimo para atrás, lexítima punteiro anterior e seguinte. De novo, se está a traballar coas extremidades, vostede precisa para xestionar os lixeiramente diferente, e nós non estamos indo a falar sobre iso agora. Pero pode, probabelmente, descubrir o que precisa por facer só por ver este vídeo. 

Entón, nós temos illado X. X é o nó que quere eliminar da lista. O que imos facer? En primeiro lugar, necesitamos reorganizar os punteiros fóra. Necesitamos reorganizar 9 do próximo para ir máis de 13 e apuntan 10-- que é o que acabamos de facer. E tamén necesitamos reorganizar 10 Anterior para ligar a 9 en vez de apuntar 13. 

Entón, de novo, este foi o diagrama para comezar. Esta foi a nosa cadea. Necesitamos ir máis de 13, pero precisamos tamén preservar a integridade da lista. Non quere perder ningún información en ambas as direccións. Entón, necesitamos reorganizar os punteiros coidadosamente así que non romper a cadea en todo. 

Así, podemos dicir 9 Seguinte punteiro apunta para o mesmo lugar que trece Seguinte punteiro apunta agora. Porque somos eventualmente Vai querer ir máis de 13. Así, onde queira 13 puntos seguinte, quere nove para apuntar alí no seu lugar. Entón é iso. E entón onde queira que 13 puntos de volta para o que vén antes de 13, queremos 10 para apuntar para que, no canto de 13. Agora conta, se seguir as frechas, podemos caer 13 sen realmente perder calquera información. Nós mantivemos a integridade da lista, movéndose para a adiante e cara atrás. E entón podemos só sorte de limpa-lo un pouco tirando a lista xuntos. Entón, nós rearranjado o punteiros en ambos os dous lados. E entón nós liberou o X nó que contiña 13, e non romper a cadea. Por iso, fixemos boa. 

Nota final aquí en listas ligadas. Así, ambos singly- e dobremente ligada listas, como vimos, soporte inserción realmente eficiente e eliminación de elementos. Pode moi ben facer lo en tempo constante. O que temos que facer para eliminar un elemento só un segundo atrás? Nós cambiamos un punteiro. Nós nos cambiamos outro punteiro. Nós liberado x-- levou tres operacións. Sempre leva tres operacións para eliminar que node-- para liberar un nó. 

Como é que imos introducir? Ben, nós somos só sempre adherencia a principios se estamos introducindo de forma eficiente. Entón, necesitamos rearrange-- dependendo se é un singly- ou dobremente ligada lista, nós pode ter facer tres ou como máximo catro operacións. Pero, de novo, sempre tres ou catro. Non importa cantas elementos están na nosa lista, sempre tres ou catro operations-- así como a eliminación sempre tres ou catro operacións. É tempo constante. Entón, iso é realmente grande. 

Con matrices, que estaban facendo algo así como ordenación por inserción. Probablemente recordar que a inserción tipo non é un algoritmo de tempo constante. É realmente moi caro. Entón, iso é moito mellor para a inserción. Pero como eu mencionen no illadamente conectado lista de vídeos, temos unha desvantaxe aquí tamén, non? Perdemos a capacidade de acceder ao azar elementos. Non podemos dicir, quero elemento número catro ou o número do elemento 10 dunha lista ligada Do mesmo xeito que podemos facelo con unha matriz ou podemos só directamente índice en elemento da nosa matriz. 

E así tentar atopar un un elemento en lista-- ligada a investigación é importante-- pode agora ter tempo lineal. Como a lista está máis tempo, pode dar un paso adicional para cada elemento da lista do a fin de atopar o que estamos buscando. Polo tanto, hai trade-offs. Hai un pouco de un pro e con elemento aquí. 

E listas dobremente vinculadas non o son último tipo de combinación de estrutura de datos que nós imos falar sobre, levando todo o edificio básico bloques de montar un C. Porque, en realidade, podemos incluso facer mellor que iso para crear unha estrutura de datos que pode ser capaz de buscar na constante de tempo demasiado. Pero máis sobre iso noutro vídeo. 

Eu son Doug Lloyd. Este é CS50.