Lista Genérica

Nesta unidade, iremos implementar uma lista genérica. As funções de callback serão armazenadas no construtor da lista, dando um toque mais profissional para nosso programa.

Interface

list.h

#include <stdbool.h>
#include <stddef.h>

typedef void(*cb_free)(void *);
typedef int(*cb_compare)(void *a, void *b);

typedef struct node {
    void* data;          // Ponteiro genérico para o dado
    struct node* next;
} Node;

typedef struct {
    site_t data_size;
    Node *head; 
    // Funções de callback para o tipo de dado
    cb_free free_data;
    cb_compare compare_data;
} List;


List* list_create (size_t data_size, cb_free free_data, cb_compare compare_data);
void list_destroy (List *list);
void list_add (List *list, void *data);
bool list_contains (List *list, void *data);

Nossa lista é bastante simples. Cada nó possui um dado e um ponteiro para o próximo nó. Já a estrutura lista é composta pelo tamanho do dado, um ponteiro para a cabeça da lista e duas funções de callback. As funções declaradas serão usadas para criar uma lista, liberar a memória da lista, adicionar um novo nó e determinar se um nó pertence a uma lista.

Implementação

Importando as bibliotecas.

list.c

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

Criar Lista

A primeira função que iremos implementar é o construtor da lista, list_create. O primeiro paramêtro é o tamanho em bytes do dado que iremos armazenar na lista. Depois as funções de callback para liberar a memória desse dado e como comparar dois dados.

list.c

List *list_create(size_t data_size, cb_free free_data, cb_compare compare_data) {
    assert(data_size > 0);  

    List *list = malloc(sizeof(List));
    list->data_size = data_size;
    list->head = NULL;
    list->free_data = free_data;
    list->compare_data = compare_data;
    return list;
}

Como a lista inicia vazia, logo a cabeça da lista será NULL.

Adicionar Elementos

Após criar a lista, temos de adicionar nós a ela. A função list_add aloca memória duas vezes, uma para o nó e outra para o dado. Não podemos fazer um simples atribuição com = para passar o dado para o campo data do nó. Portanto, usamos a função memcpy que estudamos na seção sobre gerenciamento de memória.

list.c

void list_add(List *list, void *data) {
    assert(list != NULL);
    assert(data != NULL);

    Node *newNode = calloc(1, sizeof(Node));
    newNode->data = malloc(list->data_size);
    memcpy(newNode->data, data, list->data_size);

    newNode->next = list->head;
    list->head = newNode;
}

Essa função adiciona elementos na cabeça da lista: o novo nó aponta para a cabeça da lista (linha 9) e depois a cabeça da lista é atualizada para o novo nó (linha 10).

Apagar Lista

Precisamos criar o destrutor da lista. Mas antes temos de implementar a free_node_data. Ela serve para liberar a memória alocada para o dado que é armazenado na lista. Esse dado pode ser mais complexo do que pensamos (algum struct com alocação interna). Por isso, passamos um função callback para tratar esses casos. Por outro lado, para uma lista de inteiros ou outro tipo simples, um free é suficiente.

list.c

static void free_node_data(cb_free free_data, void *data) { 
    if (free_data != NULL) 
        free_data(data); 
    else 
        free(data); 
}

Mote que essa função não foi declarada no arquivo .h e isso significa que ela é privada. O modificador static indica isso para nós.

A lógica do destrutor é simples. Após a verificação de segurança do assert, criamos um nó que aponta para a cabeça da lista. Em seguida, caminhamos na lista em direção a cauda. Nesse percurso, liberamos a memória do dado e depois do nó. Quando acabamos o percurso, liberaramos a estrutura lista.

list.c

void list_destroy(List *list){
    assert(list != NULL);
    
    Node *node = list->head;
        
    while (node != NULL){
        Node *next = node->next; // guarda o próximo antes de liberar
        free_node_data(list->free_data, node->data);
        free(node);
        node = next;
    }

    free(list);
}

Note que usamos três liberações de memória. Uma para o dado (linha 8), uma para o nó (linha 9) e outra para a lista (linha 13). Isso porque usamos a alocação de memória três vezes, uma em list_create e duas em list_add. Lembre-se do que estudamos, para cada alocação deve haver um liberação correspondente.

Procurar Elementos

Uma das funções que declaramos em nossa interface foi list_contains. Ela será usada para saber se algum elemento existe dentro da lista. Ela só retorna sim ou não.

list.c

bool list_contains(List *list, void *data) {
    assert(list->compare_data != NULL);
    
    Node *node = list->head;
    while (node != NULL)    {
        if (list->compare_data(node->data, data) == 0)
            return true;        
        node = node->next;
    }
    return false;
}

Se liga! É uma boa prática implementar a função de comparação da seguinte forma:

Se a < b, retorne um número negativo
Se a = b, retorne zero
Se a > b, retorne um número positivo

Note que para tipos primitivos, como inteiros, a igualdade é simples (a == b). Contudo, nossa lista armazena dados de forma genérica (void *data), o que significa que o operador == só compararia os endereços de memória dos dados, e não o seu conteúdo lógico. Por isso, o callback compare_data é essencial: ele permite que o usuário defina a lógica de comparação correta para tipos complexos, como um struct de aluno (onde a igualdade pode depender, por exemplo, do ID ou Matrícula).

Exemplo de Uso

Importando as bibliotecas e API da lista que criamos.

int_list.c

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

Função de callback para comparar dois inteiros.

int_list.c

// Callback para comparar dois inteiros
int compare_int(void *a, void *b) {
    int x = *(int*)a;
    int y = *(int*)b;
    return x - y;
}

Se liga! Não vamos precisar de um função callback para liberar um inteiro, pois nossa função free_node_data já trata esse caso se passarmos NULL como argumento para list_create.

Lembre-se, o padrão é que retorne zero se ambos são iguais.

Função principal:

int_list.c

int main() {

    // Criar uma lista de inteiros
    List *list = list_create(sizeof(int), NULL, compare_int);
    int item[5] = {2, 5, 3, 8, 9};
 
    // Adicionar elementos
    for (int i = 0; i < 5; i++) {
        int *data = malloc(sizeof(int));
        *data = item[i];
        list_add(list, data);
        free(data);
    }

    // Verificar se um valor está na lista
    int search_key = 8;
    
    printf("Procurando nó com chave: %d...\n", search_key);
    
    if (list_contains(list, &search_key))
        printf("-> Sucesso: Chave %d encontrada!\n", search_key);
    else 
        printf("-> Falha: Chave %d não encontrada.\n", search_key);
    
    printf("----------------------------------------\n");

    
    // Destruir a lista    
    list_destroy(list);
    list = NULL;

    return 0;
}

Para demonstrar o poder da nossa lista genérica, vamos criar uma lista de anulos, onde cada aluno é uma struct.

student_list.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "list.h" 

typedef struct student {
    char* name;
    int id;
} Student;

int compare_student(void *a, void *b) {
    Student *student_a = (Student *)a;
    Student *student_b = (Student *)b;

    return student_a->id - student_b->id;
}

void free_student(void *data) {
    Student *student_ptr = (Student *)data;
    
    if (student_ptr == NULL) 
        return; 
    
    if (student_ptr->name != NULL) 
        free(student_ptr->name); 
    
    free(student_ptr);
}

Função auxiliar para criar um aluno.

student_list.c

Student *create_student(const char *name, int id) {
    Student *new_student = (Student *)malloc(sizeof(Student));
    if (new_student == NULL) {
        fprintf(stderr, "Erro ao alocar Student\n");
        return 1; 
    }

    new_student->id = id;
    
    // strdup faz o malloc interno e a cópia.
    new_student->name = strdup(name); 
    if (new_student->name == NULL) {
        free(new_student); // Limpeza em caso de falha de alocação do nome
        fprintf(stderr, "Erro ao alocar nome\n");
        return 1; 
    }

    return new_student;
}

Se liga! Internamente, strdup faz:

char *new_name = malloc(strlen(name) + 1);
strcpy(new_name, name);

Note que o free correspondente ao malloc de strdup está no callback free_student, no segundo if.

Agora estamos prontos para simular uma lista de alunos.

student_list.c

int main() {

    // Criar um  lista de alunos
    List *list = list_create(sizeof(Student), free_student, compare_student);

    // Nomes e IDs
    const char *names[] = {"Alice", "Bob", "Charlie", "Diana"};
    int ids[] = {101, 205, 303, 408};

    // Adicionar elementos
    for (int i = 0; i < 4; i++) {
        Student *s = create_student(names[i], ids[i]);
        list_add(list, s); 
    }
   
    // Verificar se um aluno está na lista
    Student search_key = {.name = NULL, .id = 303}; 
    
    printf("Procurando aluno com ID: %d...\n", search_key.id);
    
    if (list_contains(list, &search_key)) 
        printf("-> Sucesso: Aluno ID %d encontrado!\n", search_key.id);
    else
        printf("-> Falha: Aluno ID %d não encontrado.\n", search_key.id);
    
    printf("----------------------------------------\n");

    // Destruir a lista
    list_destroy(list); 
    list = NULL;

    return 0;
}

A implementação desta lista genérica garante alta modularidade. Graças ao design baseado em funções callback, evitamos a reimplementação de funções centrais (como criação, adição ou destruição). Para adaptar a lista a qualquer novo tipo de dado, basta fornecer os callbacks específicos para a comparação e liberação de memória daquele tipo.

🎯 Desafio de Código

Defina uma nova assinatura para um função callback chamada cb_iterate e adicione a declaração da função list_iterate no arquivo de cabeçalho (list.h).

typedef bool(*cb_iterate)(int index, void *data);
void list_iterate(LinkedList *list, cb_iterate iterate_callback);

Depois, na implementação (list.c) escreva a o código para essa função.

void list_iterate(LinkedList *list, cb_iterate iterate_callback) {
    assert(list != NULL);
    assert(iterate_callback != NULL);

    Node *current = list->head;  
    int index = 0;               

    // Enquanto ainda houver nós para visitar
    while (current != NULL) {
        // Chamamos a função de callback para o nó atual.
        bool continuar = iterate_callback(index, current->data);

        // Se a função de callback retornar 'false', paramos a iteração
        if (!continuar) break;

        // Avançamos para o próximo nó
        current = current->next;
        index++;
    }
}

Implemente uma funçao callback para imprimir a lista de inteiros. Ela deve ter a mesma assinatura de cb_iterate:

bool print_int(int index, void *data);

Exemplo de uso:

printf("Conteúdo da lista:\n");
list_iterate(list, print_int);

Solução (clique para ver)

// Callback para iterar e imprimir
bool print_int(int index, void *data) {
    int value = *(int*)data;
    printf("[%d]: %d\n", index, value);
    return true; // continuar a iteração
}

Conclusão

Com a lista genérica implementada, concluímos com sucesso a exploração de um dos temas mais poderosos em programação C: o design de estruturas de dados independentes de tipo.

O verdadeiro valor deste exercício não está apenas no código da lista, mas nos conceitos transferíveis que você aprendeu. A utilização estratégica de ponteiros para funções (callbacks) e a rigorosa gestão da memória via Heap são os pilares que sustentam a criação de qualquer estrutura avançada. Você agora tem o conhecimento necessário para replicar essa arquitetura em pilhas, filas, árvores genéricas e além.

Este trabalho estabelece a base para o desenvolvimento profissional, alinhando seu código com os padrões utilizados nas bibliotecas de software de código aberto mais robustas. Você não apenas criou uma lista; você adquiriu um modelo de design para resolver problemas complexos com elegância.

Nesta unidade, você aprendeu

✅ a criar uma lista ligada genérica simples

