Um resumo sobre: listas duplamente encadeadas.
Tags: algorithms, python
Published: 2023-02-27 20:33:07

Para um melhor entendimento deste resumo, leia sobre [lista encadeada simples](https://dev.to/costamateus7/um-resumo-sobre-listas-encadeadas-simples-3lo6), 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4vhqa7enzb1275t17222.png)


**Listas duplamente encadeadas:**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4bf16mc2nki5j2f3lwvn.png)


Para **<u>inserir um elemento</u>** 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/et25ft7s691gngr4ac30.png)

Podemos também **<u>inserir um elemento</u>** 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5dq4sfqf32826muidrna.png)


Para **<u>excluir no início</u>**:
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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8yov8pnynw070sqqtom7.png)

Para **<u>excluir no final</u>** 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/taifom87hom3ke32zzwy.png)


**<u>Excluir na posição</u>**:

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u81pxsc7gf9yvd9bcy89.png)


[Aqui está](https://colab.research.google.com/drive/1E_T3Lf9XF1bgKsf8gdxNE6pqG97hUM4u?usp=sharing) 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](https://www.udemy.com/course/estrutura-de-dados-e-algoritmos-python-guia-completo/)