[Música tocando] DOUG LLOYD: Tudo bem. Então, se você acabou de terminar que vídeo em listas individualmente ligados pesaroso Eu deixei você fora em um pouco de um cliffhanger. Mas eu estou feliz que você está aqui para terminar a história de listas duplamente ligadas. 

Então, se você se lembrar de que o vídeo, nós falamos sobre como individualmente ligado Listas de fazer participar a nossa capacidade para lidar com informações em que o número de elementos ou o número de itens nas uma lista pode aumentar ou diminuir. Agora podemos lidar com algo como que, quando nós não poderíamos lidar com isso com matrizes. 

Mas eles sofrem de uma limitação crítica quais é que, com um ligado isoladamente lista, só podemos mover em uma única direção através da lista. E a única situação real onde que pode tornar-se um problema foi quando nós estávamos tentando excluir um único elemento. E nós nem sequer discutir como fazê-lo em uma lista isoladamente ligada em pseudocódigo. É certamente factível, mas ele pode ser um pouco de um aborrecimento. Então, se você encontrar-se em uma situação onde você está tentando excluir elementos únicos da lista ou ele vai ser exigido que você vai ser a exclusão elementos únicos de a lista, você pode querer considerar o uso de um ligado duplamente lista em vez de uma lista isoladamente ligado. Como as listas duplamente vinculadas permitem que você para mover ambos frente e para trás através da lista em vez de apenas para a frente através da lista-- apenas adicionando um elemento extra a nossa definição de estrutura para o nó de lista duplamente vinculada. 

Novamente, se você não está indo para ser exclusão elementos únicos do lista-- porque estamos adicionando um campo extra para a nossa estrutura definição, os próprios nós para listas duplamente ligadas vai ser maior. Eles vão levá -se mais bytes de memória. E por isso, se isso não é algo você vai precisar de fazer, você pode decidir que é Não vale a pena o trade off ter que passar o extra bytes de memória necessária Para obter uma lista duplamente vinculada se você não estiver vai ser apagando elementos individuais. Mas também é legal para outras coisas também. 

Então, como eu disse, nós apenas temos que adicionar um único campo para a nossa estrutura definition-- esta noção de um ponteiro anterior. Assim, com uma lista isoladamente ligado, nós tem o valor eo ponteiro Em seguida, assim que a lista duplamente vinculada apenas tem uma maneira de se mover para trás também. 

Agora, no individualmente ligado lista de vídeos, nós falamos sobre estes são cinco dos principais coisas que você precisa estar capaz de fazer para trabalhar com listas ligadas. E para a maioria destas, o facto que é uma lista duplamente vinculada não é realmente um grande salto. Nós ainda pode pesquisar por apenas em frente do início ao fim. Nós ainda podemos criar um nó de ar, praticamente da mesma maneira. Podemos eliminar listas bonita da mesma maneira também. As únicas coisas que são sutilmente diferentes, realmente, está inserindo novos nós na lista, e nós vamos finalmente falar sobre a exclusão um único elemento da lista bem. Mais uma vez, muito bonito os outros três, nós somos não vai falar sobre eles agora, porque eles são apenas ajustes muito menores sobre as idéias discutidas no vídeo lista isoladamente ligado. 

Então, vamos inserir um novo nó em uma lista duplamente vinculada. Nós conversamos sobre como fazer isso para listas isoladamente ligada, bem como, mas há um par de extras pega com listas duplamente ligadas. Estavam [? passando?] na cabeça da listar aqui e algum valor arbitrário, e nós queremos começar o novo chefe fora da lista desta função. É por isso que ele retorna uma estrela dllnode. Então, quais são os passos? Eles são, de novo, muito semelhante a listas ligadas individualmente- com uma adição adicional. Queremos aloca espaço para um novo nó e de verificação para ter certeza que é válido. Queremos preencher esse nó up com qualquer informação que quero colocar nele. A última coisa de que precisamos para o fazer-- extra coisa que precisamos fazer, rather-- é para corrigir o ponteiro Anterior do antigo chefe da lista. Lembre-se que, devido listas de duplamente vinculadas, podemos avançar e que backwards-- significa que cada nó realmente aponta a dois outros nós em vez de apenas um. E assim temos de corrigir o antigo chefe da lista para apontar para trás, para o novo chefe da a lista ligada, o que era algo nós não temos que fazer antes. E, como antes, nós apenas retornar um Ponteiro para o novo cabeça da lista. 

Então aqui está uma lista. Queremos inserir 12 nesta lista. Observe que o diagrama é um pouco diferente. Cada nó contém três fields-- de dados, e um ponteiro de seguida no vermelho, e um ponteiro anterior em azul. Nada vem antes do nó 15, pelo que a sua anterior ponteiro é nulo. É o início da lista. Não há nada antes dela. E nada vem depois do nó 10, e por isso é ponteiro seguida é nula também. 

Então, vamos adicionar 12 a esta lista. Precisamos [inaudível] espaço para o nó. Nós colocamos 12 dentro do mesmo. E então, novamente, temos de ser realmente cuidado para não quebrar a cadeia. Queremos reorganizar a ponteiros na ordem correta. E às vezes isso pode dizer-- como veremos particularmente com delete-- que temos algum ponteiros redundante, mas está tudo OK. 

Então, o que nós queremos fazer primeiro? Eu recomendaria o Coisas que você deve, provavelmente, fazer são para preencher os ponteiros dos 12 nó antes de tocar em qualquer outra pessoa. Então, o que é 12 vai apontar para o próximo? 15. O que vem antes de 12? Nenhuma coisa. Agora nós encheu o informação extra em 12 por isso tem Anterior, Próximo e valor. 

