C Listas Ligadas

Um array guarda os valores colados na memória, um do lado do outro. Isso é ótimo para ler, mas ruim para crescer e para tirar coisas do meio. A lista ligada faz diferente: cada valor mora numa caixinha separada, criada com malloc, e cada caixinha guarda o endereço da próxima. Nesta aula você vai montar uma lista ligada do zero, inserir, percorrer, buscar, remover e devolver toda a memória, conferindo com o valgrind que nada vazou.

Esta aula usa structs, a seta -> e malloc e free. Todos os programas foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa. Quando aparecer -g, é para o valgrind mostrar o arquivo e a linha (veja Valgrind).

A ideia: a caça ao tesouro

Pense numa caça ao tesouro. Você recebe o primeiro bilhete. Ele diz "a primeira pista é 10; o próximo bilhete está embaixo do vaso". No vaso, outro bilhete: "a pista é 20; o próximo está na gaveta". Na gaveta: "a pista é 30; acabou".

Os bilhetes estão espalhados pela casa, mas você nunca se perde, porque cada um diz onde está o próximo. Para chegar ao terceiro, você precisa passar pelo primeiro e pelo segundo. E para pôr um bilhete novo no começo, basta escrever nele "o próximo está onde estava o primeiro".

Uma lista ligada é isso. Compare com o array, que é uma fileira de armários colados, numerados:

1. O nó: uma struct que aponta para outra igual

Cada caixinha da lista é um nó (em inglês, node). Em C, um nó é uma struct com o valor e um ponteiro para o próximo nó:

struct No {
    int valor;
    struct No *prox;
};

struct No

O nome do tipo do nó. "No" é "nó" sem o acento, porque nomes em C não aceitam acentos (veja Nomes de Variáveis).

int valor;

O dado que a lista guarda. Aqui é um int, mas poderia ser um preço, um nome, uma struct inteira.

struct No *prox;

"Próximo". É um ponteiro para outro struct No: guarda o endereço do nó seguinte, ou NULL se este é o último.

Repare na esquisitice: dentro de struct No aparece struct No de novo. Isso se chama struct autorreferente ("que se refere a si mesma"). Funciona porque o campo é um ponteiro: um endereço tem sempre o mesmo tamanho (8 bytes no gcc do laboratório), não importa para que tipo ele aponta. O C não precisa saber o tamanho de struct No para reservar 8 bytes para um endereço.

Sem a estrela, não dá: um nó que contém um nó inteiro, que contém outro nó inteiro… teria tamanho infinito. O gcc recusa:

struct No {
    int valor;
    struct No prox;
};

int main(void) {
    return 0;
}

$ gcc -std=c23 -Wall -Wextra autoref.c -o autoref
autoref.c:3:15: error: field ‘prox’ has incomplete type
    3 |     struct No prox;
      |               ^~~~

Field ‘prox’ has incomplete type = "o campo ‘prox’ tem tipo incompleto". Na linha 3, o struct No ainda está sendo definido (o } não chegou), então o compilador não sabe o tamanho dele. Conserto: struct No *prox;, com a estrela.

2. Três nós ligados à mão e o primeiro percurso

Antes de usar malloc, vamos montar três nós como variáveis comuns e ligá-los com o operador & ("endereço de"). Isso mostra a ideia sem nenhuma outra novidade:

#include <stdio.h>

struct No {
    int valor;
    struct No *prox;
};

int main(void) {
    struct No c = {30, NULL};
    struct No b = {20, &c};
    struct No a = {10, &b};

    struct No *p = &a;
    while (p != NULL) {
        printf("%d\n", p->valor);
        p = p->prox;
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra tres.c -o tres
$ ./tres
10
20
30

3. Nós de verdade: criados com malloc

Nós em variáveis comuns somem quando a função termina, e você precisa saber de antemão quantos são. Numa lista de verdade, cada nó é criado com malloc ("memory allocation", reservar memória) na hora em que é preciso. Vamos escrever uma função que cria um nó e outra que o põe no início da lista:

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

struct No {
    int valor;
    struct No *prox;
};

struct No *novo_no(int valor) {
    struct No *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "Sem memória\n");
        exit(1);
    }
    n->valor = valor;
    n->prox = NULL;
    return n;
}

