Listas Encadeadas

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

LinkedLists: O que acontece por trás da interface

Documentação oficial

原文链接：Listas Encadeadas