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 encadeadas com extremidades duplas.
Enquanto a lista simples com uma única extremidade possui uma referência para o primeiro nó, a lista com extremidades duplas, referencia o primeiro e o último nó. Dessa maneira, nós podemos ter acesso tanto ao primeiro elemento da lista, quanto ao último, sendo que o último podemos inserir também dados no final. Entretanto, nós não excluímos elemento diretamente do final, somente pesquisando elemento por elemento, até chegar no último, como nas listas encadeadas com extremidade única. Isso ocorre, porque só podemos percorrer a lista da esquerda para a direita, sendo assim, se excluirmos o último, não conseguimos ter acesso ao anterior para indicar que o anterior será o último. Repare na imagem que as setas vão em uma única direção (esquerda para direita):
Para inserir um item na última posição:
1- Criamos um novo nó;
2- O objeto que era o último não aponta mais para Null e passa a apontar para o novo objeto;
3- O novo objeto irá apontar para null;
4- Por fim, nós tiramos o link do cabeça da lista apontando para o que era o último e apontamos para o que agora é o último.
A imagem irá facilitar a visualização:
Para acessar as outras operações acesse este link sobre as filas encadeadas com extremidade única, pois é a mesma ideia.
Quanto ao Big-O dessas operações, ficam da seguinte maneira:
Na inserção e exclusão do início e do final, será O(1) - constante. (Excelente performance).
Pesquisar, inserir e excluir um item específico, requer buscar os itens, o que resulta em uma notação O(n) - linear. Entretanto, na exclusão, não é necessário o remanejamento dos itens, como nos vetores.
Por fim, essa estrutura utiliza somente a memória que necessitar, podendo ser expandida de acordo com o aumento da lista, como nas listas simples com extremidades únicas.
Aqui está um algoritmo feito em python com a ideia de listas encadeadas com extremidades duplas.
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)