struct No *inserir_inicio(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    n->prox = lista;
    return n;
}

void imprimir(const struct No *lista) {
    for (const struct No *p = lista; p != NULL; p = p->prox) {
        printf("%d -> ", p->valor);
    }
    printf("NULL\n");
}

int main(void) {
    struct No *lista = NULL;
    imprimir(lista);
    lista = inserir_inicio(lista, 30);
    imprimir(lista);
    lista = inserir_inicio(lista, 20);
    imprimir(lista);
    lista = inserir_inicio(lista, 10);
    imprimir(lista);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra inicio.c -o inicio
$ ./inicio
NULL
30 -> NULL
20 -> 30 -> NULL
10 -> 20 -> 30 -> NULL

struct No *lista = NULL;

A lista começa vazia. Lista vazia = ponteiro NULL. Nunca deixe esse ponteiro sem valor inicial.

malloc(sizeof *n)

Reserva espaço para um nó. sizeof *n é "o tamanho daquilo para que n aponta"; se um dia o tipo mudar, a conta continua certa (o mesmo que sizeof(struct No)).

if (n == NULL)

O malloc devolve NULL quando não há memória. Confira sempre. Aqui o programa avisa no stderr e termina com exit(1) (veja exit).

n->prox = NULL;

Todo nó nasce "sozinho", sem próximo. Assim nenhum campo fica com lixo.

n->prox = lista;

O nó novo aponta para quem era o primeiro.

return n;

O nó novo passa a ser o primeiro. Quem chama precisa guardar esse retorno: lista = inserir_inicio(lista, 30);.

const struct No *

Em imprimir, o const promete que a função só lê os nós (veja const e Ponteiros).

Inserir no início, passo a passo

Veja o que acontece na última chamada, lista = inserir_inicio(lista, 10);, quando a lista já tem 20 e 30:

1. novo_no(10) cria o nó 10, sozinho, com prox em NULL.
2. n->prox = lista; faz o nó 10 apontar para o nó 20, o primeiro de agora.
3. return n; e lista = …: a variável lista passa a apontar para o nó 10.

Nada foi copiado nem empurrado: só duas setas mudaram. Por isso inserir no início leva o mesmo tempo com 3 ou com 3 milhões de nós.

Percorrer para contar, somar, imprimir

A função imprimir usa o laço que você guardou, na forma de for. Qualquer pergunta sobre "todos os nós" segue o mesmo molde: quantos são, qual a soma, qual o maior. Pratique:

Tamanho: 3

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

struct No {
    int valor;
    struct No *prox;
};

struct No *inserir_inicio(struct No *lista, int valor) {
    struct No *n = malloc(sizeof *n);
    if (n == NULL) {
        exit(1);
    }
    n->valor = valor;
    n->prox = lista;
    return n;
}

int contar(const struct No *lista) {
    int total = 0;
    // percorra a lista e some 1 para cada nó
    (void)lista;  // apague esta linha: ela só cala o aviso "unused parameter"
    return total;
}

void liberar(struct No *lista) {
    while (lista != NULL) {
        struct No *prox = lista->prox;
        free(lista);
        lista = prox;
    }
}

int main(void) {
    struct No *lista = NULL;
    lista = inserir_inicio(lista, 7);
    lista = inserir_inicio(lista, 5);
    lista = inserir_inicio(lista, 9);
    printf("Tamanho: %d\n", contar(lista));
    liberar(lista);
    return 0;
}

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

struct No {
    int valor;
    struct No *prox;
};

struct No *inserir_inicio(struct No *lista, int valor) {
    struct No *n = malloc(sizeof *n);
    if (n == NULL) {
        exit(1);
    }
    n->valor = valor;
    n->prox = lista;
    return n;
}

int contar(const struct No *lista) {
    int total = 0;
    for (const struct No *p = lista; p != NULL; p = p->prox) {
        total++;
    }
    return total;
}

void liberar(struct No *lista) {
    while (lista != NULL) {
        struct No *prox = lista->prox;
        free(lista);
        lista = prox;
    }
}

int main(void) {
    struct No *lista = NULL;
    lista = inserir_inicio(lista, 7);
    lista = inserir_inicio(lista, 5);
    lista = inserir_inicio(lista, 9);
    printf("Tamanho: %d\n", contar(lista));
    liberar(lista);
    return 0;
}

4. Inserir no fim

Para pôr um valor no fim, a lista precisa ser percorrida até o último nó, aquele cujo prox é NULL. Aí o prox do último passa a apontar para o nó novo:

struct No *inserir_fim(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    if (lista == NULL) {
        return n;
    }
    struct No *p = lista;
    while (p->prox != NULL) {
        p = p->prox;
    }
    p->prox = n;
    return lista;
}

5. Buscar um valor

Buscar é percorrer e parar quando achar. A função devolve o endereço do nó encontrado, ou NULL se o valor não está na lista:

struct No *buscar(struct No *lista, int valor) {
    for (struct No *p = lista; p != NULL; p = p->prox) {
        if (p->valor == valor) {
            return p;
        }
    }
    return NULL;
}

Devolver o nó (e não só "sim" ou "não") deixa quem chamou mudar o valor achado: struct No *x = buscar(lista, 30); if (x != NULL) x->valor = 35;. Sempre confira o NULL antes de usar a seta. Numa lista, buscar é sempre visitar nó por nó, do começo: não existe atalho como array[i]. Em listas grandes, isso pesa (a aula Busca compara as formas de buscar).

6. Remover um nó

Remover tem duas partes: religar a lista por cima do nó e depois liberar o nó com free. Para religar, você precisa do nó anterior, porque é o prox dele que muda. Por isso a função anda com dois ponteiros: ant (anterior) e p (atual):

struct No *remover(struct No *lista, int valor) {
    struct No *ant = NULL;
    struct No *p = lista;
    while (p != NULL && p->valor != valor) {
        ant = p;
        p = p->prox;
    }
    if (p == NULL) {
        return lista;
    }
    if (ant == NULL) {
        lista = p->prox;
    } else {
        ant->prox = p->prox;
    }
    free(p);
    return lista;
}

while (p != NULL && p->valor != valor)

Anda até achar o valor ou até a lista acabar. A ordem do && importa: se p for NULL, o C nem olha p->valor (veja Operadores Lógicos).

ant = p; p = p->prox;

Os dois andam juntos: ant fica sempre uma casa atrás de p.

if (p == NULL) return lista;

Não achou: devolve a lista do jeito que estava.

if (ant == NULL) lista = p->prox;

Achou no primeiro nó (não há anterior): a cabeça passa a ser o segundo.

ant->prox = p->prox;

Achou no meio ou no fim: o anterior "pula" o nó removido.

free(p);

Só agora, com a lista já religada, o nó é devolvido. Depois disso, p não pode mais ser usado.

O programa completo

Juntando tudo (com a função liberar, explicada logo abaixo):

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

struct No {
    int valor;
    struct No *prox;
};

struct No *novo_no(int valor) {
    struct No *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "Sem memória\n");
        exit(1);
    }
    n->valor = valor;
    n->prox = NULL;
    return n;
}

