Listas Encadeadas
Tags: java, datastructure, begginer
Published: 2020-08-04 10:59:44

---
title: Listas Encadeadas
published: true
description: Esse artigo tem o objetivo de introduzir as listas encadeadas e sua implementação no Java.
tags: #java #datastructure #begginer
---
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](https://dev-to-uploads.s3.amazonaws.com/i/fvq60dvsx0nz4x5z7isu.jpeg)

* 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](https://dev-to-uploads.s3.amazonaws.com/i/d3ukuj8niye6j3yr66uz.jpeg)

###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](https://dev-to-uploads.s3.amazonaws.com/i/lxjwg5osb9r0uou7wh46.png)

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](https://dev-to-uploads.s3.amazonaws.com/i/m3t3qfblywylg3m1fasw.png)

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](https://medium.com/@jillplatts/6-minute-beginners-guide-to-java-s-linked-list-data-structure-bb2fbcca81b1)

[Diferença entre ArrayList, Vector e LinkedList em Java](https://www.devmedia.com.br/diferenca-entre-arraylist-vector-e-linkedlist-em-java/29162)

[LinkedLists: O que acontece por trás da interface](https://www.devmedia.com.br/linkedlists-o-que-acontece-por-tras-da-interface/24613)

[Documentação oficial](https://docs.oracle.com/javase/10/docs/api/java/util/LinkedList.html)