# Qual é o principal objetivo da estrutura `List` apresentada? > Pense na abstração que ela representa. 1. [ ] Armazenar apenas inteiros de forma sequencial. 1. [x] Permitir o armazenamento de dados genéricos com callbacks para operações específicas. 1. [ ] Substituir arrays fixos por vetores dinâmicos. 1. [ ] Gerenciar automaticamente a memória da heap sem intervenção do usuário. # Qual é a função do campo `data_size` dentro da estrutura `List`? > Ele é essencial para manipular dados genéricos. 1. [x] Indicar o tamanho em bytes do tipo de dado armazenado. 1. [ ] Controlar o número total de nós da lista. 1. [ ] Identificar o tipo de dado armazenado (inteiro, float etc.). 1. [ ] Servir como índice de posição atual na lista. # Qual é a principal diferença entre o campo `free_data` e a função `free` padrão? > Observe o papel do callback no gerenciamento de memória. 1. [x] `free_data` permite liberar dados complexos com lógica personalizada. 1. [ ] `free_data` é usada apenas para liberar a estrutura `List`. 1. [ ] `free_data` substitui a função `malloc`. 1. [ ] Não há diferença — ambas fazem exatamente a mesma coisa. # No contexto da função `list_add`, por que é necessário usar `memcpy`? > Lembre-se de que `data` é um ponteiro genérico. 1. [x] Para copiar o conteúdo do dado em vez do endereço. 1. [ ] Para liberar a memória de origem após a cópia. 1. [ ] Porque `malloc` não inicializa a memória corretamente. 1. [ ] Para evitar que o ponteiro `data` fique nulo. # Quais afirmações sobre a função `list_create` estão corretas? > Considere os parâmetros e suas funções. - [x] Recebe o tamanho do dado a ser armazenado. - [x] Recebe ponteiros de função para liberar e comparar dados. - [ ] Aloca apenas o nó inicial da lista. - [ ] Cria automaticamente um primeiro elemento. # Quais são os três tipos de alocação de memória usados ao longo da implementação? > Pense no ciclo completo da lista. - [x] Alocação para a estrutura `List`. - [x] Alocação para cada `Node`. - [x] Alocação para o campo `data` em cada nó. - [ ] Alocação para cada chamada de comparação. # Coloque em ordem as etapas da função `list_destroy`. > Ela percorre e libera a lista corretamente. 1. Criar um ponteiro auxiliar para o nó inicial. 2. Guardar o próximo nó antes de liberar o atual. 3. Liberar o dado interno com `free_node_data`. 4. Liberar o nó atual. 5. Repetir até o final e liberar a estrutura `List`. # Por que `compare_data` é necessário em uma lista genérica? > Ele garante a comparação lógica correta dos dados. 1. [x] Porque `==` apenas compara endereços de memória. 1. [ ] Porque ele substitui o operador `sizeof`. 1. [ ] Porque o compilador não aceita comparação de `void *`. 1. [ ] Porque ele é obrigatório para listas de inteiros. # Em relação ao uso de `assert`, assinale as opções verdadeiras. > Elas são fundamentais para segurança em C. - [x] Garante que ponteiros não sejam nulos antes do uso. - [x] É usada para detectar falhas de pré-condição em tempo de execução. - [ ] É um comando que substitui `if`. - [ ] Impede o programa de compilar se a condição for falsa. # Quais práticas são adequadas ao manipular listas genéricas? > Pense em modularidade e segurança. - [x] Passar callbacks apropriados para cada tipo de dado. - [x] Liberar todos os recursos com `list_destroy` após o uso. - [ ] Usar o operador `==` diretamente em ponteiros `void *`. - [ ] Atribuir dados com `=` sem `memcpy`. # Coloque na ordem correta as etapas executadas pela função `list_add`. > Ela insere o elemento na cabeça da lista. 1. Criar um novo nó com `calloc`. 2. Alocar memória para o campo `data`. 3. Copiar o conteúdo do dado com `memcpy`. 4. Fazer o novo nó apontar para a cabeça atual. 5. Atualizar a cabeça da lista para o novo nó. # Sobre o uso de `strdup` na criação de um aluno, marque as opções corretas. > Lembre-se que `strdup` também faz alocação. - [x] Ela aloca memória e copia a string de origem. - [x] O `free` correspondente ocorre em `free_student`. - [ ] É equivalente a `strcpy`. - [ ] Não precisa de tratamento de erro após chamada. # Qual problema ocorreria se esquecêssemos de liberar `student->name` em `free_student`? > Ocorre com dados compostos alocados internamente. 1. [ ] *Segmentation fault* 1. [ ] *Double free* 1. [x] *Memory leak* 1. [ ] *Buffer overflow* # Quais vantagens o uso de callbacks traz para a implementação da lista? > Pense em reuso e generalização. - [x] Permite adaptar a lista a diferentes tipos de dados. - [x] Evita duplicação de código em diferentes listas. - [ ] Aumenta a velocidade de execução do programa. - [ ] Impede a ocorrência de erros de alocação. # Coloque em ordem as etapas da função `list_contains`. > Ela percorre e compara os dados. 1. Inicia em `head`. 2. Compara o dado do nó com o elemento buscado usando `compare_data`. 3. Retorna `true` se a comparação for igual a zero. 4. Avança para o próximo nó. 5. Retorna `false` se atingir o final sem encontrar. # Quais são os parâmetros da função `list_iterate` no desafio proposto? > Eles controlam o fluxo da iteração. - [x] Um ponteiro para a lista. - [x] Um ponteiro para função `cb_iterate`. - [ ] O número de nós da lista. - [ ] Um vetor de ponteiros para dados. # O que ocorre se o callback em `list_iterate` retornar `false`? > Veja o controle de fluxo dentro da função. 1. [x] A iteração é interrompida imediatamente. 1. [ ] A iteração reinicia do início. 1. [ ] O nó atual é removido. 1. [ ] O programa encerra a execução. # Quais boas práticas são aplicadas na função `create_student`? > Observe o tratamento de erros e alocações. - [x] Verificar se o `malloc` retornou `NULL`. - [x] Liberar memória parcialmente alocada em caso de falha. - [ ] Ignorar erros de alocação. - [ ] Retornar `1` para indicar sucesso na alocação. # Coloque em ordem o ciclo de vida completo de um elemento na lista de alunos. > Do início até a liberação final. 1. Criar `Student` com `malloc` e `strdup`. 2. Adicionar à lista com `list_add`. 3. Buscar elemento com `list_contains`. 4. Destruir lista com `list_destroy`. 5. Liberar memória de cada aluno via `free_student`. # Quais conceitos fundamentais da linguagem C são consolidados nesta unidade? > Eles formam a base para estruturas genéricas. - [x] Ponteiros para funções (*callbacks*). - [x] Manipulação de memória dinâmica. - [x] Estruturas genéricas com `void *`. - [ ] Recursividade em tempo de compilação.

De volta ao topo