struct No *inserir_inicio(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    n->prox = lista;
    return n;
}

struct No *inserir_fim(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    if (lista == NULL) {
        return n;
    }
    struct No *p = lista;
    while (p->prox != NULL) {
        p = p->prox;
    }
    p->prox = n;
    return lista;
}

void imprimir(const struct No *lista) {
    for (const struct No *p = lista; p != NULL; p = p->prox) {
        printf("%d -> ", p->valor);
    }
    printf("NULL\n");
}

struct No *buscar(struct No *lista, int valor) {
    for (struct No *p = lista; p != NULL; p = p->prox) {
        if (p->valor == valor) {
            return p;
        }
    }
    return NULL;
}

struct No *remover(struct No *lista, int valor) {
    struct No *ant = NULL;
    struct No *p = lista;
    while (p != NULL && p->valor != valor) {
        ant = p;
        p = p->prox;
    }
    if (p == NULL) {
        return lista;
    }
    if (ant == NULL) {
        lista = p->prox;
    } else {
        ant->prox = p->prox;
    }
    free(p);
    return lista;
}

void liberar(struct No *lista) {
    while (lista != NULL) {
        struct No *prox = lista->prox;
        free(lista);
        lista = prox;
    }
}

int main(void) {
    struct No *lista = NULL;
    lista = inserir_fim(lista, 20);
    lista = inserir_fim(lista, 30);
    lista = inserir_inicio(lista, 10);
    lista = inserir_fim(lista, 40);
    imprimir(lista);

    struct No *achou = buscar(lista, 30);
    printf("buscar 30: %s\n", achou != NULL ? "achou" : "não achou");
    printf("buscar 99: %s\n", buscar(lista, 99) != NULL ? "achou" : "não achou");

    lista = remover(lista, 30);
    imprimir(lista);
    lista = remover(lista, 10);
    imprimir(lista);
    lista = remover(lista, 99);
    imprimir(lista);

    liberar(lista);
    lista = NULL;
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g lista.c -o lista
$ ./lista
10 -> 20 -> 30 -> 40 -> NULL
buscar 30: achou
buscar 99: não achou
10 -> 20 -> 40 -> NULL
20 -> 40 -> NULL
20 -> 40 -> NULL

Linha por linha da saída: os três inserir_fim e o inserir_inicio montaram 10 20 30 40; a busca achou o 30 e não achou o 99; remover(lista, 30) tirou um nó do meio; remover(lista, 10) tirou o primeiro (e a cabeça mudou para o 20); remover(lista, 99) não achou nada e devolveu a lista igual.

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

struct No {
    int valor;
    struct No *prox;
};

struct No *novo_no(int valor) {
    struct No *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "Sem memória\n");
        exit(1);
    }
    n->valor = valor;
    n->prox = NULL;
    return n;
}

struct No *inserir_inicio(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    n->prox = lista;
    return n;
}

struct No *inserir_fim(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    if (lista == NULL) {
        return n;
    }
    struct No *p = lista;
    while (p->prox != NULL) {
        p = p->prox;
    }
    p->prox = n;
    return lista;
}

void imprimir(const struct No *lista) {
    for (const struct No *p = lista; p != NULL; p = p->prox) {
        printf("%d -> ", p->valor);
    }
    printf("NULL\n");
}

struct No *buscar(struct No *lista, int valor) {
    for (struct No *p = lista; p != NULL; p = p->prox) {
        if (p->valor == valor) {
            return p;
        }
    }
    return NULL;
}

struct No *remover(struct No *lista, int valor) {
    struct No *ant = NULL;
    struct No *p = lista;
    while (p != NULL && p->valor != valor) {
        ant = p;
        p = p->prox;
    }
    if (p == NULL) {
        return lista;
    }
    if (ant == NULL) {
        lista = p->prox;
    } else {
        ant->prox = p->prox;
    }
    free(p);
    return lista;
}

void liberar(struct No *lista) {
    while (lista != NULL) {
        struct No *prox = lista->prox;
        free(lista);
        lista = prox;
    }
}

int main(void) {
    struct No *lista = NULL;
    lista = inserir_fim(lista, 20);
    lista = inserir_fim(lista, 30);
    lista = inserir_inicio(lista, 10);
    lista = inserir_fim(lista, 40);
    imprimir(lista);

    struct No *achou = buscar(lista, 30);
    printf("buscar 30: %s\n", achou != NULL ? "achou" : "não achou");
    printf("buscar 99: %s\n", buscar(lista, 99) != NULL ? "achou" : "não achou");

    lista = remover(lista, 30);
    imprimir(lista);
    lista = remover(lista, 10);
    imprimir(lista);
    lista = remover(lista, 99);
    imprimir(lista);

    liberar(lista);
    lista = NULL;
    return 0;
}

