🚀 Capítulo 15: Estruturas de Dados — Listas Encadeadas Dinâmicas em C

🎯 Objetivos da Aula

Ao final desta aula, você será capaz de:

1. Compreender as limitações de vetores estáticos e a vantagem das Listas Encadeadas Dinâmicas.
2. Definir a estrutura de um Nó (Node) contendo dado e ponteiro para o próximo nó.
3. Implementar operações fundamentais de inserção no início, inserção no fim e percorrimento da lista.
4. Liberar adequadamente toda a memória da lista com free() nó por nó.

---

🧠 1. O que é uma Lista Encadeada Simples?

Diferente dos vetores, onde os elementos ocupam posições contíguas na memória, uma Lista Encadeada armazena elementos dispersos na memória Heap, conectados através de ponteiros.

flowchart LR
    Head["Ponteiro inicio\n(Head)"] --> Node1["No 1\n[ Dado: 10 | prox ]"]
    Node1 --> Node2["No 2\n[ Dado: 20 | prox ]"]
    Node2 --> Node3["No 3\n[ Dado: 30 | prox ]"]
    Node3 --> NullNode["NULL"]

Anatomia de um Nó em C:

typedef struct No {
    int valor;           // Carga útil de dados
    struct No *proximo;  // Ponteiro para o proximo No na memoria
} No;

---

💻 2. Prática Guiada: Implementação de Lista Encadeada em C

Let’s write the complete, executable program lista_encadeada.c:

#include <stdio.h>
#include <stdlib.h>
 
// Definicao da estrutura do No
typedef struct No {
    int valor;
    struct No *proximo;
} No;
 
// Função para inserir um novo No no INÍCIO da lista
No* inserirInicio(No *inicio, int valor) {
    No *novoNo = (No*) malloc(sizeof(No));
    if (novoNo == NULL) {
        printf(">> Erro de alocacao de memoria!\n");
        return inicio;
    }
    novoNo->valor = valor;
    novoNo->proximo = inicio; // O novo nó aponta para o antigo início
    return novoNo;            // O novo nó passa a ser o inicio da lista
}
 
// Função para imprimir todos os elementos da lista
void exibirLista(No *inicio) {
    No *atual = inicio;
    printf("\n[Inicio] -> ");
    while (atual != NULL) {
        printf("[%d] -> ", atual->valor);
        atual = atual->proximo; // Avanca para o proximo No
    }
    printf("[NULL]\n");
}
 
// Função para liberar toda a memoria da lista
void liberarLista(No *inicio) {
    No *atual = inicio;
    while (atual != NULL) {
        No *temp = atual;
        atual = atual->proximo;
        free(temp); // Libera o nó atual
    }
    printf(">> Memoria de todos os nos liberada com sucesso.\n");
}
 
int main() {
    No *lista = NULL; // Lista inicialmente vazia
    
    printf("Inserindo elementos 30, 20 e 10 no inicio...\n");
    lista = inserirInicio(lista, 30);
    lista = inserirInicio(lista, 20);
    lista = inserirInicio(lista, 10);
    
    exibirLista(lista);
    
    liberarLista(lista);
    lista = NULL;
    
    return 0;
}

---

⚔️ 3. Desafios Práticos (Exercícios 30/50/20)

🥉 Nível Bronze (Fixação)

1. Qual a principal vantagem de uma Lista Encadeada em relação a um Vetor (Array) estático com relação à inserção de elementos?
2. Por que é necessário salvar a referência do próximo nó (atual->proximo) em uma variável temporária antes de chamar free(atual) ao liberar a lista?

🥈 Nível Prata (Aplicação)

3. Escreva a função int contarElementos(No *inicio) que percorra a lista encadeada e retorne a quantidade total de nós atualmente alocados.

🥇 Nível Ouro (Desafio)

4. Implemente a função No* inserirFim(No *inicio, int valor) que percorra a lista até encontrar o último nó (cujo proximo == NULL) e anexe o novo nó no final da lista encadeada.

---

💡 Gabaritos Sanfonados de Resposta

💡 Ver Gabarito do Nível Bronze

1. A lista encadeada permite inserção de novos elementos sem necessidade de realocar todo o vetor contíguo na memória ou definir um limite máximo em tempo de compilação.
2. Se chamarmos free(atual) primeiro, perderemos o endereço armazenado em atual->proximo, tornando impossível avançar para o restante da lista (Dangling Pointer / Memory Leak).

💡 Ver Gabarito do Nível Prata & Ouro (Código C)

#include <stdio.h>
#include <stdlib.h>
 
typedef struct No {
    int valor;
    struct No *proximo;
} No;
 
int contarElementos(No *inicio) {
    int contador = 0;
    No *atual = inicio;
    while (atual != NULL) {
        contador++;
        atual = atual->proximo;
    }
    return contador;
}

---

📚 Referências Teóricas Oficiais

• CORMEN, Thomas H. et al.. Algoritmos: Teoria e Prática. 3ª Edição. Elsevier, 2012. Cap. 10 (Estruturas de Dados Elementares — Listas Encadeadas).
• KERNIGHAN, Brian W.; RITCHIE, Dennis M.. A Linguagem de Programação C. 2ª Edição. Campus, 1989. Cap. 6 (Estruturas Auto-Referenciadas).

---

⬅️ Capítulo Anterior (Manipulação de Arquivos) | Voltar ao Sumário | Próximo Capítulo (Pilhas e Filas) ➡️