DEV Community

Mateus Costa
Mateus Costa

Posted on • Edited on

Um resumo sobre: listas duplamente encadeadas.

Para um melhor entendimento deste resumo, leia sobre lista encadeada simples, pois lá faço uma boa introdução sobre as listas encadeadas.
Aqui irei abordar sobre as listas duplamente encadeadas.

Fechando o tema de listas encadeadas, vou para este último tópico:

As listas encadeadas simples, possuem algumas limitações, por exemplo, quando percorremos este tipo de estrutura, ao avançarmos, nós não poderemos retroceder, pois o caminho delas são da esquerda para a direita, mas não percorrem da direita para a esquerda. As listas duplamente encadeadas, resolvem este problemas, uma vez que os nós apontam para o valor anterior e o próximo. Perceba a diferença entre elas.
Listas encadeadas com extremidades duplas:
Image description

Listas duplamente encadeadas:

Image description

Para inserir um elemento no início, nós iremos:
1- Criar um nó com o anterior igual a none;
2- Colocar o “próximo” do novo elemento vai apontar para o primeiro elemento (que será o segundo);
3- O antigo primeiro elemento, não aponta mais o “anterior” para o nulo, mas, sim, para o que será o primeiro elemento;
4- A cabeça da lista agora apontará para o novo elemento e não para o antigo.
Com essa imagem ficará mais claro:

Image description

Podemos também inserir um elemento no final da lista:
1- Criar um nó que o “próximo” aponta para nulo;
2- Apontar o anterior do novo para o elemento que era o último e agora será o penúltimo;
3- Cortamos a ligação do posterior do atual penúltimo com o nulo e ligamos ao atual último;
4- Retiramos o link que aponta o antigo último e colocamos ele apontando para o novo elemento.
Com a imagem ficará mais fácil a visualização:

Image description

Para excluir no início:
1- Colocamos o anterior da segunda posição apontando para o nulo,
2- Colocamos a referência “cabeça de lista” apontando para o segundo.

Image description

Para excluir no final da lista:
1- Apontar o “próximo” do penúltimo ao valor nulo;
2- Apontamos a referência do último ao nó penúltimo.

Image description

Excluir na posição:

1- Fazer pesquisa para saber qual elemento apagar (pode ser da direita para a esquerda ou da esquerda para a direita),
2- Apontar o próximo do anterior do atual para o próximo do atual,
3- Apontar o anterior do próximo do atual para o anterior do atual,
4- Lembrando que nenhum elemento é apagado em si, ele apenas desfaz as ligações que faz com que ele faça parte da lista.

Image description

Aqui está um algoritmo feito em python com a ideia de listas duplamente encadeadas, com inserção no início e no final, exclusão no início, no final e numa posição específica.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Top comments (0)