7. Liberar a lista inteira (e o valgrind)

Cada nó veio de um malloc, então cada nó precisa do seu free. Esquecer não dá erro nenhum na hora: o programa só vai segurando memória. É o vazamento de memória. O programa inicio.c lá de cima não liberava nada. O valgrind mostra:

$ gcc -std=c23 -Wall -Wextra -g inicio.c -o inicio
$ valgrind --leak-check=full ./inicio
==32493== Memcheck, a memory error detector
==32493== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
==32493== Using Valgrind-3.26.0 and LibVEX; rerun with -h for copyright info
==32493== Command: ./inicio
==32493==
NULL
30 -> NULL
20 -> 30 -> NULL
10 -> 20 -> 30 -> NULL
==32493==
==32493== HEAP SUMMARY:
==32493==     in use at exit: 48 bytes in 3 blocks
==32493==   total heap usage: 4 allocs, 1 frees, 4,144 bytes allocated
==32493==
==32493== 48 (16 direct, 32 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 3
==32493==    at 0x4850858: malloc (vg_replace_malloc.c:447)
==32493==    by 0x40011E1: novo_no (inicio.c:10)
==32493==    by 0x400124E: inserir_inicio (inicio.c:21)
==32493==    by 0x4001332: main (inicio.c:40)
==32493==
==32493== LEAK SUMMARY:
==32493==    definitely lost: 16 bytes in 1 blocks
==32493==    indirectly lost: 32 bytes in 2 blocks
==32493==      possibly lost: 0 bytes in 0 blocks
==32493==    still reachable: 0 bytes in 0 blocks
==32493==         suppressed: 0 bytes in 0 blocks
==32493==
==32493== For lists of detected and suppressed errors, rerun with: -s
==32493== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

• in use at exit: 48 bytes in 3 blocks: no fim, 3 blocos (os 3 nós) ainda estavam reservados. Cada nó tem 16 bytes no laboratório: 4 do int, 4 de "enchimento" para alinhar e 8 do ponteiro (veja sizeof).
• 4 allocs, 1 frees: os 3 nós e mais um bloco que o próprio printf reservou para a saída (e devolveu sozinho no fim).
• definitely lost: 16 bytes in 1 blocks: o nó 10, o primeiro. Ninguém mais aponta para ele: está "definitivamente perdido". A linha main (inicio.c:40) mostra onde ele nasceu.
• indirectly lost: 32 bytes in 2 blocks: o 20 e o 30. Só eram alcançáveis pelo nó 10; perdido o 10, eles se perderam "indiretamente".

Para liberar, ande pela lista e dê free em cada nó. O detalhe que importa: guarde o próximo antes de liberar o atual.

void liberar(struct No *lista) {
    while (lista != NULL) {
        struct No *prox = lista->prox;
        free(lista);
        lista = prox;
    }
}

Com o liberar no fim do main, o programa completo lista.c fica limpo:

$ valgrind --leak-check=full ./lista
==28184== Memcheck, a memory error detector
==28184== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
==28184== Using Valgrind-3.26.0 and LibVEX; rerun with -h for copyright info
==28184== Command: ./lista
==28184==
10 -> 20 -> 30 -> 40 -> NULL
buscar 30: achou
buscar 99: não achou
10 -> 20 -> 40 -> NULL
20 -> 40 -> NULL
20 -> 40 -> NULL
==28184==
==28184== HEAP SUMMARY:
==28184==     in use at exit: 0 bytes in 0 blocks
==28184==   total heap usage: 5 allocs, 5 frees, 4,160 bytes allocated
==28184==
==28184== All heap blocks were freed -- no leaks are possible
==28184==
==28184== For lists of detected and suppressed errors, rerun with: -s
==28184== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

All heap blocks were freed -- no leaks are possible = "todos os blocos foram liberados: não há vazamento possível". São 5 malloc (4 nós + o do printf) e 5 free (2 do remover, 2 do liberar, 1 do printf). ERROR SUMMARY: 0 errors: nenhum acesso errado à memória.

Formas diferentes

a) Com typedef e ponteiro para ponteiro

