Operation to release a circular list

Question

Operation to release a circular list

Navigation

#1 by (0 votes)
#2 by (0 votes)

1

I'm in doubt about implementing the method of releasing memory from a chained circular 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 am reading it releases after the while the head, but there is segmentatium fault, but I do not know if it is necessary since the aux releases the first node (head);

c lista-encadeada

asked by anonymous 02.05.2017 / 00:28

2 answers

Browse Zip Code by user location [closed] Problems in integration between C ++ and C #

score 0 · Answer 1

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

I did not test the code, but this 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;
}

score 0 · Answer 2

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

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

And also that it is purely circular, and not something like a linear base attached to a circular end.

I think it's counterproductive to create a pointer that will go all over the list for the sole purpose of finding the penultimate element. It's redundant too obvious.

Thinking a little bit, I believe there are some bordering boxes to deal with - empty list, list of one element only ...

Finally, the idea is to treat the circular list as if it were linear. To do this, I will use two pointers: one points to the element that will be deleted, 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 did not test, though.