Nesta aula estudamos a segunda forma de implementar o TAD Lista: o encadeamento. Veremos como abandonar o vetor de capacidade fixa da Aula 2c e passar a montar a lista "nó a nó", usando alocação dinâmica e ponteiros.

1. Revisão

Relembrando o que já vimos sobre listas:

• Uma lista é linear, sequencial, e possui uma relação de ordem entre seus elementos;
• É uma sequência de zero ou mais nodos do mesmo tipo (int, float, struct X, etc.).

( A ) ---> ( B ) ---> ( C )

Também vimos que existem duas formas de implementar essa especificação:

• Contiguidade física (Aula 2c): a adjacência lógica entre elementos equivale à adjacência física na memória — implementada com um vetor de capacidade máxima, e uma struct ListaContEst guardando o vetor mais um contador tamanho;
• Encadeamento (esta aula): cada elemento aponta explicitamente para o próximo.

2. Listas (simplesmente) encadeadas

Em uma lista simplesmente encadeada, cada elemento (nodo) contém:

• Os dados propriamente ditos;
• Um ponteiro para o próximo elemento da lista.

O ponteiro NULL marca o final da lista, e a lista guarda um ponteiro para o seu primeiro nodo:

lista.ini
  |
  v
+-------+-------+     +-------+-------+     +-------+-------+
| Dados | Ptr.  | --> | Dados | Ptr.  | --> | Dados | Ptr.  | --> NULL
|       | prox. |     |       | prox. |     |       | prox. |
+-------+-------+     +-------+-------+     +-------+-------+

Algumas características importantes dessa implementação:

• O número de elementos aumenta e diminui dinamicamente (alocação dinâmica) — o único limite é a capacidade da memória disponível;
• Os elementos não estão em posições contíguas da memória — diferente do que vimos na Aula 2c;
• Isso permite um melhor aproveitamento do espaço livre na memória;
• Usar lista[elemento], como fazíamos com o vetor, não funciona — não existe mais acesso direto por índice;
• Cuidado: se perdermos a referência a um ponteiro da lista, não é mais possível recuperá-lo — o espaço alocado para aquele nó fica inacessível (um vazamento de memória).

Exemplo: partindo de uma lista vazia, após inserirInicio(10), inserirInicio(8) e inserirInicio(19), a lista fica assim:

lista.ini
  |
  v
+----+-------+     +---+-------+     +----+-------+
| 19 | Ptr.  | --> | 8 | Ptr.  | --> | 10 | Ptr.  | --> NULL
|    | prox. |     |   | prox. |     |    | prox. |
+----+-------+     +---+-------+     +----+-------+

Note que cada novo elemento inserido no início "empurra" a lista anterior para trás — os elementos aparecem na ordem inversa à da inserção.

3. TAD Lista Simplesmente Encadeada (LSE)

Dados

Assim como na Aula 2c, definimos primeiro o dado a ser armazenado em cada nodo:

typedef struct {
    int cod;
    char nome[50];
    float preco;
} Produto;

Agora o nodo da lista, que guarda um Produto e um ponteiro para o próximo nodo. Como o nodo referencia a si mesmo (através de prox), é preciso declarar o tipo em duas etapas:

typedef struct str_Nodo Nodo;

struct str_Nodo {
    Nodo *prox;
    Produto dado;
};

E, por fim, o tipo da lista propriamente dita — assim como fizemos com ListaContEst na Aula 2c, encapsulamos o ponteiro para o primeiro nodo (ini) dentro de uma struct:

typedef struct {
    Nodo *ini;
} ListaEnc;

Note o paralelo com a Aula 2c: lá, ListaContEst guardava um vetor mais um contador de controle (tamanho); aqui, ListaEnc guarda apenas um ponteiro para o primeiro nodo (ini) — os dados em si não ficam "dentro" da struct da lista, e sim espalhados entre os nodos alocados dinamicamente.

Operações

Como agora sempre trabalhamos com um ponteiro para a struct da lista (ListaEnc *lista), as funções podem alterar lista->ini diretamente através dele — sem precisar retornar a lista, como seria necessário se ela fosse apenas um Nodo * solto (mais sobre isso ao final da aula). O tamanho da lista não é guardado na struct: existe uma função tamanho própria para calculá-lo quando necessário. Assim como na Aula 2c, as funções que apenas leem a lista (imprimir, buscar e tamanho) recebem const ListaEnc *lista, deixando explícito que não alteram a lista recebida.

void    inicializar(ListaEnc *lista);
void    imprimir(const ListaEnc *lista);
Produto buscar(const ListaEnc *lista, int cod);
int     inserirInicio(ListaEnc *lista, Produto prod);
int     inserirFim(ListaEnc *lista, Produto prod);
int     removerPorCod(ListaEnc *lista, int cod);
void    destruir(ListaEnc *lista);
int     tamanho(const ListaEnc *lista);

4. Implementação em C

inicializar

void inicializar(ListaEnc *lista) {
    lista->ini = NULL;
}

tamanho

Como a struct não guarda mais um contador, calculamos o tamanho percorrendo a lista e contando os nodos:

int tamanho(const ListaEnc *lista) {
    Nodo *aux = lista->ini;
    int contador = 0;

    while (aux != NULL) {
        contador++;
        aux = aux->prox;
    }

    return contador;
}

imprimir

Para percorrer a lista, usamos um ponteiro auxiliar (aux), avançando-o até chegar a NULL:

void imprimir(const ListaEnc *lista) {
    Nodo *aux;
    aux = lista->ini;

    while (aux != NULL) {
        printf("Codigo: %d\n", aux->dado.cod);
        printf("Nome: %s\n", aux->dado.nome);
        printf("Preco: %f\n", aux->dado.preco);
        aux = aux->prox;
    }
}

buscar

Produto buscar(const ListaEnc *lista, int cod) {
    Nodo *aux;
    Produto prod = {0, "", 0.0f};
    aux = lista->ini;

    while (aux != NULL) {
        if (aux->dado.cod == cod)
            return aux->dado;
        aux = aux->prox;
    }

    return prod; // não encontrado: produto "vazio"
}

inserirInicio

Inserir no início não exige percorrer a lista: basta criar um novo nodo e "encaixá-lo" antes do primeiro nodo atual. Como recebemos um ponteiro para a struct da lista, podemos atualizar lista->ini diretamente:

int inserirInicio(ListaEnc *lista, Produto prod) {
    Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
    if (novo == NULL)
        return 0; // falha na alocação

    novo->dado = prod;
    novo->prox = lista->ini; // o novo nodo aponta para o antigo início
    lista->ini = novo;        // o novo nodo passa a ser o início

    return 1;
}

Na main, basta passar o endereço da lista — não é preciso reatribuir nenhum retorno, pois a própria struct apontada por lista já foi alterada:

inserirInicio(&lista, p1);

inserirFim

Inserir no final exige percorrer a lista inteira até encontrar o último nodo (aquele cujo prox é NULL):

int inserirFim(ListaEnc *lista, Produto prod) {
    Nodo *novo;
    Nodo *aux;

    novo = (Nodo*) malloc(sizeof(Nodo));
    if (novo == NULL)
        return 0;

    novo->dado = prod;
    novo->prox = NULL;

    if (lista->ini == NULL) { // lista vazia: o novo nodo é o único (e o início)
        lista->ini = novo;
    } else {
        aux = lista->ini;
        while (aux->prox != NULL) // percorre até o último nodo
            aux = aux->prox;
        aux->prox = novo;
    }

    return 1;
}

removerPorCod

Remover exige guardar, além do nodo procurado (aux), o nodo anterior a ele (ant) — é através dele que "religamos" a lista após retirar o nodo removido:

int removerPorCod(ListaEnc *lista, int cod) {
    Nodo *ant;
    Nodo *aux;

    ant = NULL;
    aux = lista->ini;

    while (aux != NULL && aux->dado.cod != cod) {
        ant = aux;
        aux = aux->prox;
    }

    if (aux == NULL) // não encontrado
        return 0;

    if (ant == NULL) // removendo o primeiro nodo
        lista->ini = aux->prox;
    else             // removendo do meio ou do final
        ant->prox = aux->prox;

    free(aux);
    return 1;
}

destruir

Diferente da Aula 2c, aqui existe memória de fato alocada para cada nodo: é preciso percorrer a lista inteira, liberando um nodo de cada vez:

void destruir(ListaEnc *lista) {
    Nodo *ant;
    Nodo *aux;
    aux = lista->ini;

    while (aux != NULL) {
        ant = aux;
        aux = aux->prox;
        free(ant);
    }

    lista->ini = NULL;
}

5. Exemplo de uso

int main() {
    ListaEnc lista;
    inicializar(&lista);

    Produto p1 = {1, "Produto A", 10.0f};
    Produto p2 = {2, "Produto B", 20.0f};

    inserirInicio(&lista, p1); // lista: [A]
    inserirFim(&lista, p2);    // lista: [A, B]

    imprimir(&lista);
    printf("Tamanho: %d\n", tamanho(&lista)); // imprime 2

    buscar(&lista, 1);

    removerPorCod(&lista, 1);  // lista: [B]
    destruir(&lista);          // lista: vazia, memória liberada

    return 0;
}

6. Contiguidade física versus encadeamento

Com as duas implementações já vistas (Aula 2c e esta aula), podemos comparar diretamente suas vantagens e desvantagens:

7. Complexidade das operações (LSE)

Resumo

Observação: outras formas de representar a lista

Nem todo material sobre listas encadeadas usa uma struct como ListaEnc. É comum encontrar textos e exemplos em que a lista é, ela mesma, apenas o ponteiro para o primeiro nodo — ou seja, uma variável do tipo Nodo * diretamente, sem nenhum "envelope" ao redor.

Nesse caso, como não existe uma struct intermediária para guardar lista->ini, as funções que alteram o início da lista (como inserirInicio e removerPorCod) precisam de outra forma de "avisar" o chamador sobre o novo início. Existem duas soluções comuns:

Por exemplo, a versão de inserirInicio com retorno ficaria assim:

Nodo* inserirInicio(Nodo *lista, Produto prod) {
    Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
    if (novo == NULL)
        return lista; // falha na alocação: mantém a lista como estava

    novo->dado = prod;
    novo->prox = lista;
    return novo; // o novo nodo passa a ser o início
}

// Na main:
Nodo *lista = NULL;
lista = inserirInicio(lista, p1);

E a versão com ponteiro para ponteiro, evitando o retorno:

int inserirInicio(Nodo **lista, Produto prod) {
    Nodo *novo = malloc(sizeof(Nodo));
    if (novo == NULL)
        return -1;

    novo->dado = prod;
    novo->prox = *lista;
    *lista = novo;

    return 0;
}

// Na main:
Nodo *lista = NULL;
inserirInicio(&lista, p1);

Note que a abordagem usada nesta aula (ListaEnc *lista, com lista->ini dentro de uma struct) já resolve naturalmente esse problema: como sempre passamos o endereço da struct da lista, as funções podem alterar lista->ini livremente, do mesmo jeito que o "ponteiro para ponteiro" faria — sem precisar escolher entre retornar a lista ou usar Nodo **. Por isso seguiremos com ListaEnc pelo restante da disciplina, mas é importante reconhecer as outras formas, caso você as encontre em outros materiais.

Exercícios

1. Por que, em uma lista simplesmente encadeada, a expressão lista.ini[2] não funciona, ao contrário do que acontecia com l->dados[pos] na implementação por contiguidade física da Aula 2c?
2. Explique por que, ao percorrer uma lista encadeada, usamos um ponteiro auxiliar (como aux) em vez de andar diretamente com lista->ini.
3. Explique por que, nesta implementação com ListaEnc *lista, as funções não precisam mais retornar Nodo * nem usar Nodo ** para atualizar o início da lista — qual campo da struct cumpre esse papel?
4. Na função destruir, por que é necessário guardar aux->prox em ant antes de chamar free(ant)? O que aconteceria se a ordem das instruções dentro do laço fosse trocada?
5. Compare a complexidade de inserirInicio com a de inserirFim. Por que elas são diferentes, se ambas realizam basicamente "uma inserção"?
6. Por que a função tamanho desta aula é O(n), e não O(1) como era na Aula 2c (onde ListaContEst guardava um campo tamanho que permitia obter o tamanho diretamente)? O que a struct ListaEnc precisaria guardar para tornar essa função O(1), e qual seria o "preço" de fazer isso?
7. Considerando a tabela da seção 6, em qual cenário a lista por contiguidade física (Aula 2c) seria preferível a uma lista encadeada? E em qual cenário o encadeamento seria preferível?
8. Implemente uma função int soma(const ListaEnc *lista) que retorne a soma dos preços (arredondados para inteiro, apenas para simplificar) de todos os produtos da lista.
9. Implemente uma função float precoMedio(const ListaEnc *lista) que retorne o preço médio dos produtos da lista, reaproveitando as funções soma (exercício anterior) e tamanho já implementadas nesta aula. Cuidado com o caso da lista vazia.
10. Implemente uma função int contarAcimaDe(const ListaEnc *lista, float valor) que retorne quantos produtos da lista têm preço estritamente maior que valor.
11. Escreva um pequeno main() que crie uma ListaEnc, insira (com inserirFim) três produtos com preços 10.0, 25.0 e 40.0, e então imprima: o preço médio (precoMedio) e quantos produtos custam mais que 20.0 (contarAcimaDe).

Sugestões de Respostas dos Exercícios

int soma(const ListaEnc *lista) {
    Nodo *aux = lista->ini;
    int total = 0;

    while (aux != NULL) {
        total += (int) aux->dado.preco;
        aux = aux->prox;
    }

    return total;
}

float precoMedio(const ListaEnc *lista) {
    if (tamanho(lista) == 0) {
        return 0; // evita divisão por zero
    }

    return (float) soma(lista) / tamanho(lista);
}

int contarAcimaDe(const ListaEnc *lista, float valor) {
    Nodo *aux = lista->ini;
    int contador = 0;

    while (aux != NULL) {
        if (aux->dado.preco > valor) {
            contador++;
        }
        aux = aux->prox;
    }

    return contador;
}

int main() {
    ListaEnc lista;
    inicializar(&lista);

    Produto p1 = {1, "Produto A", 10.0f};
    Produto p2 = {2, "Produto B", 25.0f};
    Produto p3 = {3, "Produto C", 40.0f};

    inserirFim(&lista, p1);
    inserirFim(&lista, p2);
    inserirFim(&lista, p3);

    printf("Preco medio: %.2f\n", precoMedio(&lista));         // 25.00
    printf("Acima de 20: %d\n", contarAcimaDe(&lista, 20.0f)); // 2

    destruir(&lista);
    return 0;
}

Código para Download

O TAD ListaEnc completo, exatamente como visto nesta aula, dividido em interface (listaEnc.h) e implementação (listaEnc.c), junto com um main.c de exemplo: