Lista Encadeada
Nota Conceitual:
Uma lista encadeada é uma estrutura linear onde os elementos (nós) não ficam em blocos unidos de memória, como um array. Cada nó é composto por uma caixinha com um dado e um ponteiro para o próximo nó, formando uma corrente. O acesso começa sempre pelo head, e para chegar ao k-ésimo elemento é preciso percorrer nó por nó, então o acesso é O(n), diferente do array que é O(1) por índice.
Aqui vale o segredo do morcego: "ponteiro é ponteiro, caixinha é caixinha". São duas coisas separadas dentro do mesmo nó. Quando você move um ponteiro, você não está copiando ou destruindo a caixinha, só está reescrevendo pra qual endereço ele aponta. É esse detalhe que confunde muita gente no início e é a causa da maioria dos bugs de segmentation fault: tentar acessar o dado de uma caixinha usando um ponteiro que não aponta pra lugar nenhum (NULL) ou que já foi liberado.
A vantagem principal é a inserção e remoção eficientes (O(1) se você já tem o ponteiro do nó), sem precisar deslocar elementos como em um array. Isso também significa que a lista não tem limite fixo de tamanho, crescendo conforme a memória disponível. Uma boa prática é manter também um ponteiro para o tail, evitando ter que percorrer tudo para inserir no fim.
Existem variações importantes: lista simplesmente encadeada (só next), duplamente encadeada (next e prev, permite andar nos dois sentidos) e circular (o último nó aponta de volta pro primeiro, útil em problemas tipo Josephus). Vale treinar a implementação manual dos nós antes de usar bibliotecas prontas.
struct No {
int valor;
No* proximo;
};