Conhecendo a classe LinkedList do Java
Tags: java, linkedlist, programming, beginners
Published: 2022-11-01 14:09:00

Neste artigo apresentarei algumas características da classe **LinkedList**, também explanarei um pouco sobre seu funcionamento e farei algumas comparações entre a mesma e a classe **ArrayList**.  

Se você quiser saber mais sobre a classe **ArrayList**, escrevi um artigo sobre esse assunto e você poderá consultá-lo clicando [aqui](https://dev.to/yesminmarie/utilizacao-da-classe-arraylist-do-java-para-manipulacao-de-vetores-370m).

##Como funciona a classe LinkedList do Java?

Assim como **ArrayList**, a classe **LinkedList** também implementa a interface **List**. Veja no diagrama abaixo a hierarquia de interfaces e classes. As linhas cheias representam **“extends”** e as linhas pontilhadas **“implements”**:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m7tbdyw659vushagxmwa.png)

Sendo assim, os mesmos métodos disponíveis para **ArrayList** também estão disponíveis para **LinkedList**, mas implementados de forma diferente.

De forma distinta da classe ArrayList, que usa um array internamente, a classe **LinkedList** trabalha com **lista duplamente encadeada**. Seu funcionamento ocorre da seguinte forma: cada elemento da lista fica armazenado em um nó e cada nó possui dois ponteiros, um localizado à esquerda e outro à direita. Esses ponteiros guardam a posição do nó anterior e do nó posterior.

A imagem a seguir ilustra como é um nó do **LinkedList**:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xqp5vu9pdb3dqmtc0hdx.png)

A próxima imagem mostra o funcionamento de uma lista duplamente encadeada, onde cada nó aponta para o elemento anterior e posterior. Veja que o primeiro nó não possui posição para o elemento anterior (**null**). Assim como último elemento não possui posição para o próximo.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qu9e5mdre1mza5ozjymk.png)

Dessa maneira, diferentemente do ArrayList, que armazena os elementos de forma consecutiva (um ao lado do outro), no **LinkedList** os elementos ficam espalhados na memória, mas cada um deles sabe quem é seu antecessor e seu sucessor por meio dos ponteiros que fazem as conexões entre eles. 

Sendo assim, adicionar ou remover elementos no **LinkedList** é mais rápido do que no **ArrayList**. Isso porque na lista encadeada, não há o deslocamento dos elementos após cada operação de adição e remoção, bastando apenas alterar as referências dos ponteiros, indicando quem passou a ser o elemento anterior e posterior.

##Como funciona a adição de elementos no LinkedList?

Como exemplo, vamos supor que temos um LinkedList onde cada nó armazena os seguinte nomes:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7hsxquwu6ipmx7h6fubs.png)

Vamos adicionar um novo elemento contendo o nome “Rafael” após o índice 1, que contém o nome “Pedro” e que está apontando para “Maria” (índice 2):


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qvjgc96nwc6b710866oc.png)

Repare que foi apenas necessário mudar os apontamentos dos nós:

- “Pedro”, que antes apontava para “Maria”, agora está apontando para “Rafael”. 
- “Maria”, que antes apontava para “Pedro” como seu antecessor, agora passa a apontar para “Rafael”. 
- “Rafael” agora se tornou o elemento de índice 2,  passando a apontar para “Pedro” como seu antecessor, e “Maria” como sucessor. 
- “Maria”, que antes era o elemento de índice 2, agora passa a ser o índice 3. 
- “João” agora ocupa o índice 4.

##Como funciona a remoção de elementos no LinkedList?

Usando como exemplo a lista abaixo, vamos remover o elemento que contém o nome “Pedro”:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qvjgc96nwc6b710866oc.png)

Lista após a remoção:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fn8ge3docs5t19gvertg.png)


Veja que agora “Ana” passa a apontar para “Rafael” e vice-versa. “Rafael” passa a ter o índice 1, “Maria” agora está no índice 2 e “João” no índice 3. O Garbage Collector do Java se encarrega de liberar a memória que o elemento removido ocupava.

##Outros aspectos que diferem LinkedList de ArrayList

