LinkedList ou ArrayList em Java: o que escolher e por que isso é importante

LinkedList ou ArrayList: batalha dos titãs das coleções Java

Se você já escreveu código Java que trabalha com listas de dados, certamente já enfrentou o dilema: LinkedList ou ArrayList? Essa pergunta é um verdadeiro sucesso no Stack Overflow, discutida por milhares de desenvolvedores. E não é à toa. Escolher a estrutura de dados errada pode transformar seu código rápido em uma tartaruga que rasteja pelo pântano. Já a escolha certa pode tornar sua aplicação responsiva e eficiente.

Hoje não vamos apenas listar fatos secos. Vamos olhar por baixo dos panos do Java, entender como essas coleções funcionam no nível de memória e processador, e dar uma resposta clara: quando, afinal, usar LinkedList e quando usar ArrayList. Vamos lá!

Resumindo o essencial: o que dizem os cavalheiros da documentação

Vamos começar com o básico. Ambas as classes implementam a interface List, mas fazem isso de maneiras diferentes.

\n
• ArrayList — é um array dinâmico. Ele armazena elementos em um bloco contínuo de memória. Quando o array fica cheio, ele cria um novo, maior, e copia todos os elementos para ele.
\n
• LinkedList — é uma lista duplamente encadeada. Cada elemento (nó) armazena referências para o elemento anterior e o próximo. A memória é alocada separadamente para cada nó.
\n

Parece simples. Mas o diabo, como sempre, está nos detalhes. Vamos dar uma olhada no código.

Por baixo dos panos: como funciona na prática

ArrayList: velocidade de acesso, mas inserção lenta no meio

import java.util.ArrayList;\nimport java.util.List;\n\npublic class ArrayListDemo {\n    public static void main(String[] args) {\n        List<String> arrayList = new ArrayList<>();\n        \n        // Adicionar ao final — rápido (O(1) amortizado)\n        long start = System.nanoTime();\n        for (int i = 0; i < 100000; i++) {\n            arrayList.add("Element " + i);\n        }\n        long end = System.nanoTime();\n        System.out.println("ArrayList add (ao final): " + (end - start) / 1e6 + " ms");\n        \n        // Acesso por índice — instantâneo (O(1))\n        start = System.nanoTime();\n        String element = arrayList.get(50000);\n        end = System.nanoTime();\n        System.out.println("ArrayList get: " + (end - start) + " ns");\n        \n        // Inserção no meio — lenta (O(n))\n        start = System.nanoTime();\n        arrayList.add(25000, "INSERTED");\n        end = System.nanoTime();\n        System.out.println("ArrayList insert (meio): " + (end - start) / 1e6 + " ms");\n    }\n}

O que acontece aqui? Quando você insere um elemento no meio de um ArrayList, todos os elementos à direita do ponto de inserção são deslocados uma posição. Essa é uma operação O(n). Se você tem um milhão de elementos, será um milhão de operações de cópia. Doloroso.

LinkedList: inserção é rei, mas acesso é pária

import java.util.LinkedList;\nimport java.util.List;\n\npublic class LinkedListDemo {\n    public static void main(String[] args) {\n        List<String> linkedList = new LinkedList<>();\n        \n        // Adicionar ao final — rápido (O(1))\n        long start = System.nanoTime();\n        for (int i = 0; i < 100000; i++) {\n            linkedList.add("Element " + i);\n        }\n        long end = System.nanoTime();\n        System.out.println("LinkedList add (ao final): " + (end - start) / 1e6 + " ms");\n        \n        // Acesso por índice — lento (O(n))\n        start = System.nanoTime();\n        String element = linkedList.get(50000);\n        end = System.nanoTime();\n        System.out.println("LinkedList get: " + (end - start) / 1e6 + " ms");\n        \n        // Inserção no meio — rápida (O(1) após encontrar a posição)\n        start = System.nanoTime();\n        // ATENÇÃO: o próprio método add(index, element) ainda faz a busca (O(n))\n        linkedList