O que é uma lista ligada (LinkedList)?

Uma lista ligada é uma estrutura de dados linear na qual os elementos não são armazenados em células de memória contíguas. Em vez disso, cada elemento, chamado nó, contém dados e uma referência (ou ponteiro) para o próximo nó na sequência.

Existem diferentes tipos de listas ligadas:

• Lista ligada simples: Cada nó contém apenas uma referência ao próximo nó.
• Lista duplamente ligada: Cada nó contém referências tanto ao próximo como ao anterior.
• Lista ligada circular: O último nó referencia o primeiro, formando um ciclo.

Operações principais numa lista ligada:

• Inserção: Adicionar um novo nó à lista.
• Remoção: Remover um nó da lista.
• Procura: Procurar um nó pelo seu valor.
• Percurso: Acesso sequencial a todos os nós da lista.

Vantagens:

• Flexibilidade para inserir e remover elementos em qualquer posição.
• Gestão eficiente de memória, pois os elementos não requerem blocos contíguos.

Desvantagens:

• Acesso aleatório lento aos elementos (é necessário percorrer sequencialmente).
• Requer memória adicional para armazenar referências.

Exemplo de estrutura de um nó numa lista ligada simples:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}