Java LinkedList

A LinkedList é a "outra" lista do Java. Ela faz tudo o que a ArrayList faz, mas guarda os elementos de um jeito diferente: como vagões de um trem, cada um engatado no próximo. Isso a deixa boa para mexer nas pontas (começo e fim) e, por isso, ela também serve de fila. Nesta aula você vai vê-la como lista e como fila, entender quando ela ganha (e quando perde) da ArrayList, e conhecer a ArrayDeque, a melhor escolha para filas e pilhas.

A ideia: um trem de vagões

A ArrayList guarda os elementos lado a lado, numa fileira de cadeiras numeradas. Para achar a cadeira 500, basta ir direto a ela. Mas, para encaixar alguém na cadeira 0, todo mundo precisa levantar e andar uma cadeira para o lado.

A LinkedList guarda cada elemento num "vagão" (o nome técnico é nó) que sabe quem é o vagão da frente e o de trás. Daí o nome: linked = ligada, encadeada.

ArrayList:   [ Ana | Bruno | Carla | Duda ]        « fileira numerada: 0, 1, 2, 3

LinkedList:  Ana ⇄ Bruno ⇄ Carla ⇄ Duda             « cada vagão conhece o vizinho
             ↑ primeiro                ↑ último

As consequências:

• Engatar ou soltar um vagão na ponta é instantâneo: basta mudar dois engates. Ninguém precisa andar.
• Achar o vagão número 500 é lento: não há número pintado nos vagões. É preciso começar da ponta e contar um por um.

A LinkedList como lista

Tudo o que você aprendeu de List funciona igual: add, get, set, remove, size, contains… Além disso, ela tem métodos próprios para as pontas:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> trem = new LinkedList<>();
        trem.add("vagão 1");
        trem.add("vagão 2");
        System.out.println("Início:        " + trem);

        trem.addFirst("locomotiva");
        trem.addLast("vagão 3");
        System.out.println("addFirst/Last: " + trem);

        System.out.println("getFirst(): " + trem.getFirst());
        System.out.println("getLast():  " + trem.getLast());
        System.out.println("get(2):     " + trem.get(2));

        String saiu1 = trem.removeFirst();
        String saiu2 = trem.removeLast();
        System.out.println("removeFirst tirou " + saiu1 + ", removeLast tirou " + saiu2);
        System.out.println("Sobrou:        " + trem);
    }
}

LinkedList<String> trem

Aqui a variável é do tipo LinkedList, e não List, de propósito: os métodos addFirst, removeFirst… são da LinkedList (vêm da interface Deque, que você vai ver adiante).

addFirst(x) / addLast(x)

Engata no começo / no fim. addLast é o mesmo que add.

getFirst() / getLast()

Lê o primeiro / o último, sem tirar.

removeFirst() / removeLast()

Tira o primeiro / o último e devolve quem saiu.

$ javac Main.java
$ java Main
Início:        [vagão 1, vagão 2]
addFirst/Last: [locomotiva, vagão 1, vagão 2, vagão 3]
getFirst(): locomotiva
getLast():  vagão 3
get(2):     vagão 2                    « funciona, mas conta vagão por vagão
removeFirst tirou locomotiva, removeLast tirou vagão 3
Sobrou:        [vagão 1, vagão 2]

A LinkedList se imprime igual à ArrayList, entre colchetes. Olhando a saída, não dá para saber qual das duas é: a diferença está só em como os dados são guardados.

A LinkedList como fila (Queue)

Uma fila funciona como a da cantina: quem chega entra no fim; quem é atendido sai do começo. Em inglês isso se chama FIFO, first in, first out ("o primeiro a entrar é o primeiro a sair"). A interface do Java para filas é a Queue (pronuncia-se "kiú", fila), e a LinkedList é uma das classes que a implementam.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> fila = new LinkedList<>();
        fila.offer("Ana");
        fila.offer("Bruno");
        fila.offer("Carla");
        System.out.println("Fila: " + fila);
        System.out.println("Próxima (peek): " + fila.peek());

        while (!fila.isEmpty()) {
            String pessoa = fila.poll();
            System.out.println("Atendendo " + pessoa + " | ainda esperam: " + fila);
        }
        System.out.println("poll() na fila vazia: " + fila.poll());
        System.out.println("peek() na fila vazia: " + fila.peek());
    }
}

