Nesta aula vemos uma segunda variação sobre as listas encadeadas: a lista circular, em que o último nodo, em vez de apontar para NULL, aponta de volta para o primeiro — fechando a lista em um "círculo".

1. A ideia central

Em uma lista circular (a partir da simplesmente encadeada da Aula 4), o último nodo aponta para o primeiro em vez de para NULL:

l.ini
  |
  v
+-------+     +-------+     +-------+
| Dados | --> | Dados | --> | Dados | --+
+-------+     +-------+     +-------+   |
    ^                                    |
    +------------------------------------+

Não existe mais um nodo cujo prox seja NULL — todos os nodos apontam para algum outro nodo da lista, inclusive o último, que aponta de volta para o início. Isso muda a forma como percorremos a lista: não podemos mais usar aux != NULL como condição de parada, pois esse caso nunca ocorre.

2. Percorrendo uma lista circular

A forma usual de percorrer uma lista circular é comparar o ponteiro auxiliar com o próprio início da lista, parando quando voltarmos a ele. Como a comparação só faz sentido depois de avançar pelo menos uma vez, usamos um do-while em vez de um while:

void imprime(ListaCirc *l) {
    Nodo *aux;

    if (l->ini == NULL) // lista vazia: nada a imprimir
        return;

    aux = l->ini;
    do {
        printf("%d - %s - %.2f\n", aux->dado.cod, aux->dado.nome, aux->dado.preco);
        aux = aux->prox;
    } while (aux != l->ini);
}

Note o teste explícito de lista vazia antes do do-while: como o corpo de um do-while sempre executa pelo menos uma vez, seria necessário garantir que l->ini não é NULL antes de acessar aux->dado.

3. Inserção em uma lista circular

A principal diferença em relação à Aula 4 é que, ao inserir um novo nodo, o último nodo da lista (e não NULL) precisa apontar para o novo início — ou, de forma equivalente, o novo nodo precisa apontar de volta para o início da lista:

int insereInicio(ListaCirc *l, Produto prod) {
    Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
    Nodo *ultimo;

    if (novo == NULL)
        return 0;

    novo->dado = prod;

    if (l->ini == NULL) { // lista vazia: o novo nodo aponta para si mesmo
        novo->prox = novo;
    } else {
        ultimo = l->ini;
        while (ultimo->prox != l->ini) // percorre até achar quem aponta para o início
            ultimo = ultimo->prox;

        novo->prox = l->ini;
        ultimo->prox = novo;
    }

    l->ini = novo;
    return 1;
}

4. Aplicações

Listas circulares são úteis sempre que o conceito de "início" e "fim" não faz muito sentido, e o que importa é poder percorrer indefinidamente os elementos, voltando ao começo depois do último:

• Escalonamento round-robin: um sistema operacional distribuindo tempo de processador entre processos, sempre voltando ao primeiro processo da fila após passar pelo último;
• Buffers circulares: estruturas que reaproveitam posições já utilizadas, comuns em sistemas de streaming e comunicação;
• Jogos por turno: alternar entre jogadores de forma cíclica (jogador 1, 2, 3, ..., voltando ao jogador 1).

Resumo

Exercícios

1. Por que a condição while (aux != NULL), usada para percorrer listas na Aula 4, nunca é verdadeira em uma lista circular?
2. Por que a função imprime desta aula verifica l->ini == NULL antes do do-while, em vez de deixar essa verificação apenas na condição de parada do laço?
3. Cite um cenário (diferente dos vistos em aula) em que uma lista circular seria uma escolha natural, e explique por quê.
4. Implemente uma função int tamanho(ListaCirc *l) que retorne o número de nodos de uma lista circular, tomando cuidado para não entrar em laço infinito.

Sugestões de Respostas dos Exercícios

int tamanho(ListaCirc *l) {
    Nodo *aux;
    int contador = 0;

    if (l->ini == NULL)
        return 0;

    aux = l->ini;
    do {
        contador++;
        aux = aux->prox;
    } while (aux != l->ini);

    return contador;
}