Listas circulares

Listas em que o último nó aponta de volta para o primeiro. Representação pelo último nó, percurso com do-while e aplicações em rodízio.

Algumas aplicações lidam com sequências cíclicas, em que depois do último elemento vem de novo o primeiro:

o escalonamento circular (round-robin) de um sistema operacional, em que cada processo recebe um pouco de tempo de processador, em rodízio;
os vértices de um polígono, em que o último lado liga o último vértice ao primeiro;
a vez dos jogadores em um jogo de tabuleiro.

Para esses casos, existem as listas circulares: o último nó, em vez de apontar para NULL, aponta de volta para o primeiro.

Acima, quatro nós 1, 2, 3 e 5 encadeados, com o último apontando de volta para o primeiro e o ponteiro ultimo apontando para o nó 5. Abaixo, três nós duplamente encadeados, em que o próximo do último é o primeiro e o anterior do primeiro é o último — Lista circular simplesmente encadeada (acima) e duplamente encadeada (abaixo).

Nenhum nó tem proximo igual a NULL. A rigor, nem existe "primeiro" ou "último": a lista é um ciclo, e qualquer nó pode servir de ponto de partida. Uma lista circular também pode ser duplamente encadeada: o próximo do último é o primeiro, e o anterior do primeiro é o último. Assim, ela pode ser percorrida nos dois sentidos, a partir de qualquer nó.

Guardando o último nó

Para representar a lista, basta um ponteiro para um nó qualquer do ciclo. Uma escolha esperta é guardar o último nó:

typedef struct lista {
    No *ultimo;      /* o primeiro é ultimo->proximo; NULL se vazia */
    int tamanho;
} Lista;

Com o último, o primeiro está a um passo (ultimo->proximo). Por isso, inserir no início e no fim são as duas , com um único ponteiro na struct:

no início: o novo nó entra entre o último e o primeiro;
no fim: o novo nó entra no mesmo lugar, e o ultimo avança para ele.

Em uma lista vazia, o primeiro nó inserido forma um ciclo sozinho: ele é o próprio próximo.

void insereInicioLista(Lista *lista, int valor) {
    No *novo = malloc(sizeof(No));
    novo->dado = valor;
    if (lista->ultimo == NULL) {         /* lista vazia: o nó aponta para si mesmo */
        novo->proximo = novo;
        lista->ultimo = novo;
    } else {
        novo->proximo = lista->ultimo->proximo;   /* o antigo primeiro */
        lista->ultimo->proximo = novo;
    }
    lista->tamanho++;
}

/* Inserir no fim = inserir no início e "andar" o último uma posição */
void insereFimLista(Lista *lista, int valor) {
    insereInicioLista(lista, valor);
    lista->ultimo = lista->ultimo->proximo;
}

Percorrendo

Como não existe NULL no fim, a condição de parada muda: em vez de "até chegar a NULL", é "até voltar ao nó de partida". Mas o percurso começa justamente no nó de partida, e um while (p != inicio) pararia antes de começar. A solução é o do ... while, que executa o corpo uma vez antes de testar:

No *inicio = lista->ultimo->proximo;
No *p = inicio;
do {
    printf("%d -> ", p->dado);
    p = p->proximo;
} while (p != inicio);

A lista vazia (ultimo == NULL) precisa ser tratada antes, porque não há nó de partida.

Para liberar a lista, o mais simples é quebrar o ciclo (ultimo->proximo = NULL) e liberar como em uma lista comum, até chegar a NULL.

lista_circular.cC

No fim do programa, o ponteiro p dá dez passos e passa pelos quatro nós várias vezes: é o rodízio de um escalonador, em que cada processo é atendido na sua vez e volta para o fim da fila.

Por que guardar o último, e não o primeiro nó?

Com o primeiro, inserir no início seria , mas o novo nó também precisa ser apontado pelo último (para fechar o ciclo), e achar o último exige dar a volta inteira, em . O mesmo vale para inserir no fim. Guardando o último, os dois extremos estão sempre a no máximo um passo. A outra saída seria guardar os dois ponteiros, como na lista com inicio e fim.

Como seria a lista circular duplamente encadeada?

Cada nó tem proximo e anterior, e as duas pontas se ligam: primeiro->anterior == ultimo e ultimo->proximo == primeiro. Nessa lista, basta guardar um ponteiro para qualquer nó (o primeiro, por exemplo): o último é primeiro->anterior, a um passo. As operações seguem as da lista duplamente encadeada, sem os casos de NULL nas pontas, exceto o da lista vazia e o do nó único, que aponta para si mesmo nos dois sentidos.

Exercícios

Encontre e corrija o erro

Programa 1

Deveria contar quantos nós a lista tem.

conta.cC

Resposta

contaNos percorre a lista esperando chegar a NULL, como em uma lista comum. Em uma lista circular, isso nunca acontece: o laço dá voltas sem fim (até o tempo limite, ou até o contador estourar). A condição de parada é voltar ao nó de partida:

No *inicio = lista->ultimo->proximo;
No *p = inicio;
do {
    total++;
    p = p->proximo;
} while (p != inicio);

Programa 2

insere.cC

Resposta

Ao inserir na lista vazia, o novo nó vira o ultimo, mas o seu proximo não é inicializado. Em uma lista circular com um nó, ele é o próprio próximo: falta novo->proximo = novo;. Sem isso, logo na primeira chamada, insereFimLista faz ultimo avançar para esse campo com lixo, e a inserção seguinte acessa um endereço inválido. (O 0xbebebebebebebebe da mensagem é o padrão que o AddressSanitizer escreve na memória recém-alocada.)

Implemente

Rotacionar a lista. Na lista circular representada pelo último nó, "quem é o primeiro" depende só de para onde aponta ultimo. Rotacione a lista posições, para qualquer lado. Os testes usam da ordem de .

Rotacionar a lista circularC

Problema de Josefo. pessoas estão em círculo, e a cada rodada a -ésima pessoa, contando a partir de onde parou, sai do círculo. Use uma lista circular para simular as eliminações e descobrir quem sobra. Por exemplo, com e , saem as pessoas 2, 4, 1 e 5, e sobra a 3.

Problema de JosefoC

Referências

W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.
Josephus problem. Wikipedia.

Nesta página