Node

Nós e estruturas encadeadas

Um nó (Node) é o bloco fundamental de estruturas de dados encadeadas como listas ligadas, árvores e grafos. Cada nó contém um valor (o dado que armazena) e uma ou mais referências para nós vizinhos. A referência nula (null) indica o fim da cadeia.

Numa lista simplesmente ligada (singly linked list), cada nó aponta apenas para o próximo. Numa lista duplamente ligada, cada nó aponta para o próximo e para o anterior, permitindo percorrer nos dois sentidos. Em árvores binárias, cada nó tem referências para os filhos esquerdo e direito.

Entender nós é essencial para compreender os trade-offs das coleções Java: LinkedList tem inserção O(1) no início porque só ajusta um ponteiro, mas busca O(n) porque precisa percorrer os nós. ArrayList tem busca O(1) por índice mas inserção no meio O(n) porque precisa deslocar elementos.

Exemplo.java

// ── Nó genérico para lista ligada ────────────────
public class Node<T> {
    public T valor;
    public Node<T> proximo;

    public Node(T valor) {
        this.valor = valor;
        this.proximo = null;
    }
}

// ── Construindo uma lista ligada manualmente ──────
Node<Integer> no1 = new Node<>(10);
Node<Integer> no2 = new Node<>(20);
Node<Integer> no3 = new Node<>(30);

no1.proximo = no2;  // 10 → 20
no2.proximo = no3;  // 20 → 30
                    // 30 → null

// ── Percorrendo a lista ───────────────────────────
Node<Integer> atual = no1;
while (atual != null) {
    System.out.print(atual.valor + " ");
    atual = atual.proximo;
}
// Saída: 10 20 30

// ── Nó de árvore binária ──────────────────────────
public class TreeNode<T> {
    public T valor;
    public TreeNode<T> esquerdo;
    public TreeNode<T> direito;

    public TreeNode(T valor) { this.valor = valor; }
}

💡 Dica pro

Java já oferece LinkedList que usa nós internamente. Implemente sua própria LinkedList do zero pelo menos uma vez — é o exercício mais eficaz para entender ponteiros e referências em Java.

Recompensa+30 XP+exercícios