#6 Qual é a diferença entre ArrayList e LinkedList em Java? Em qual situação você usaria cada um?

Resposta direta

Ambas implementam a interface List, mas suas estruturas internas são completamente diferentes.

ArrayList usa um array dinâmico (dynamic array) por baixo. Acesso aleatório por índice é O(1) — é só um deslocamento de ponteiro. Adicionar no final é O(1) amortizado: quando o array enche, Java aloca um novo com ~1,5× o tamanho e copia os elementos (resize). Inserções ou deleções no meio são O(n) porque os elementos precisam ser deslocados (shift).

LinkedList é uma lista duplamente encadeada (doubly-linked list). Cada nó carrega o elemento mais dois ponteiros (anterior e próximo). Adicionar ou remover na cabeça ou na cauda é O(1). Mas acesso por índice é O(n) — é preciso percorrer desde o início. Ela também implementa Deque, sendo usada nativamente como fila (queue) ou pilha (stack).

Na prática, ArrayList vence na grande maioria dos casos por causa da localidade de cache (cache locality) — CPUs modernas pré-buscam memória contígua com eficiência. LinkedList tem overhead maior de memória por elemento (dois ponteiros extras) e causa cache misses frequentes durante iteração.

Exemplo de código

import java.util.*;

public class ListComparison {

    public static void main(String[] args) {
        List<String> arrayList   = new ArrayList<>();
        List<String> linkedList  = new LinkedList<>();
        Deque<String> deque      = new LinkedList<>(); // as a queue

        // O(1) amortised — adding at the end
        arrayList.add("a");
        arrayList.add("b");

        // O(1) — adding at head/tail
        ((LinkedList<String>) linkedList).addFirst("x");
        ((LinkedList<String>) linkedList).addLast("y");

        // O(1) random access — ArrayList shines here
        String s = arrayList.get(0);

        // O(n) random access — LinkedList pain point
        String t = linkedList.get(0); // traverses from head!

        // O(n) middle insertion — shifts all elements right
        arrayList.add(0, "first"); // expensive!

        // O(1) middle insertion IF you already have an iterator
        ListIterator<String> it = linkedList.listIterator(0);
        it.add("head"); // just pointer updates, no shift

        // Prefer ArrayDeque over LinkedList when you need a queue
        Deque<String> betterQueue = new ArrayDeque<>();
    }
}

Pegadinhas e armadilhas

• “LinkedList é melhor para inserções no meio” — só é verdade se você já tem um Iterator na posição. Buscar o índice primeiro (get(i)) custa O(n), anulando a vantagem.
• O entrevistador pode perguntar sobre o resize interno do ArrayList: o threshold é ~75% da capacidade no JDK moderno, e o novo tamanho é (oldCapacity * 3) / 2 + 1. Saber isso diferencia candidatos.
• LinkedList implementa Deque (double-ended queue), mas na prática ArrayDeque é mais rápida para uso como fila ou pilha porque evita os cache misses dos nós espalhados na heap.
• Memória: cada nó de LinkedList aloca um objeto extra com dois ponteiros — em JVMs 64-bit sem compressed oops, são ~40 bytes por nó vs ~4–8 bytes por slot no array do ArrayList.
• Iterar via for (int i=0; i<list.size(); i++) list.get(i) numa LinkedList é O(n²). Sempre use enhanced-for ou iterator — isso é um erro clássico de performance.

Perguntas de follow-up

Como o ArrayList lida com o redimensionamento interno?

Quando a capacidade é atingida, ArrayList aloca um novo array com tamanho ≈ 1,5× (grow factor) e copia todos os elementos via Arrays.copyOf. Essa operação é O(n) pontualmente, mas como acontece com frequência exponencialmente menor, o custo amortizado (amortized cost) por inserção ainda é O(1). Você pode evitar o resize chamando new ArrayList<>(initialCapacity) se souber o tamanho esperado.

Quando você preferiria LinkedList em produção?

Raramente. Um caso legítimo é quando você tem um ListIterator já posicionado e faz muitas inserções/deleções consecutivas naquela posição (ex.: processamento de stream de eventos com cursor fixo). Para filas e deques, prefira ArrayDeque, que é mais rápida e tem melhor footprint de memória.

O que é um iterator fail-fast e como ele se relaciona com essas coleções?

Ambas usam iteradores fail-fast (fail-fast iterators): mantêm um contador interno modCount que incrementa a cada modificação estrutural. Se o iterator detecta que modCount mudou durante a iteração, lança ConcurrentModificationException. Isso não garante thread-safety — é apenas um mecanismo best-effort para detectar bugs de modificação concorrente (concurrent modification).

Qual é a alternativa thread-safe ao ArrayList?

CopyOnWriteArrayList do pacote java.util.concurrent: a cada escrita, cria uma cópia completa do array interno, permitindo leituras concorrentes sem locks. É ideal quando leituras dominam e escritas são raras. Para casos com muitas escritas, prefira uma lista sincronizada via Collections.synchronizedList combinada com sincronização explícita nos blocos de iteração.