Até aqui, vimos que tanto adicionar quanto remover elementos são tarefas que o **LinkedList** realiza com mais eficiência do que o **ArrayList**. No entanto, o **LinkedList** é mais lento para acessar elementos da lista. Se por exemplo, quiséssemos acessar a posição 10, teríamos que percorrer desde o início até a posição que queremos.

Outro ponto que difere um **ArrayList** de um **LinkedList** é que neste, não é possível passar a capacidade inicial por parâmetro no construtor quando o inicializamos. Como o **LinkedList** se baseia no modelo de lista encadeada, o espaço em memória não é alocado antes dos itens serem inseridos e sua capacidade inicial é zero. 

No entanto, assim como no **ArrayList**, podemos criar uma lista a partir de outra já existente, passando a lista base por parâmetro no construtor. Exemplo:

```java
LinkedList<String> lista = new LinkedList<>();
lista.add("Maria");
lista.add("Pedro");
LinkedList<String> novaLista = new LinkedList<>(lista);
System.out.println(novaLista);
```
##Formas de Inicializar um LinkedList

Assim como no **ArrayList**, podemos utilizar o polimorfismo e declarar uma referência da interface **List** e instanciar a classe **LinkedList**:

```java
List<String> lista = new LinkedList<>();
```

Mas se quisermos utilizar os métodos específicos do **LinkedList**, temos que declarar uma referência da própria classe LinkedList:

```java
LinkedList<String> lista = new LinkedList<>();
```
##Métodos específicos do LinkedList

Além dos métodos implementados da interface List, como **add(item), remove(posição), set(posição, item), get(posição)**, dentre outros. Também temos alguns métodos específicos que a classe LinkedList implementa da interface **Deque**. A seguir estão listados alguns deles:

- **addFirst(item)** -> adiciona um elemento no início da lista;
- **addLast(item)** -> adiciona um elemento no final da lista;
- **getFirst()** -> retorna o primeiro elemento da lista;
- **getLast()** -> retorna o último elemento da lista;
- **removeFirst()** -> remove o primeiro elemento da lista e o retorna;
- **removeLast()** -> remove o último elemento da lista e o retorna;

##Exemplos de como utilizar LinkedList

