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.

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”:

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:

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.

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:

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):

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”:

Lista após a remoção:

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:

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:

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:

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. 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.

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:

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!