Vamos a mais uma variação da estrutura de dados lista simplesmente encadeada? Dando continuidade ao nosso Curso de Programação C, vamos aprender hoje como implementar uma LISTA CIRCULAR.

Outra estrutura de dados dinâmica clássica é a Lista Circular. Como o nome sugere ela é circular, ou seja, ao percorrer uma lista circular a partir do início, em algum momento iremos chegar novamente no início, pois o ponteiro próximo do último nó aponta para o início da lista.

Um risco a criar uma lista circular é entrar em loop infinito, uma repetição que nunca termina ao não identificar corretamente o fim da lista.

Para este exemplo faremos uso de duas estruturas, a estrutura nó que já conhecemos e a estrutura lista. Esta estrutura possuirá dois ponteiros, um para o início da lista, um para o fim da lista e um inteiro para o tamanho da lista.

/*
      Estrutura nó
*/
typedef struct no{
    int valor;
    struct no *proximo;
}No;

// estrutura lista
typedef struct{
    No *inicio;
    No *fim;
    int tam;
}Lista;

A principal complexidade da lista circular está no fato de que, em qualquer operação na lista, precisamos manipular vários ponteiros, mantendo sempre o último nó apontando para o primeiro nó. No trecho de código a seguir apresentamos um procedimento para inserir no início da lista. Observe que ao inserir no início, o primeiro nó da lista é alterado fazendo com que o ponteiro próximo do último nó também precise ser alterado, uma vez que ele aponta para o primeiro nó da lista.

/*
        procedimento para inserir no início
*/
void inserir_no_inicio(Lista *lista, int num){
    No *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        // o próximo aponta para o início da lista
        novo->proximo = lista->inicio;
        // novo se torna o início da lista
        lista->inicio = novo;
        // se fim for nulo (lista vazia), fim aponta para novo nó
        if(lista->fim == NULL)
            lista->fim = novo;
        // fim aponta para início
        lista->fim->proximo = lista->inicio;
        lista->tam++;
    }
    else
        printf("Erro ao alocar memoria!\n");
}

Uma dica para ajudar na compreensão de cada uma destas operações é desenhar uma lista no papel e simular as operações. Por exemplo, se for inserir de forma ordenada, desenhe uma lista com alguns elementos e um novo nó a ser inserido de forma ordenada. Agora rastreie o procedimento de inserção ordenada, fazendo no papel o que cada linha de código faz. Isso ajuda a entender a manipulação dos ponteiros.

Observe que todos estes conceitos que estamos aprendendo podem se juntar para formar uma estrutura mais complexa. Se o problema que estamos resolvendo com programação exigir nós podemos ter por exemplo uma lista duplamente encadeada circular em que cada nó possui dois ponteiros e o fim sempre aponta para o início da lista.

Código de exemplo completo em C para uma Lista Circular

/*
            Aula 258: Lista Circular

            Código escrito por Wagner Gaspar
            Agosto de 2021
*/

typedef struct no{
    int valor;
    struct no *proximo;
}No;

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

void criar_lista(Lista *lista){
    lista->inicio = NULL;
    lista->fim = NULL;
    lista->tam = 0;
}

// procedimento para inserir no início
void inserir_no_inicio(Lista *lista, int num){
    No *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        novo->proximo = lista->inicio;
        lista->inicio = novo;
        if(lista->fim == NULL)
            lista->fim = novo;
        lista->fim->proximo = lista->inicio;
        lista->tam++;
    }
    else
        printf("Erro ao alocar memoria!\n");
}

// procedimento para inserir no fim
void inserir_no_fim(Lista *lista, int num){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;

        // é o primeiro?
        if(lista->inicio == NULL){
            lista->inicio = novo;
            lista->fim = novo;
            lista->fim->proximo = lista->inicio;
        }
        else{
            lista->fim->proximo = novo;
            lista->fim = novo;
            // as duas linhas a seguir são sinônimas. Escolha a que achar mais fácil compreender
            //lista->fim->proximo = lista->inicio;
            novo->proximo = lista->inicio;
        }
        lista->tam++;
    }
    else
        printf("Erro ao alocar memoria!\n");
}

