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:
Listas duplamente encadeadas:
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:
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:
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.
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.
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.
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)