Muito código escreve No em vez de struct No com um typedef, e passa &lista para as funções mudarem a cabeça elas mesmas, com um ponteiro para ponteiro (No **). A função fica livre para devolver outra coisa, como um bool dizendo se o malloc deu certo:

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

typedef struct No {
    int valor;
    struct No *prox;
} No;

bool inserir_inicio(No **inicio, int valor) {
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        return false;
    }
    n->valor = valor;
    n->prox = *inicio;
    *inicio = n;
    return true;
}

void liberar(No **inicio) {
    No *p = *inicio;
    while (p != NULL) {
        No *prox = p->prox;
        free(p);
        p = prox;
    }
    *inicio = NULL;
}

int main(void) {
    No *lista = NULL;
    for (int v = 30; v >= 10; v -= 10) {
        if (!inserir_inicio(&lista, v)) {
            fprintf(stderr, "Sem memória\n");
            liberar(&lista);
            return 1;
        }
    }
    for (No *p = lista; p != NULL; p = p->prox) {
        printf("%d ", p->valor);
    }
    printf("\n");
    liberar(&lista);
    printf("Depois de liberar: %s\n", lista == NULL ? "NULL" : "ainda aponta");
    return 0;
}

$ gcc -std=c23 -Wall -Wextra duplo.c -o duplo
$ ./duplo
10 20 30
Depois de liberar: NULL

typedef struct No { … } No;

Cria o apelido No. Dentro das chaves, o apelido ainda não existe, por isso o campo continua struct No *prox;.

No **inicio

O endereço da variável lista do main. *inicio é a própria lista.

*inicio = n;

Muda a lista do main diretamente: ninguém precisa lembrar de guardar o retorno.

bool

No C23, bool, true e false são palavras da linguagem, sem #include C23. No C99 a C17, inclua <stdbool.h> (veja Booleanos).

b) Com ponteiro para o fim

Uma struct "dona da lista" guarda o primeiro nó, o último e o tamanho. Inserir no fim fica tão rápido quanto no início, porque não precisa andar até o último: ele já está guardado.

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

typedef struct No {
    int valor;
    struct No *prox;
} No;

typedef struct {
    No *inicio;
    No *fim;
    int tamanho;
} Lista;

bool inserir_fim(Lista *l, int valor) {
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        return false;
    }
    n->valor = valor;
    n->prox = NULL;
    if (l->fim == NULL) {
        l->inicio = n;
    } else {
        l->fim->prox = n;
    }
    l->fim = n;
    l->tamanho++;
    return true;
}

void liberar(Lista *l) {
    No *p = l->inicio;
    while (p != NULL) {
        No *prox = p->prox;
        free(p);
        p = prox;
    }
    l->inicio = l->fim = NULL;
    l->tamanho = 0;
}

