DEV Community

loading...

Listas Encadeadas

ccunha profile image Carolina Cunha Updated on ・3 min read

Listas encadeadas ou listas ligadas são estruturas lineares para armazenamento de objetos do mesmo tipo. Esses objetos estão ligados uns nos outros através de ponteiros, que guardam a posição do próximo objeto da lista.

Essas listas podem ser de dois tipos:

  • Listas encadeadas simples: onde cada elemento tem armazenado o endereço de memória onde está localizado o próximo elemento da lista:

Listas encadeadas simples

  • Listas duplamente encadeadas: onde cada elemento tem armazenado o endereço de memória onde está localizando o anterior e o próximo elemento da lista:

Listas duplamente encadeadas

Listas Encadeadas no Java

No Java, a implementaçãos das listas encadeadas é feita através da coleção LinkedList, que é uma lista circular duplamente encadeada. Nesse tipo de lista, cada elemento é chamado de nó, e cada nó guarda em si, além do elemento, a posição do elemento anterior e a posição do elemento posterior.

Na memória, uma LinkedList não fica armazenada sequencialmente. Ela fica distribuída, por isso a importância de ser a posição dos elementos anteriores e posteriores em cada nó. O fato de estar distribuída na memória permite que a lista possa crescer durante a execução do programa de forma limitada apenas pela memória física disponível.

Exemplo de utilização de uma LinkedList

Pelo exemplo acima, vemos que a utilização de uma LinkedList é muito semelhante a utilização de um ArrayList. Então, qual seria a vantagem de utilizar uma LinkedList?

Performance! Se você precisa que sua lista tenha uma melhor performance na adição e/ou remoção de elementos, então você deve utilizar uma LinkedList! Mas por que? Porque a performance é melhor nos métodos add e remove?

Se estivermos falando de inserção/remoção no final ou no início da lista, é uma operação simples: após a criação do nó, será feita a atualização das posições nos elementos:

Operação de inserção de novo elemento no início de uma LinkedList

Se estivermos falando de inserção/remoção no meio da lista, antes da inserção ainda haverá a operação de busca do local onde deve ser inserido o elemento, então perde-se um pouco na performance nesse caso, porém devemos lembrar que o Java nesse caso escolhe o menor caminho a percorrer.

Porém, quando falamos de operações de busca de elementos específicos, a LinkedList se comporta como um ArrayList, ou seja: no pior caso, será necessário percorrer a lista toda.

Concluindo, os melhores indicativos de que se é um bom momento para usar uma LinkedList são:

  • Quando não serão necessários acessos a elementos de forma aleatória;
  • Quando serão efetuadas muitas operações de inserção/deleção de elementos;
  • Quando for necessário que o crescimento da lista seja dinâmico.

Bibliografia:

Essa desenvolvedora bacana aqui

Diferença entre ArrayList, Vector e LinkedList em Java

LinkedLists: O que acontece por trás da interface

Documentação oficial

Discussion

pic
Editor guide