Java LinkedList

LinkedList<E> é uma lista duplamente encadeada: cada elemento vive em seu próprio nó no heap com um ponteiro para o próximo nó e um ponteiro para o anterior. Isso lhe confere o perfil de desempenho oposto ao do ArrayList: inserir e remover nas extremidades é O(1), mas get(i) precisa percorrer desde uma extremidade até o índice — O(n). A classe também é a única List nativa do Java que implementa Deque<E>, funcionando portanto como uma fila. Este capítulo explica quando essa combinação é a ferramenta certa, e a lista (um pouco maior) dos casos em que não é.

A estrutura de dados

Cada elemento é um nó:

node:  prev ←—— element ——→ next

A lista mantém duas referências de campo — first e last — e um contador size. Para adicionar em qualquer extremidade, você aloca um nó, o encaixa ajustando dois ponteiros e incrementa size. Sem array, sem redimensionamento, sem memória desperdiçada. Esse é o atrativo.

O custo aparece em todo o resto:

• Cada elemento paga por um objeto nó — três referências e um cabeçalho de objeto. A sobrecarga de memória por elemento é muito maior do que a do array plano do ArrayList.
• get(i), set(i, x), add(i, x), remove(i) percorrem todos desde a extremidade mais próxima. Portanto, list.get(size/2) é O(n/2). Em listas longas, isso se acumula de forma prejudicial.
• A localidade de cache é ruim — os nós estão espalhados pelo heap, fazendo com que a travessia perca o cache da CPU e fique mais lenta mesmo quando o algoritmo parece linear.

Quando LinkedList é a escolha certa

A resposta honesta em 2026: raramente como List, às vezes como Deque, quase nunca para "acelerar inserções." O folclore de "use LinkedList porque você vai inserir" não envelheceu bem — para a maioria das cargas de trabalho, a eficiência de cache do ArrayList mais seu append O(1) amortizado supera a perseguição de ponteiros extra de uma lista encadeada, mesmo quando o algoritmo chama add(0, x) às vezes. Os casos em que LinkedList de fato vence:

• Você precisa de um Deque (adicionar/remover em ambas as extremidades) e ainda não tem um ArrayDeque no escopo. ArrayDeque é mais rápido; LinkedList é mais familiar.
• Você mantém referências persistentes a nós específicos (via ListIterator) e quer inserção/remoção O(1) nessas posições exatas. Este é o caso de uso clássico de lista encadeada — e raramente aparece no Java cotidiano.
• Você quer uma implementação de Queue que também expõe métodos de List para inspeção. Exemplo real: uma fila de tarefas que ocasionalmente é despejada em um log.

Para "lista à qual adiciono e leio por índice," use ArrayList. Para "fila ou deque," use ArrayDeque. LinkedList fica entre os dois e raramente é a melhor escolha para qualquer um dos trabalhos.

Criando e usando como List

A metade List da API é idêntica à do ArrayList:

List<String> tasks = new LinkedList<>();
tasks.add("compile");
tasks.add("test");
tasks.add(0, "lint");          // O(1) — at the head
String first = tasks.get(0);   // O(1) — head
String last  = tasks.get(tasks.size() - 1);   // O(1) — tail
String mid   = tasks.get(tasks.size() / 2);   // O(n/2) — has to walk

O construtor não tem parâmetro de capacidade — não há nada a pré-dimensionar, pois os nós são alocados um de cada vez.

Usando como Queue e Deque

Como LinkedList implementa tanto Queue<E> quanto Deque<E>, você obtém os métodos de fila além dos de List:

Deque<String> stack = new LinkedList<>();
stack.push("a");          // adds to head
stack.push("b");
String top = stack.pop(); // removes from head → "b"

Queue<String> jobs = new LinkedList<>();
jobs.offer("j1");         // adds to tail
jobs.offer("j2");
String next = jobs.poll();// removes from head → "j1"