$ javac Main.java
$ java Main
Fila: [Ana, Bruno, Carla]
Próxima (peek): Ana
Atendendo Ana | ainda esperam: [Bruno, Carla]
Atendendo Bruno | ainda esperam: [Carla]
Atendendo Carla | ainda esperam: []
poll() na fila vazia: null            « fila vazia: null, sem exceção
peek() na fila vazia: null

O laço while (!fila.isEmpty()) se lê "enquanto a fila não estiver vazia": atende um por vez até acabar. Repare que a variável foi declarada como Queue: assim ela só mostra os métodos de fila, e ninguém "fura a fila" com um add(0, …) por engano.

Cada operação tem duas versões

A Queue tem dois métodos para cada operação. A diferença está no que acontece quando não dá certo (por exemplo, fila vazia):

Para filas, prefira a coluna da direita (offer, poll, peek): uma fila vazia é uma situação normal, não um erro.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> fila = new LinkedList<>();
        fila.offer("Ana");
        fila.offer("Bruno");
        fila.offer("Carla");

        // a Duda chegou

        // atenda todo mundo
    }
}

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> fila = new LinkedList<>();
        fila.offer("Ana");
        fila.offer("Bruno");
        fila.offer("Carla");
        fila.offer("Duda");

        while (!fila.isEmpty()) {
            System.out.println("Atendendo " + fila.poll());
        }
    }
}

ArrayList × LinkedList

As duas são List. Qual escolher? Veja o que cada operação custa em cada uma:

Veja a diferença do get(i) na prática. Este programa enche cada lista com 20 mil números e depois lê todos com get(i), medindo o tempo com System.nanoTime() (o relógio do computador, em nanossegundos):

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static long medir(List<Integer> lista) {
        for (int i = 0; i < 20_000; i++) {
            lista.add(i);
        }
        long inicio = System.nanoTime();
        long soma = 0;
        for (int i = 0; i < lista.size(); i++) {
            soma += lista.get(i);
        }
        return (System.nanoTime() - inicio) / 1_000_000;
    }

    public static void main(String[] args) {
        System.out.println("ArrayList,  20 mil get(i): " + medir(new ArrayList<>()) + " ms");
        System.out.println("LinkedList, 20 mil get(i): " + medir(new LinkedList<>()) + " ms");
    }
}

$ javac Main.java
$ java Main
ArrayList,  20 mil get(i): 2 ms
LinkedList, 20 mil get(i): 247 ms        « mais de 100 vezes mais lento

Os números mudam de computador para computador e de uma execução para outra, mas a diferença é sempre enorme. Repare que o método medir recebe List<Integer>: graças a programar para a interface, o mesmo método serve para as duas.

ArrayDeque: pilha e fila rápidas

Deque (pronuncia-se "déc") vem de double-ended queue, "fila de duas pontas": dá para entrar e sair pelos dois lados. A ArrayDeque implementa isso com um array "circular", sem nós: é mais rápida e gasta menos memória do que a LinkedList para esse uso. Com ela você monta tanto uma fila quanto uma pilha.

Pilha: o último a entrar é o primeiro a sair

Pense numa pilha de pratos: você põe um prato em cima e, quando precisa, tira o de cima. Em inglês, LIFO (last in, first out). O exemplo clássico é o "desfazer" (Ctrl+Z) de um editor: ele desfaz primeiro a última coisa que você fez.

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<String> desfazer = new ArrayDeque<>();
        desfazer.push("digitou 'Olá'");
        desfazer.push("apagou uma palavra");
        desfazer.push("colou um texto");
        System.out.println("Pilha: " + desfazer);
        System.out.println("Topo (peek): " + desfazer.peek());

        System.out.println("Ctrl+Z desfaz: " + desfazer.pop());
        System.out.println("Ctrl+Z desfaz: " + desfazer.pop());
        System.out.println("Pilha: " + desfazer);
    }
}