Este primeiro exemplo é igual a outro que inseri no artigo que escrevi sobre [ArrayList](https://dev.to/yesminmarie/utilizacao-da-classe-arraylist-do-java-para-manipulacao-de-vetores-370m). Estou colocando neste artigo também para mostrar que podemos usar os mesmos métodos que estão disponíveis para **ArrayList**, pois ambos implementam a interface **List**.

```java
import java.util.Iterator;
import java.util.LinkedList;

public class TesteLinkedList {
    public static void main(String[] args) {

        // 1) Primeiro, vamos instanciar uma LinkedList;
        LinkedList<String> cidades = new LinkedList<>();

        // 2) Depois, vamos adicionar cinco cidades
        // usando o método add(item);
        cidades.add("São Paulo");
        cidades.add("Rio de Janeiro");
        cidades.add("Recife");
        cidades.add("Manaus");
        cidades.add("Curitiba");

        // 3) Percorreremos a lista e exibiremos
        // essas cidades usando o for.
        // Aqui serão utilizados os métodos get(posição) e size()
        System.out.println("Percorrendo a lista usando for:");
        for(int i = 0; i < cidades.size(); i++){
            System.out.println("Posição " + i + " - " + cidades.get(i));
        }

        // 4) Com o método remove(posição),
        // removeremos a cidade da posição 3 (Manaus);
        cidades.remove(3);

        // 5) Com o método add(posição, item),
        // adicionaremos a cidade “Florianópolis” na posição zero;
        cidades.add(0, "Florianópolis");

        // 6) Vamos percorrer novamente a lista usando for-each;
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando for-each:");
        int i = 0;
        for(String cidade : cidades){
            System.out.println("Posição " + i + " - " + cidade);
            i++;
        }

        // 7) Agora, usaremos o indexOf(item) para retornar
        // a posição da cidade “Recife” e, com o método
        // set(posição, item) substituiremos "Recife"
        // por “Salvador”;
        int posicaoCidade = cidades.indexOf("Recife");
        cidades.set(posicaoCidade, "Salvador");

        // 8) Agora, vamos percorrer a lista novamente,
        // mas usando Iterator.
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando Iterator:");
        i = 0;
        Iterator<String> iterator = cidades.iterator();
        // o método hasNext() verifica se existe
        // um próximo elemento para ser iterado
        while (iterator.hasNext()){
            // o método next() retorna o próximo elemento
            System.out.println("Posição " + i + " - " + iterator.next());
            i++;
        }
    }
}
```
Saída:

```
Percorrendo a lista usando for:
Posição 0 - São Paulo
Posição 1 - Rio de Janeiro
Posição 2 - Recife
Posição 3 - Manaus
Posição 4 - Curitiba
==================
Percorrendo a lista usando for-each:
Posição 0 - Florianópolis
Posição 1 - São Paulo
Posição 2 - Rio de Janeiro
Posição 3 - Recife
Posição 4 - Curitiba
==================
Percorrendo a lista usando Iterator:
Posição 0 - Florianópolis
Posição 1 - São Paulo
Posição 2 - Rio de Janeiro
Posição 3 - Salvador
Posição 4 - Curitiba
```
Neste segundo exemplo, vamos utilizar alguns dos métodos específicos do **LinkedList**:

```java
import java.util.Iterator;
import java.util.LinkedList;

public class TesteLinkedListMetodosEspecificos {
    public static void main(String[] args) {

        // 1) Primeiro, vamos instanciar uma LinkedList;
        LinkedList<String> nomes = new LinkedList<>();

        // 2) Depois, vamos adicionar quatro nomes
        // usando o método add(item);
        nomes.add("Ana");
        nomes.add("Pedro");
        nomes.add("Maria");
        nomes.add("João");

        // 3) Com o método addFirst(item) vamos
        // adicionar Marcelo no início da lista
        nomes.addFirst("Marcelo");

        // 4) Com o método addLast(item) vamos
        // adicionar Bruna no final da lista
        nomes.addLast("Bruna");

        // 5) Vamos percorrer a lista usando for-each;
        System.out.println("Percorrendo a lista usando for-each:");
        int i = 0;
        for(String nome : nomes){
            System.out.println("Posição " + i + " - " + nome);
            i++;
        }

        System.out.println("==================");

        // 6) Usando o método getFirst(),
        // vamos retornar o primeiro elemento da lista
        System.out.println("Primeiro elemento: " + nomes.getFirst());

        // 8) Usando o método getLast(),
        // vamos retornar o último elemento da lista
        System.out.println("Último elemento: " + nomes.getLast());

        // 9) Com o método removeFirst() vamos remover
        // o primeiro elemento da lista
        nomes.removeFirst();

        // 10) Com o método removeLast() vamos remover
        // o último elemento da lista
        nomes.removeLast();

        // 11) vamos percorrer a lista novamente
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando Iterator:");
        i = 0;
        Iterator<String> iterator = nomes.iterator();
        while (iterator.hasNext()){
            System.out.println("Posição " + i + " - " + iterator.next());
            i++;
        }
    }
}
```
Saída:

```
Percorrendo a lista usando for-each:
Posição 0 - Marcelo
Posição 1 - Ana
Posição 2 - Pedro
Posição 3 - Maria
Posição 4 - João
Posição 5 - Bruna
==================
Primeiro elemento: Marcelo
Último elemento: Bruna
==================
Percorrendo a lista usando Iterator:
Posição 0 - Ana
Posição 1 - Pedro
Posição 2 - Maria
Posição 3 - João
```
##Quando usar ArrayList e quando usar LinkedList?

Se você for utilizar com frequência operações de adicionar e remover elementos da lista, o mais indicado seria usar **LinkedList**, pois como vimos, esta classe consegue realizar essas operações com mais eficiência do que a classe ArrayList.

Agora, se você precisar acessar elementos da lista com mais frequência, a melhor escolha seria usar a classe **ArrayList**, pois ela faz isso de maneira muito mais rápida do que a classe LinkedList.

#Considerações Finais

Neste artigo foi apresentado o funcionamento da classe LinkedList e foram abordadas as principais diferenças entre esta classe e a ArrayList. Vimos também que podemos utilizar os mesmos métodos de ArrayList, já que as duas implementam a interface List, e conhecemos mais alguns métodos específicos de LinkedList. Além disso, vimos em quais momentos é mais adequado utilizar um ou outro.
 
Espero ter ajudado e até a próxima!