int main(void) {
    Lista senhas = {NULL, NULL, 0};
    for (int s = 101; s <= 104; s++) {
        if (!inserir_fim(&senhas, s)) {
            fprintf(stderr, "Sem memória\n");
            liberar(&senhas);
            return 1;
        }
    }
    printf("%d senhas: ", senhas.tamanho);
    for (No *p = senhas.inicio; p != NULL; p = p->prox) {
        printf("%d ", p->valor);
    }
    printf("\nÚltima: %d\n", senhas.fim->valor);
    liberar(&senhas);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g fim_rapido.c -o fim_rapido
$ ./fim_rapido
4 senhas: 101 102 103 104
Última: 104
$ valgrind -q --leak-check=full ./fim_rapido
4 senhas: 101 102 103 104
Última: 104

O -q ("quiet", quieto) faz o valgrind falar só quando acha problema: como não apareceu nada além da saída do programa, não há vazamento nem erro. Esta versão é a base das filas da próxima aula.

Qual usar

Lista ligada ou array?

Na prática, o array que cresce ganha na maioria dos programas. A lista ligada brilha quando há muitas inserções e remoções no começo ou no meio, e é a base de outras estruturas: pilhas e filas, os "baldes" da tabela hash e, com dois ponteiros por nó, as árvores.

Quando dá errado

#include <stdio.h>

struct No {
    int valor;
    struct No *prox;
};

int ultimo(const struct No *lista) {
    const struct No *p = lista;
    while (p->prox != NULL) {
        p = p->prox;
    }
    return p->valor;
}

int main(void) {
    struct No *lista = NULL;
    printf("Último: %d\n", ultimo(lista));
    return 0;
}

$ gcc -std=c23 -Wall -Wextra vazia.c -o vazia
$ ./vazia
Falha de segmentação (imagem do núcleo gravada)
$ echo $?
139

void liberar(struct No *lista) {
    for (struct No *p = lista; p != NULL; p = p->prox) {
        free(p);
    }
}

$ gcc -std=c23 -Wall -Wextra -g uaf.c -o uaf
uaf.c: In function ‘liberar’:
uaf.c:18:45: warning: pointer ‘p’ used after ‘free’ [-Wuse-after-free]
   18 |     for (struct No *p = lista; p != NULL; p = p->prox) {
      |                                           ~~^~~~~~~~~
uaf.c:19:9: note: call to ‘free’ here
   19 |         free(p);
      |         ^~~~~~~
$ ./uaf; echo "código: $?"
free(): invalid pointer
código: 134

$ valgrind ./uaf
==29164== Memcheck, a memory error detector
==29164== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
==29164== Using Valgrind-3.26.0 and LibVEX; rerun with -h for copyright info
==29164== Command: ./uaf
==29164==
==29164== Invalid read of size 8
==29164==    at 0x4001200: liberar (uaf.c:18)
==29164==    by 0x4001265: main (uaf.c:28)
==29164==  Address 0x4aa60e8 is 8 bytes inside a block of size 16 free'd
==29164==    at 0x48538BF: free (vg_replace_malloc.c:990)
==29164==    by 0x40011FB: liberar (uaf.c:19)
==29164==    by 0x4001265: main (uaf.c:28)
==29164==  Block was alloc'd at
==29164==    at 0x4850858: malloc (vg_replace_malloc.c:447)
==29164==    by 0x40011A5: inserir_inicio (uaf.c:10)
==29164==    by 0x400124B: main (uaf.c:26)
==29164==
==29164==
==29164== HEAP SUMMARY:
==29164==     in use at exit: 0 bytes in 0 blocks
==29164==   total heap usage: 3 allocs, 3 frees, 48 bytes allocated
==29164==
==29164== All heap blocks were freed -- no leaks are possible
==29164==
==29164== For lists of detected and suppressed errors, rerun with: -s
==29164== ERROR SUMMARY: 3 errors from 1 contexts (suppressed: 0 from 0)

[[nodiscard]] struct No *inserir_inicio(struct No *lista, int valor) {

$ gcc -std=c23 -Wall -Wextra esqueceu.c -o esqueceu
esqueceu.c: In function ‘main’:
esqueceu.c:19:5: warning: ignoring return value of ‘inserir_inicio’, declared with attribute ‘nodiscard’ [-Wunused-result]
   19 |     inserir_inicio(lista, 10);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~
esqueceu.c:9:26: note: declared here
    9 | [[nodiscard]] struct No *inserir_inicio(struct No *lista, int valor) {
      |                          ^~~~~~~~~~~~~~
$ ./esqueceu
lista vazia

$ gcc -std=c23 -Wall -Wextra semtypedef.c -o semtypedef
semtypedef.c:3:5: error: unknown type name ‘No’
    3 |     No *prox;
      |     ^~

Referência rápida

Exercícios

Missão final: os pedidos da lojinha

Pedidos: 15 -> 40 -> 25 -> NULL
Total: 80

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

struct No {
    int valor;
    struct No *prox;
};

struct No *novo_no(int valor) {
    struct No *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "Sem memória\n");
        exit(1);
    }
    n->valor = valor;
    n->prox = NULL;
    return n;
}

// CONSERTE: hoje ela coloca o nó novo no INÍCIO
struct No *inserir_fim(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    n->prox = lista;
    return n;
}

// CONSERTE: hoje ela sempre devolve 0
int somar(const struct No *lista) {
    int soma = 0;
    (void)lista;
    return soma;
}

void imprimir(const struct No *lista) {
    printf("Pedidos: ");
    for (const struct No *p = lista; p != NULL; p = p->prox) {
        printf("%d -> ", p->valor);
    }
    printf("NULL\n");
}

void liberar(struct No *lista) {
    while (lista != NULL) {
        struct No *prox = lista->prox;
        free(lista);
        lista = prox;
    }
}

int main(void) {
    struct No *pedidos = NULL;
    pedidos = inserir_fim(pedidos, 15);
    pedidos = inserir_fim(pedidos, 40);
    pedidos = inserir_fim(pedidos, 25);
    imprimir(pedidos);
    printf("Total: %d\n", somar(pedidos));
    liberar(pedidos);
    return 0;
}

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

struct No {
    int valor;
    struct No *prox;
};

struct No *novo_no(int valor) {
    struct No *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "Sem memória\n");
        exit(1);
    }
    n->valor = valor;
    n->prox = NULL;
    return n;
}