Deque<String> desfazer = new ArrayDeque<>();

A variável é a interface Deque; o objeto, uma ArrayDeque.

push(x)

"Empurrar": põe x no topo da pilha (na prática, no começo do deque).

peek()

Olha o topo sem tirar.

pop()

"Estourar": tira o topo e devolve.

$ javac Main.java
$ java Main
Pilha: [colou um texto, apagou uma palavra, digitou 'Olá']     « o topo aparece primeiro
Topo (peek): colou um texto
Ctrl+Z desfaz: colou um texto
Ctrl+Z desfaz: apagou uma palavra
Pilha: [digitou 'Olá']

A ordem impressa é a do topo para o fundo: o último que entrou (colou um texto) aparece primeiro e é o primeiro a sair.

Fila com as duas pontas

A mesma ArrayDeque serve de fila. Com os métodos …First/…Last, você escolhe a ponta:

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<String> fila = new ArrayDeque<>();
        fila.offerLast("Ana");
        fila.offerLast("Bruno");
        fila.offerFirst("Dona Zélia (prioridade)");
        System.out.println("Fila: " + fila);
        System.out.println("Atende: " + fila.pollFirst());
        System.out.println("Desistiu do fim: " + fila.pollLast());
        System.out.println("Fila: " + fila);
    }
}

$ javac Main.java
$ java Main
Fila: [Dona Zélia (prioridade), Ana, Bruno]     « offerFirst furou a fila (de propósito)
Atende: Dona Zélia (prioridade)
Desistiu do fim: Bruno
Fila: [Ana]

Qual usar para fila e pilha?

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> d = new ArrayDeque<>();
        d.push(1);
        d.push(2);
        d.push(3);
        System.out.println("Deque: " + d);
        while (!d.isEmpty()) {
            System.out.println("saiu " + d.pop());
        }
    }
}

Quando dá errado

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<String> pilha = new ArrayDeque<>();
        pilha.push("único");
        System.out.println(pilha.pop());
        System.out.println(pilha.pop());
    }
}

$ javac Main.java
$ java Main
único
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:360)
	at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:591)
	at Main.main(Main.java:9)

$ java Main
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.LinkedList.removeFirst(LinkedList.java:282)
	at Main.main(Main.java:6)

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> trem = new LinkedList<>();
        trem.addFirst("locomotiva");
        System.out.println(trem);
    }
}

$ javac --release 17 Main.java
Main.java:7: error: cannot find symbol
        trem.addFirst("locomotiva");
            ^
  symbol:   method addFirst(String)
  location: variable trem of type List<String>
1 error
$ javac Main.java && java Main
[locomotiva]                     « no Java 21+ compila e funciona

Referência

Exercícios

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        String palavra = "Java";
        Deque<Character> pilha = new ArrayDeque<>();
        for (char c : palavra.toCharArray()) {
            // empilhe a letra
        }
        String invertida = "";
        // desempilhe tudo, juntando em invertida
        System.out.println(invertida);
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        String palavra = "Java";
        Deque<Character> pilha = new ArrayDeque<>();
        for (char c : palavra.toCharArray()) {
            pilha.push(c);
        }
        String invertida = "";
        while (!pilha.isEmpty()) {
            invertida += pilha.pop();
        }
        System.out.println(invertida);
    }
}

Resumo

• A LinkedList guarda os elementos em nós encadeados: rápida nas pontas, lenta para achar uma posição.
• Métodos das pontas: addFirst, addLast, getFirst, getLast, removeFirst, removeLast.
• Como fila (Queue): offer entra no fim, poll tira do começo, peek espia; com fila vazia, devolvem null.
• ArrayList × LinkedList: quase sempre ArrayList; get(i) numa LinkedList é muito mais lento.
• Para fila e pilha, use ArrayDeque: push/pop/peek (pilha) ou offer/poll (fila). Evite a antiga Stack.
• Tirar de uma estrutura vazia com pop/removeFirst dá NoSuchElementException.

Próxima aula: HashMap, para guardar pares chave → valor.