// procedimento para inserir ordenado
void inserir_ordenado(Lista *lista, int num){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        if(lista->inicio == NULL){
            inserir_no_inicio(lista, num);
        }
        else if(novo->valor < lista->inicio->valor){
            inserir_no_inicio(lista, num);
        }
        else{
            aux = lista->inicio;
            while(aux->proximo != lista->inicio && novo->valor > aux->proximo->valor)
                aux = aux->proximo;
            if(aux->proximo == lista->inicio)
                inserir_no_fim(lista, num);
            else{
                novo->proximo = aux->proximo;
                aux->proximo = novo;
                lista->tam++;
            }
        }
    }
    else
        printf("Erro ao alocar memoria!\n");
}

// função para remover um nó
No* remover(Lista *lista, int num){
    No *aux, *remover = NULL;

    if(lista->inicio){
        if(lista->inicio == lista->fim && lista->inicio->valor == num){
            remover = lista->inicio;
            lista->inicio = NULL;
            lista->fim = NULL;
            lista->tam--;
        }
        else if(lista->inicio->valor == num){
            remover = lista->inicio;
            lista->inicio = remover->proximo;
            lista->fim->proximo = lista->inicio;
            lista->tam--;
        }
        else{
            aux = lista->inicio;
            while(aux->proximo != lista->inicio && aux->proximo->valor != num)
                aux = aux->proximo;
            if(aux->proximo->valor == num){
                if(lista->fim == aux->proximo){
                    remover = aux->proximo;
                    aux->proximo = remover->proximo;
                    lista->fim = aux;
                }
                else{
                    remover = aux->proximo;
                    aux->proximo = remover->proximo;
                }
                lista->tam--;
            }
        }
    }

    return remover;
}

// função para buscar um valor
No* buscar(Lista *lista, int num){
    No *aux = lista->inicio;

    if(aux){
        do{
            if(aux->valor == num)
                return aux;
            aux = aux->proximo;
        }while(aux != lista->inicio);
    }
    return NULL;
}

// procedimento para imprimir a lista circular
void imprimir(Lista lista){
    No *no = lista.inicio;
    printf("\n\tLista tam %d: ", lista.tam);
    if(no){
        do{
            printf("%d ", no->valor);
            no = no->proximo;
        }while(no != lista.inicio);
        printf("\nInicio: %d\n", no->valor);
    }
    printf("\n\n");
}

int main(){

    int opcao, valor, anterior;
    //No *lista = NULL;
    Lista lista;
    No *removido;

    criar_lista(&lista);

    do{
        printf("\n\t0 - Sair\n\t1 - InserirI\n\t2 - inserirF\n\t3 - InserirO\n\t4 - Remover\n\t5 - Imprimir\n\t6 - Buscar\n");
        scanf("%d", &opcao);

        switch(opcao){
        case 1:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_no_inicio(&lista, valor);
            break;
        case 2:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_no_fim(&lista, valor);
            break;
        case 3:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_ordenado(&lista, valor);
            break;
        case 4:
            printf("Digite um valor a ser removido: ");
            scanf("%d", &valor);
            removido = remover(&lista, valor);
            if(removido){
                printf("Elemento removido: %d\n", removido->valor);
                free(removido);
            }
            else
                printf("elemento inesistente!\n");
            break;
        case 5:
            imprimir(lista);
            break;
        case 6:
            printf("Digite um valor a ser buscado: ");
            scanf("%d", &valor);
            removido = buscar(&lista, valor);
            if(removido)
                printf("Valor encontrado: %d\n", removido->valor);
            else
                printf("Valor nao encontrado!\n");
            break;
        default:
            if(opcao != 0)
                printf("Opcao invalida!\n");
        }

    }while(opcao != 0);

    return 0;
}