struct No *inserir_fim(struct No *lista, int valor) {
    struct No *n = novo_no(valor);
    if (lista == NULL) {
        return n;
    }
    struct No *p = lista;
    while (p->prox != NULL) {
        p = p->prox;
    }
    p->prox = n;
    return lista;
}

int somar(const struct No *lista) {
    int soma = 0;
    for (const struct No *p = lista; p != NULL; p = p->prox) {
        soma += p->valor;
    }
    return soma;
}

void imprimir(const struct No *lista) {
    printf("Pedidos: ");
    for (const struct No *p = lista; p != NULL; p = p->prox) {
        printf("%d -> ", p->valor);
    }
    printf("NULL\n");
}

void liberar(struct No *lista) {
    while (lista != NULL) {
        struct No *prox = lista->prox;
        free(lista);
        lista = prox;
    }
}

int main(void) {
    struct No *pedidos = NULL;
    pedidos = inserir_fim(pedidos, 15);
    pedidos = inserir_fim(pedidos, 40);
    pedidos = inserir_fim(pedidos, 25);
    imprimir(pedidos);
    printf("Total: %d\n", somar(pedidos));
    liberar(pedidos);
    return 0;
}

No seu computador, compile a solução com -g e rode valgrind --leak-check=full ./pedidos: com o liberar no fim, a resposta tem de ser All heap blocks were freed -- no leaks are possible.

Resumo

• Uma lista ligada é uma corrente de nós. Cada nó é uma struct com o valor e o ponteiro struct No *prox para o próximo; o último aponta para NULL. A lista em si é só o ponteiro para o primeiro nó (NULL = vazia).
• Percorrer: for (p = lista; p != NULL; p = p->prox). Use um ponteiro auxiliar, nunca a cabeça.
• Inserir no início: n->prox = lista; lista = n;, nessa ordem. Instantâneo.
• Inserir no fim: ande até o nó cujo prox é NULL e ligue o novo nele. Trate a lista vazia. Com um ponteiro para o fim, fica instantâneo.
• Remover: ache o nó e o anterior, religue (ant->prox = p->prox, ou mude a cabeça se for o primeiro) e só então free(p).
• Liberar: guarde o prox antes de cada free. Todo malloc tem o seu free; confira com valgrind --leak-check=full.
• Lista ligada ganha em inserir e remover no começo e no meio; o array ganha em acessar por posição e em percorrer.