0Pricing
Java Academy · Aula

Estrutura Interna de LinkedList

Explore a estrutura de nós duplamente encadeados de LinkedList e seu perfil de complexidade temporal.

Estrutura Interna de LinkedList é uma aula grátis de Java Academy no CoddyKit. Esta é a aula 1 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.

内部 da LinkedList

A LinkedList do Java é uma lista duplamente encadeada: cada nó mantém uma referência para o nó anterior e o próximo, além do valor do elemento. Ao contrário da ArrayList, não há um vetor de apoio — a memória é alocada por nó.

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;
    Node(T data) { this.data = data; }
}

Perfil de complexidade temporal

As características de desempenho da LinkedList diferem significativamente das da ArrayList:

  • addFirst / addLast: O(1)
  • get(índice): O(n) — é necessário percorrer a partir do início ou do fim
  • remove(índice): O(n) para localizar, depois O(1) para desvincular
  • Percurso com iterador: O(n)

Use LinkedList quando precisar inserir frequentemente no início ou no fim, não para acesso aleatório.

Criando e percorrendo uma LinkedList

Criar uma LinkedList e iterar por ela segue a mesma interface List que você já conhece. A diferença está na estrutura interna.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");

for (String name : list) {
    System.out.println(name);
}

System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: "  + list.getLast());  // Carol

addFirst, addLast, removeFirst, removeLast

A LinkedList oferece operações no início e no fim que a ArrayList não fornece de forma eficiente:

LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10);   // [10]
nums.addLast(20);   // [10, 20]
nums.addFirst(5);   // [5, 10, 20]

System.out.println(nums.removeFirst()); // 5  → [10, 20]
System.out.println(nums.removeLast());  // 20 → [10]

Desvinculação de nós: exclusão O(1) após a localização

Quando você tem uma referência para um nó (por meio de um iterador), a remoção é O(1), pois basta atualizar os ponteiros para o próximo e o anterior — não há deslocamento de elementos como na ArrayList.

import java.util.*;

LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
    String t = it.next();
    if (t.equals("B") || t.equals("D")) {
        it.remove(); // O(1) unlink
    }
}
System.out.println(tasks); // [A, C]

Sobrecarga de memória em comparação com ArrayList

Cada nó de LinkedList contém duas referências extras (anterior e próximo), além da referência para o elemento — cerca de 48 bytes por entrada em uma JVM de 64 bits. ArrayList armazena apenas a referência para o elemento (8 bytes) em um vetor contíguo.

Para grandes conjuntos de dados com muitas leituras, ArrayList geralmente aproveita melhor o cache e usa menos memória.

Operações de fila de duas extremidades: pilha e fila

LinkedList implementa a interface Deque, o que permite usá-la tanto como pilha quanto como fila.

import java.util.LinkedList;
import java.util.Deque;

// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first

// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

Visão geral da PriorityQueue

PriorityQueue é uma fila baseada em heap na qual o menor elemento (pela ordem natural ou por um comparador) é sempre retirado primeiro. Ela NÃO é apoiada por uma lista encadeada — usa um vetor de heap binário.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);

System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40

PriorityQueue com comparador personalizado

Forneça um Comparator para inverter a ordenação ou ordenar por um campo personalizado:

import java.util.*;

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));

while (!tasks.isEmpty()) {
    System.out.println(tasks.poll().name());
}
// High, Med, Low

Escolhendo entre LinkedList e ArrayList

Regra prática:

  • Use ArrayList para acesso aleatório, iteração e para a maioria dos cenários.
  • Use LinkedList quando precisar inserir ou remover frequentemente em O(1) nas duas extremidades e não precisar de acesso por índice.
  • Use PriorityQueue quando precisar de processamento ordenado (agendamento de tarefas, algoritmo de Dijkstra).

Armadilhas comuns

Evite chamar get(i) em um laço sobre uma LinkedList — o custo total é O(n²):

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);

// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
    int val = list.get(i); // slow!
}

// GOOD: O(n) — use iterator
for (int val : list) {
    // process val
}

Verificação rápida

Qual operação de LinkedList é O(1), independentemente do tamanho da lista?

Recapitulação: LinkedList e fila de duas extremidades

Principais conclusões:

  • LinkedList é uma lista duplamente encadeada com operações O(1) no início e no fim
  • O acesso aleatório (leitura e atribuição por índice) é O(n)
  • Implementa uma fila de duas extremidades — pode ser usada como pilha ou fila
  • PriorityQueue fornece processamento ordenado por heap
  • Prefira ArrayList na maioria dos casos de uso; LinkedList se destaca quando há alterações frequentes no início ou no fim

Perguntas Frequentes

A aula “Estrutura Interna de LinkedList” é grátis?

Sim — o texto completo de “Estrutura Interna de LinkedList” é 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 “Estrutura Interna de LinkedList”?

Explore a estrutura de nós duplamente encadeados de LinkedList e seu perfil de complexidade temporal. 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 1 de 4.

Quanto tempo leva a aula “Estrutura Interna de LinkedList”?

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