Se sua necessidade é puramente "fila FIFO" ou "pilha LIFO," declare a variável como Queue<E> ou Deque<E> — e prefira new ArrayDeque<>() como implementação. A interface é a mesma; a implementação baseada em array é mensuravelmente mais rápida.

Iteração e ConcurrentModificationException

Mesmo modelo fail-fast do ArrayList. Mutação durante um loop for-each lança exceção:

LinkedList<Integer> xs = new LinkedList<>(List.of(1, 2, 3, 4));
for (int x : xs) if (x % 2 == 0) xs.remove(Integer.valueOf(x));  // throws

removeIf e o Iterator.remove() explícito são as duas formas seguras — idênticas ao capítulo sobre ArrayList. O aspecto interessante do LinkedList é o ListIterator: como o iterador mantém uma referência direta ao nó atual, seus métodos add e remove são genuinamente O(1). Se você realmente precisa de iteração com inserção rápida por posição, LinkedList.listIterator() é a API que entrega o que o livro didático promete.

Segurança de threads

Mesma situação do ArrayList: nenhuma. Use Collections.synchronizedList(new LinkedList<>()) para bloqueio geral, ou — muito melhor — um ConcurrentLinkedDeque se seu caso de uso é realmente uma fila concorrente.

A comparação com ArrayDeque em um parágrafo

Quando você recorre ao LinkedList para usar como fila ou pilha, olhe primeiro para o ArrayDeque. ArrayDeque é um array circular — sem nó por elemento, sem perseguição de ponteiros, sem regras de rejeição de null para lembrar. Em cargas de trabalho reais de pilha/fila, ele geralmente supera o LinkedList — às vezes por uma margem considerável — porque evita um nó no heap e um cabeçalho por elemento e mantém seus dados contíguos na memória. Ele não implementa List, que é sua única desvantagem real. (Não interprete demais um pequeno benchmark em qualquer direção; veja o exemplo trabalhado abaixo.)

Um exemplo trabalhado: mesma tarefa, duas estruturas de dados

O programa abaixo constrói a mesma fila com ArrayList, LinkedList e ArrayDeque — adiciona em uma extremidade, remove da outra 200 000 vezes — e imprime o tempo de relógio de parede para cada um. Leia os números em contexto: eles são um micro-benchmark aproximado de execução única em uma JVM fria, não um resultado rigoroso, portanto trate a ordem relativa — não os milissegundos exatos — como a lição. ArrayList é dramaticamente mais lento do que os outros dois porque remove(0) é O(n), tornando o loop de drenagem quadrático. LinkedList e ArrayDeque são ambos rápidos: cada um faz trabalho O(1) na cabeça. Qual dos dois fica à frente depende da máquina, do JIT e do boxing de Integer — é exatamente por isso que você nunca deve se basear em um benchmark tão pequeno para escolher entre eles.

Duas conclusões:

• Os dois primeiros tempos mostram por que nunca indexe um LinkedList em um loop. A forma for-each percorre a lista uma vez em O(n); a forma por índice percorre uma vez por índice, resultando em O(n²). Para 10 000 elementos isso já é doloroso; para 100 000 leva segundos.
• Os três tempos de fila mostram a verdadeira divisão: ela está entre ArrayList (drenagem quadrática) e as duas estruturas O(1) na cabeça, não entre LinkedList e ArrayDeque. Uma vez que você descartou ArrayList para trabalho com filas, prefira ArrayDeque de qualquer forma — ele não aloca nenhum nó por elemento e tem localidade de cache muito melhor em filas grandes e de longa duração, o que um loop de inicialização a frio de 200 000 elementos não expõe completamente. O motivo genuíno restante para usar LinkedList é "quero um Deque e uma List," e mesmo isso é raro.

O que vem a seguir

LinkedList e ArrayList são as duas implementações de List de uso geral mais interessantes. A terceira — mais antiga, sincronizada, majoritariamente histórica — é o Vector. Saber por que ela não é a escolha certa em novo código faz parte de ser fluente no framework.

Prática