Aula 38 — Lista Ligada com Implementação Dinâmica

De estática para dinâmica

Na Aula 37 aprendemos a modelar e gerenciar listas ligadas usando a implementação estática: um array de tamanho fixo MAX armazenava todos os registros, e duas cadeias de cursores controlavam quais posições estavam em uso e quais estavam disponíveis.

Hoje aprenderemos a implementação dinâmica: alocaremos e desalocaremos a memória para cada elemento sob demanda, usando malloc e free.

Ideia geral: ponteiros como endereços reais

Na implementação estática, o campo prox guardava um índice (número inteiro). Na dinâmica, ele guarda um endereço de memória real — que é exatamente o que um ponteiro armazena.

O marcador de fim de lista deixa de ser INVALIDO = −1 e passa a ser NULL — o endereço nulo, universalmente reconhecido em C.

Modelagem: as estruturas de dados

A struct do nodo agora contém um ponteiro para o próprio tipo — a struct auto-referenciada. O nome-tag aux é necessário porque o typedef ainda não está completo quando o campo prox é declarado.

#include <stdio.h>
#include <stdlib.h>    /* malloc e free */
#include <stdbool.h>

#define ERRO -1

typedef int TIPOCHAVE;

typedef struct {
    TIPOCHAVE chave;
    // outros campos do registro...
} REGISTRO;

/* Nodo: dado + ponteiro para o próximo nodo */
typedef struct aux {
    REGISTRO    reg;
    struct aux* prox;   /* struct auto-referenciada */
} ELEMENTO;

/* Apelido de tipo: PONT é um ponteiro para ELEMENTO */
typedef ELEMENTO* PONT;

/* Cabeça da lista: apenas o ponteiro para o 1º nodo */
typedef struct {
    PONT inicio;   /* NULL = lista vazia */
} LISTA;

Inicialização

Inicializar a lista dinâmica é muito mais simples do que na versão estática: basta apontar inicio para NULL. Não há array a preparar, nem cadeia de disponíveis a montar.

void inicializarLista(LISTA* l) {
    l->inicio = NULL;   /* lista vazia — nenhum nodo alocado ainda */
}

Retornar o número de elementos

Não há campo nroElem. Para contar os nodos, percorremos a cadeia a partir de inicio até encontrar NULL:

int tamanho(LISTA* l) {
    PONT p   = l->inicio;
    int  tam = 0;
    while (p != NULL) {
        tam++;
        p = p->prox;   /* avança para o próximo nodo */
    }
    return tam;
}

Exibição / Impressão

O padrão de travessia é idêntico ao de tamanho: ponteiro auxiliar p percorre a cadeia até NULL, imprimindo a chave de cada nodo:

void exibirLista(LISTA* l) {
    PONT p = l->inicio;
    printf("Lista: \" ");
    while (p != NULL) {
        printf("%i ", p->reg.chave);
        p = p->prox;
    }
    printf("\"\n");
}

Busca auxiliar: buscaSequencialExc

Tanto a inserção quanto a exclusão precisam de dois endereços ao mesmo tempo:

• O endereço do elemento com a chave buscada (se ele existir).
• O endereço do predecessor desse elemento — independentemente de ele existir ou não na lista.

Uma única função pode resolver as duas perguntas de uma vez. Mas como retornar dois endereços diferentes? Em C, uma função tem apenas um valor de retorno. A solução é passar um ponteiro para ponteiro (PONT* ant) como parâmetro de saída: a função escreve o predecessor em *ant e retorna o elemento encontrado (ou NULL).

/* Busca auxiliar: retorna o nodo com chave ch (ou NULL se não existir)
   e escreve em *ant o endereço do predecessor (NULL se for o 1º).
   Usada como base de inserção e exclusão.                           */
PONT buscaSequencialExc(LISTA* l, TIPOCHAVE ch, PONT* ant) {
    *ant  = NULL;
    PONT atual = l->inicio;
    while ((atual != NULL) && (atual->reg.chave < ch)) {
        *ant  = atual;
        atual = atual->prox;
    }
    if ((atual != NULL) && (atual->reg.chave == ch))
        return atual;
    return NULL;
}

Inserção de um elemento

Com buscaSequencialExc disponível, a inserção fica limpa: chamamos a auxiliar para obter simultaneamente se o elemento já existe (duplicata) e quem seria seu predecessor. Depois alocamos o nodo e ajustamos dois ponteiros.

bool inserirElemListaOrd(LISTA* l, REGISTRO reg) {
    PONT ant;
    PONT p = buscaSequencialExc(l, reg.chave, &ant);

    /* duplicata: rejeita */
    if (p != NULL) return false;

    /* ── aloca o novo nodo ── */
    PONT novo = (PONT) malloc(sizeof(ELEMENTO));
    if (novo == NULL) return false;   /* sem memória disponível */

    novo->reg  = reg;
    novo->prox = p;   /* p == NULL aqui, mas aponta para quem virá depois */

    /* ── encadeia o novo nodo ── */
    if (ant == NULL)
        l->inicio = novo;   /* inserção no início (lista vazia ou menor elemento) */
    else
        ant->prox = novo;   /* inserção no meio ou no final */

    return true;
}

O papel do malloc

malloc(sizeof(ELEMENTO)) solicita ao sistema operacional exatamente o número de bytes necessários para um ELEMENTO e retorna o endereço do bloco alocado. Se não houver memória disponível, retorna NULL — sempre verifique esse retorno antes de usar o ponteiro.

Exclusão de um elemento

Assim como na inserção, a exclusão usa buscaSequencialExc para obter simultaneamente o nodo a remover e seu predecessor. Se o nodo existir, desligamos da cadeia e chamamos free:

bool excluirElemLista(LISTA* l, TIPOCHAVE ch) {
    PONT ant;
    PONT p = buscaSequencialExc(l, ch, &ant);

    /* não encontrou */
    if (p == NULL) return false;

    /* desliga o nodo da cadeia */
    if (ant == NULL)
        l->inicio = p->prox;    /* era o primeiro elemento */
    else
        ant->prox = p->prox;    /* meio ou final */

    free(p);    /* devolve a memória ao sistema operacional */
    return true;
}

Reinicializar a lista

Na versão estática, reinicializar era simples: bastava ajustar inicio e dispo porque a memória do array pertencia à struct e seria liberada quando o escopo terminasse.

Na versão dinâmica, cada nodo foi alocado individualmente com malloc e precisa ser liberado individualmente com free — caso contrário, ocorre vazamento de memória (memory leak):

void reinicializarLista(LISTA* l) {
    PONT p = l->inicio;
    while (p != NULL) {
        PONT aux = p->prox;   /* salva o próximo ANTES de liberar p */
        free(p);
        p = aux;              /* avança com o ponteiro salvo        */
    }
    l->inicio = NULL;
}

Comparação lado a lado: estática × dinâmica

As operações são estruturalmente idênticas — o que muda é apenas o mecanismo de gerenciamento de memória:

Exemplo completo com todas as operações

int main() {
    LISTA l;
    REGISTRO r;

    inicializarLista(&l);
    exibirLista(&l);
    printf("Tamanho: %d\n\n", tamanho(&l));

    /* Inserções fora de ordem — a lista se auto-ordena */
    r.chave = 7; inserirElemListaOrd(&l, r);
    r.chave = 3; inserirElemListaOrd(&l, r);
    r.chave = 9; inserirElemListaOrd(&l, r);
    r.chave = 1; inserirElemListaOrd(&l, r);
    r.chave = 5; inserirElemListaOrd(&l, r);
    exibirLista(&l);
    printf("Tamanho: %d\n\n", tamanho(&l));

    /* Inserção de duplicata */
    r.chave = 3;
    if (!inserirElemListaOrd(&l, r))
        printf("Inserção de 3 recusada: elemento já existe\n\n");

    /* Busca */
    PONT ant_busca;
    PONT pos = buscaSequencialExc(&l, 9, &ant_busca);
    if (pos != NULL)
        printf("Chave 9 encontrada (endereço %p)\n", (void*)pos);
    pos = buscaSequencialExc(&l, 4, &ant_busca);
    if (pos == NULL)
        printf("Chave 4 não encontrada\n\n");

    /* Exclusões */
    if (excluirElemLista(&l, 3)) printf("Chave 3 excluída\n");
    if (excluirElemLista(&l, 1)) printf("Chave 1 excluída\n");
    if (!excluirElemLista(&l, 8)) printf("Chave 8 não encontrada\n\n");

    exibirLista(&l);
    printf("Tamanho: %d\n\n", tamanho(&l));

    /* Libera toda a memória antes de encerrar */
    reinicializarLista(&l);
    exibirLista(&l);
    printf("Tamanho: %d\n", tamanho(&l));

    return 0;
}

Código-fonte completo

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ERRO -1
typedef int TIPOCHAVE;
typedef struct { TIPOCHAVE chave; } REGISTRO;

typedef struct aux { REGISTRO reg; struct aux* prox; } ELEMENTO;
typedef ELEMENTO* PONT;
typedef struct { PONT inicio; } LISTA;

/* ── Inicialização ── */
void inicializarLista(LISTA* l) { l->inicio = NULL; }

/* ── Tamanho ── */
int tamanho(LISTA* l) {
    PONT p = l->inicio; int tam = 0;
    while (p != NULL) { tam++; p = p->prox; }
    return tam;
}

/* ── Exibição ── */
void exibirLista(LISTA* l) {
    PONT p = l->inicio;
    printf("Lista: \" ");
    while (p != NULL) { printf("%i ", p->reg.chave); p = p->prox; }
    printf("\"\n");
}

/* ── Busca auxiliar ── */
PONT buscaSequencialExc(LISTA* l, TIPOCHAVE ch, PONT* ant) {
    *ant = NULL;
    PONT atual = l->inicio;
    while ((atual != NULL) && (atual->reg.chave < ch)) { *ant = atual; atual = atual->prox; }
    if ((atual != NULL) && (atual->reg.chave == ch)) return atual;
    return NULL;
}

/* ── Inserção ── */
bool inserirElemListaOrd(LISTA* l, REGISTRO reg) {
    PONT ant;
    PONT p = buscaSequencialExc(l, reg.chave, &ant);
    if (p != NULL) return false;
    PONT novo = (PONT) malloc(sizeof(ELEMENTO));
    if (novo == NULL) return false;
    novo->reg = reg; novo->prox = p;
    if (ant == NULL) l->inicio = novo;
    else ant->prox = novo;
    return true;
}

/* ── Exclusão ── */
bool excluirElemLista(LISTA* l, TIPOCHAVE ch) {
    PONT ant;
    PONT p = buscaSequencialExc(l, ch, &ant);
    if (p == NULL) return false;
    if (ant == NULL) l->inicio = p->prox;
    else ant->prox = p->prox;
    free(p);
    return true;
}

/* ── Reinicialização ── */
void reinicializarLista(LISTA* l) {
    PONT p = l->inicio;
    while (p != NULL) { PONT aux = p->prox; free(p); p = aux; }
    l->inicio = NULL;
}

Resumo: o que você precisa saber desta aula