Operation to release a circular list

Asked

Viewed 402 times

2

I am in doubt in the implementation of the method of releasing the memory of a circular chained list:

void liberarLista() {

   if(head == NULL)
     return; //retorna original(NULL);

    lista *aux, *temp = head;
    while(temp->prox != head) {
        aux = temp;
        temp = temp->prox;
        free(aux);
    }
    head = NULL;
}

In the material I’m reading it releases after the while the head, but it occurs segmentatium fault, but I don’t know if it’s necessary since the aux releases the first node (head);

c chain-list

  • After the first iteration of your while will already generate an error as you try to access the memory address pointed by Head, however it no longer exists as it has just been released.

  • Add more information so we can help

2 answers

0

You need two pointers: one pointing to an initial element, in this case the head, and the other pointing to the pointer "previous" to the head relative to the list, otherwise your pointer will end up losing reference and pointing to junk in memory.

I didn’t get to test the code, but that way it should work:

void liberarLista() 
{
    if (head == NULL)
        return; //retorna original(NULL);

    // Inicia temp apontando para head
    lista *temp = head;

    // Faz temp pular elementos da lista até que aponte para
    // o elemento anterior a head
    while (temp->prox != head)
        temp = temp->prox;

    // Desaloca tudo enquanto temp não aponta para head
    while (temp != head)
    {
        temp->prox = head->prox;
        free(head);
        head = temp->prox;
    }

    // Saiu do loop, temp finalmente aponta para head
    // Agora só precisa desalocar o último elemento 
    free(head); 
    head = NULL;
}

0

For now I’m going to assume that your list is something like

typedef struct list{
   int ID;
   struct list *next;
} list, *listp;

And also that it be purely circular, and not something like a linear base connected on a circular end.

I believe it is counterproductive to create a pointer that will walk the entire list with the sole purpose of finding the penultimate element. It’s too obvious a redundancy.

On second thought, I think you have some borderline little things to deal with - empty list, single element list...

Anyway, the idea is to treat the circular list as if it were linear. For this, I will use two pointers: one points to the element that will be eliminated, and the other points to the next element.

void libera_lista(listp HEAD){

  if (HEAD == NULL)
     return;
  if (HEAD->next == HEAD){ /*A lista tem apenas um elemento*/
    free(HEAD);
    return;
  } 
  aux0 = HEAD->next;
  aux1 = aux0->next;
  while(aux1 != HEAD){
    free(aux0);
    aux0 = aux1;
    aux1 = aux1->next;
  }
  free(aux0);
  free(HEAD);
}

I think that’s it. I didn’t get to test it, though.

Browser other questions tagged c chain-list

You are not signed in. Login or sign up in order to post.