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 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 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.
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:
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
Top comments (0)