0Pricing
Java Academy · Aula

LinkedList versus ArrayList: Compromissos

Compare o desempenho de inserção, exclusão e acesso aleatório para escolher o tipo de lista adequado.

LinkedList versus ArrayList: Compromissos é uma aula grátis de Java Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Java Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Java Academy inclui 4 aulas no total.

A questão central

Tanto ArrayList quanto LinkedList implementam List, portanto compartilham a mesma API. A diferença está nas estruturas de dados internas e nas operações que cada uma executa com eficiência.

Estrutura interna da ArrayList

ArrayList armazena os elementos em um vetor contíguo. Quando o vetor fica cheio, ele é substituído por um novo vetor 1,5 vez maior, e todos os elementos são copiados.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

Estrutura interna da LinkedList revisitada

Cada elemento vive em seu próprio objeto Node, com ponteiros para o anterior e o próximo. Não há memória contígua — os nós podem estar em qualquer lugar do heap.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Acesso aleatório: ArrayList vence

ArrayList.get(i) é O(1) — índice direto do vetor. LinkedList.get(i) é O(n) — percorre até n/2 nós.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Inserções no início: LinkedList vence

Adicionar no índice 0 em ArrayList exige deslocar todos os elementos — O(n). LinkedList apenas atualiza dois ponteiros — O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Inserções no fim: aproximadamente iguais

ArrayList e LinkedList oferecem anexações amortizadas O(1) no fim. ArrayList ocasionalmente inicia uma cópia para redimensionar, mas o custo amortizado ainda é O(1). LinkedList aloca um novo nó — não é necessário redimensionar.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Uso de memória

ArrayList: cerca de 8 bytes por elemento (uma referência no vetor). LinkedList: cerca de 48 bytes por elemento (objeto Node com dados, ponteiros para o anterior e o próximo, além do cabeçalho do objeto). Para grandes conjuntos de dados, ArrayList usa significativamente menos memória.

Desempenho da iteração

A iteração sequencial (for-each ou iterador) é O(n) para ambas. Porém, ArrayList se beneficia da pré-busca do cache da CPU — os elementos são contíguos na memória. Os nós de LinkedList ficam espalhados pelo heap, causando falhas de cache.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Inserção/remoção no meio

Ambas exigem O(n) para localizar a posição. Depois de encontrá-la, ArrayList desloca os elementos em O(n); LinkedList apenas desvincula em O(1). Portanto, para alterações frequentes no meio quando você já mantém um iterador, LinkedList vence; caso contrário, são semelhantes.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Guia de decisão

Escolha com base na operação dominante:

  • ArrayList: acesso aleatório, iteração e anexações no fim — abrange 90% dos casos de uso
  • LinkedList: inserções e remoções frequentes no início ou no fim, implementação de fila, fila de duas extremidades ou pilha
  • ArrayDeque: quando precisar de uma fila ou pilha pura (melhor que LinkedList)

Resumo do teste de desempenho

Modelo mental para o desempenho:

  • get(i): ArrayList O(1) em comparação com LinkedList O(n)
  • add(0,x): ArrayList O(n) em comparação com LinkedList O(1)
  • add(x): ambas amortizadas em O(1)
  • remoção com iterador: ambas O(1) depois que a posição é encontrada
  • Memória por elemento: ArrayList cerca de 8B em comparação com LinkedList cerca de 48B

Verificação rápida

Você está criando uma fila de tarefas na qual as tarefas são adicionadas ao fim e removidas do início milhões de vezes por segundo. Qual estrutura de dados é mais apropriada?

Recapitulação: LinkedList versus ArrayList

Principais conclusões:

  • ArrayList é excelente para acesso aleatório (O(1)) e iteração eficiente em relação ao cache
  • LinkedList é excelente para operações O(1) no início e no fim
  • Memória: ArrayList ~8 B/elemento; LinkedList ~48 B/elemento
  • Para filas/pilhas, prefira ArrayDeque a LinkedList
  • ArrayList é a escolha padrão adequada para a maioria dos cenários

Perguntas Frequentes

A aula “LinkedList versus ArrayList: Compromissos” é grátis?

Sim — o texto completo de “LinkedList versus ArrayList: Compromissos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Java Academy, atualize para CoddyKit PRO. O curso de Java Academy inclui 4 aulas no total.

O que vou aprender em “LinkedList versus ArrayList: Compromissos”?

Compare o desempenho de inserção, exclusão e acesso aleatório para escolher o tipo de lista adequado. Você pratica Java Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Java Academy?

Nenhuma experiência prévia é necessária. Java Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.

Quanto tempo leva a aula “LinkedList versus ArrayList: Compromissos”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Java Academy?

Sim. Cada aula de Java Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Estrutura Interna de LinkedList
  2. Operações de Deque: Pilha e Fila
  3. LinkedList versus ArrayList: Compromissos
  4. PriorityQueue para Processamento Ordenado
← Voltar para Java Academy