Agora podemos ter 15-- este adicional passo nós estávamos falando about-- nós pode ter 15 pontos de volta para 12. E agora nós podemos mover a cabeça de a lista encadeada também ser 12. Então é muito semelhante ao que estavam fazendo com listas individualmente ligados, excepto para o passo adicional de conectando o velho cabeça de lista volta para a nova cabeça da lista. 

Agora vamos finalmente apagar um nó de uma lista ligada. Então, digamos que temos alguma outra função que é encontrar um nó que deseja excluir e nos deu um ponteiro para exatamente o nó que deseja excluir. Nós nem sequer dizer o need-- cabeça ainda está globalmente declarado. Nós não precisamos de cabeça aqui. Tudo esta função está a fazer é que nós temos encontrado um ponteiro para exatamente o que nó quer se livrar de. Vamos livrar-se dele. É muito mais fácil com listas duplamente vinculada. First-- é realmente apenas um par de coisas. Nós só precisamos corrigir torno ponteiros dos nós de modo que eles Pular o nó que deseja excluir. E então podemos excluir esse nó. Então, novamente, estamos apenas passando por aqui. Nós aparentemente decidiram que queremos excluir o nó X. E, novamente, o que eu sou fazendo aqui-- pelo maneira-- é um processo geral para uma nó que está no meio. Há um par de caveats extras que você precisa considerar quando você está excluindo o início da lista ou o fim da lista. Há um par de especial casos de canto ao lidar com lá. 

Então, isso funciona para excluir qualquer nó no meio do que um lista-- tem um ponteiro legítimo para a frente e um ponteiro legítimo para trás, legítima ponteiro anterior e próxima. Novamente, se você está trabalhando com as extremidades, você precisa para lidar com os ligeiramente diferente, e nós não estamos indo para falar sobre isso agora. Mas você pode, provavelmente, descobrir o que precisa a ser feito apenas por assistir este vídeo. 

Então, nós temos isolado X. X é o nó que deseja excluir da lista. O que nós fazemos? Em primeiro lugar, precisamos reorganizar os ponteiros fora. Precisamos reorganizar 9 do próximo para saltar mais de 13 e apontam para 10-- que é o que acabamos de fazer. E também precisamos reorganizar 10 Anterior para apontar para 9 em vez de apontar para 13. 

Então, novamente, este foi o diagrama para começar. Esta foi a nossa cadeia. Precisamos saltar mais de 13, mas precisamos também preservar a integridade da lista. Não quer perder nenhum informação em ambas as direcções. Então, precisamos reorganizar os ponteiros cuidadosamente assim que nós não quebrar a cadeia em tudo. 

Assim, podemos dizer 9 Próximo ponteiro aponta para o mesmo lugar que treze Próximo ponteiro aponta agora. Porque nós somos, eventualmente, vai querer saltar mais de 13. Assim, onde quer 13 pontos seguinte, você quer nove para apontar lá em vez disso. Então é isso. E então onde quer que 13 pontos de volta para, o que vem antes de 13, queremos 10 para apontar para que, em vez de 13. Agora note, se você seguir as setas, podemos cair 13 sem realmente perder qualquer informação. Nós mantivemos a integridade da lista, movendo-se para a frente e para trás. E então nós podemos apenas sorte de limpá-lo um pouco puxando a lista juntos. Então, nós rearranjado o ponteiros em ambos os lados. E então nós libertou o X nó que continha 13, e nós não quebrar a cadeia. Por isso, fizemos boa. 

Nota final aqui em listas ligadas. Assim, ambos singly- e duplamente ligada listas, como vimos, suporte inserção realmente eficiente e eliminação de elementos. Você pode muito bem fazer lo em tempo constante. O que temos que fazer para eliminar um elemento apenas um segundo atrás? Nós mudamos um ponteiro. Nós nos mudamos outro ponteiro. Nós libertado x-- levou três operações. Sempre leva três operações para excluir que node-- para libertar um nó. 

Como é que vamos inserir? Bem, nós somos apenas sempre aderência no início se estamos inserindo de forma eficiente. Então, precisamos rearrange-- dependendo se é um singly- ou duplamente ligada lista, nós pode precisar fazer três ou no máximo quatro operações. Mas, novamente, é sempre três ou quatro. Não importa quantas elementos estão em nossa lista, é sempre três ou quatro operations-- assim como a eliminação é sempre três ou quatro operações. É tempo constante. Então, isso é realmente grande. 

Com matrizes, nós estávamos fazendo algo como ordenação por inserção. Você provavelmente recordar que a inserção tipo não é um algoritmo de tempo constante. É realmente muito caro. Então, isso é muito melhor para a inserção. Mas como eu mencionei no isoladamente ligado lista de vídeos, nós temos uma desvantagem aqui também, certo? Perdemos a capacidade de acessar aleatoriamente elementos. Nós não podemos dizer, eu quero elemento número quatro ou o número do elemento 10 de uma lista ligada Da mesma forma que pudermos fazer isso com uma matriz ou podemos apenas diretamente índice em elemento de nossa matriz. 

E assim tentar encontrar um um elemento em lista-- ligada se a pesquisa é importante-- pode agora ter tempo linear. Como a lista fica mais tempo, pode dar um passo adicional para cada elemento na lista do a fim de encontrar o que estamos procurando. Portanto, há trade-offs. Há um pouco de um pro e con elemento aqui. 

E listas duplamente vinculadas não o são último tipo de combinação de estrutura de dados que nós vamos falar sobre, levando todo o edifício básico blocos de montar um C. Porque, na verdade, nós podemos até mesmo fazer melhor do que isso para criar uma estrutura de dados que você pode ser capaz de pesquisar na constante de tempo demasiado. Mas mais sobre isso em outro vídeo. 

Eu sou Doug Lloyd. Este é CS50.