C Estruturas de dados Intermediário
Lista encadeada
Uma lista encadeada é uma estrutura de dados dinâmica formada por nós que contêm um valor e um ponteiro para o próximo nó. Diferente de um vetor, os elementos não ficam em posições contíguas de memória, mas conectados por ponteiros. Isso permite inserções e remoções eficientes sem realocação, ao custo de acesso sequencial e uso extra de memória para os ponteiros.
Cada nó é uma struct com um campo de dados e um ponteiro para o próximo nó (struct No *prox). O último nó aponta para NULL, indicando o fim da lista. Para manipular a lista, mantemos um ponteiro para o primeiro nó (cabeça).
As operações básicas incluem inserção (no início, no fim ou em posição específica), remoção (ajustando os ponteiros) e liberação de memória (percorrer a lista e liberar cada nó com free). É fundamental gerenciar corretamente a memória alocada com malloc para evitar vazamentos.
Pontos-chave
- Cada nó contém um dado e um ponteiro para o próximo nó.
- A lista é acessada por um ponteiro para o primeiro nó (cabeça).
- Inserção e remoção exigem atualização cuidadosa dos ponteiros.
- Sempre libere a memória de todos os nós com
freeao final. - Percorra a lista com um ponteiro auxiliar até encontrar
NULL.
#include <stdio.h>
#include <stdlib.h>
typedef struct No {
int valor;
struct No *prox;
} No;
// Insere no início da lista
No* inserir_inicio(No *head, int valor) {
No *novo = malloc(sizeof(No));
if (!novo) { perror("malloc"); exit(1); }
novo->valor = valor;
novo->prox = head;
return novo;
}
// Remove o primeiro nó com o valor dado
No* remover(No *head, int valor) {
No *ant = NULL, *atual = head;
while (atual && atual->valor != valor) {
ant = atual;
atual = atual->prox;
}
if (!atual) return head; // não encontrado
if (ant) ant->prox = atual->prox;
else head = atual->prox;
free(atual);
return head;
}
// Imprime a lista
void imprimir(No *head) {
for (No *p = head; p; p = p->prox)
printf("%d -> ", p->valor);
printf("NULL\n");
}
// Libera toda a memória
void liberar(No *head) {
while (head) {
No *prox = head->prox;
free(head);
head = prox;
}
}
int main(void) {
No *lista = NULL;
lista = inserir_inicio(lista, 10);
lista = inserir_inicio(lista, 20);
lista = inserir_inicio(lista, 30);
imprimir(lista); // 30 -> 20 -> 10 -> NULL
lista = remover(lista, 20);
imprimir(lista); // 30 -> 10 -> NULL
liberar(lista);
return 0;
}