A lista circular, assim como as demais, é composta por elementos que possuem um apontador seguinte (*prox). Porém, esta tem a peculiaridade de que o seu último elemento, ao invés de apontar para NULL, apontará para o primeiro elemento da lista, ou seja, fazendo-a ser um looping sem fim. De resto, a lista se faz extremamente semelhante a uma lista simplesmente encadeada, com funções de inserção, remoção e etc.
Portanto, seguem abaixo os procedimentos a serem seguidos para a sua criação:
De maneira já conhecida, a struct de criação do elemento é bem simples, bastando apenas passar um valor e o seu apontador *prox:
struct elemento{
int num;
struct elemento *prox;
}
Posteriormente, é necessário passar esta struct como typedef para torna-la um tipo de variável: typedef struct elemento Elem.
Exatamente como a lista simplesmente encadeada, onde basta retornar o valor NULL para a lista:
Elem *criar(void){
return NULL;
}
A verificação de lista vazia servirá nas demais funções que virão a seguir, sendo esta uma verificação muito importante, mas ao mesmo tempo, muito simples de se implementar, bastanto retornar a lista como NULL:
int listaVazia(Elem *lista){
return (lista == NULL);
}
A inserção de elemento no inicio que deve haver verificações de lista vazia e caso não esteja, realocação do old, assim como visto nas demais listas
int inserirInicioCircular(Elem **lista, int valor){
Elem *novo;
novo = (Elem *)malloc(sizeof(Elem));
novo->num = valor;
//Caso 1, lista vazia
if(listaVazia(*lista)){
novo->prox = novo;
(*lista) = novo;
}else{
//Caso 2, lista não vazia - Inserir no inicio
Elem *aux;
aux = *lista;
while(aux->prox != *lista){
aux = aux->prox;
}
aux->prox = novo;
novo->prox = *lista;
(*lista) = novo;
}
return novo;
}
Aqqui onde está a grande peculiaridade da lista circular, pois o elemento que inserido no final, deverá possuir um apontador para o primeiro elemento. Mas de resto, sua implementação é bem simples e identica a das demais listas. Além do fato de que caso a lista esteja vazia, ocorrerá uma inserção no inicio da lista:
int inserirFimCircular(Elem **lista, int valor){
Elem *novo;
novo = (Elem *)malloc(sizeof(Elem));
novo->num = valor;
//Caso 1, lista vazia
if(listaVazia(*lista)){
novo->prox = novo;
(*lista) = novo;
}else{
//Caso 2, lista não vazia - Inserir no final
Elem *aux;
aux = *lista;
while(aux->prox != *lista){
aux = aux->prox;
}
aux->prox = novo;
novo->prox = *lista;
}
return 1;
}
A remoção de elemento não possui aspecto de diferença alguma. Bastanto remover o elemento e fazer com que o seu *prox assuma o seu lugar.Além da verificação de lista vazia, de forma a não remover o que não existe.
int removerInicioCircular(Elem **lista){
//Caso 1, lista vazia
if(listaVazia(*lista)){
printf("\n LISTA VAZIA \n");
return 0;
}else{
Elem *aux;
aux = *lista;
//Caso 2, lista contém 1 elemento
if(aux->prox == *lista){
free(aux);
*lista = NULL;
}else{
//Caso 3, lista contém +1 elemento
aux = aux->prox;
while(aux->prox != *lista){
aux = aux->prox;
}
aux->prox = (*lista)->prox;
free(*lista);
*lista = aux->prox;
}
}
}
A remoção de elemento do final é também muit simples, devendo exigir uma atenção maior na realocação do elemento anterior (necessidade de um segundo auxiliar) para que seu *prox aponte para o primeiro elemento
int removerFimCircular(Elem **lista){
//Caso 1, lista vazia
if(listaVazia(*lista)){
printf("\n LISTA VAZIA \n");
return 0;
}else{
Elem *aux;
aux = *lista;
//Caso 2, lista contém 1 elemento
if(aux->prox == *lista){
free(aux);
*lista = NULL;
}else{
//Caso 3, lista contém +1 elemento
aux = aux->prox;
while(aux->prox->prox != *lista){
aux = aux->prox;
}
free(aux->prox);
aux->prox = (*lista);
}
}
}
A exibição da lista se faz muito simples, onde será percorrida toda a lista exibindo elemento a elemento. A grande questão é o último elemento que não aponta para NULL. Então em tese, essa seria uma exibição infinita. Para que isso não aconteça, será feita um loop que só irá para quando o aux for igual a lista.
int imprimirListaCircular(Elem *lista){
Elem *aux;
if(listaVazia(lista)){
printf("\n LISTA VAZIA \n");
return 0;
}
aux = lista;
printf("\n LISTA: ");
do{
printf(" %d ",aux->num);
aux = aux->prox;
} while(aux != lista);
printf("\n");
return 1;
}
A liberação da lista já não é segedo algum, uma vez que é sempre a mesma para qalquer lista, bastando percorre-la e ir removendo elemento a elemento até que a lista esteja vazia:
int liberarListaCircular(Elem **lista){
if(listaVazia(lista)){
printf("\n LISTA VAZIA \n");
return 0;
}else{
Elem *aux, *aux2;
aux = (*lista)->prox;
aux2 = aux->prox;
while(aux2 != *lista){
free(aux);
aux = aux2;
aux2 = aux->prox;
}
}
}