Remove element from a chained list

Asked

Viewed 1,697 times

3

I am implementing a chained list of type "with head". It follows struct referring to the list and its creation in main()

struct lista{
    int info;
    struct lista *prox;
};
typedef struct lista Lista;


int main ()
{
    Lista *l, *aux;

    l = (Lista*) malloc(sizeof(Lista));

    l->prox = NULL;

    //Trechos de código

    retira_n(l, n);
}

Then follows the function that removes all occurrences of a given number "n" from the list and returns the list

Lista* retira_n(Lista *l, int n)
{
    Lista *atual, *ant, *atual2;
    int flag = 0;

    atual = l->prox;
    ant = l->prox;

    while(atual != NULL)
    {
        if(atual == l->prox && atual->info == n)
        {
            l->prox = atual->prox;
            free(atual);
            atual = l->prox;
            flag++;
            continue;
        }
        else if(atual->info == n)
        {
            ant->prox = atual->prox;
            flag++;
        }

        ant = atual;
        atual = atual->prox;
    }

    if(flag == 0)
    {
        printf("O elemento nao esta na lista");
    }

    return l->prox;
}

The function is working in a partial way, that is, the elements of the list are not shown when I am going to "print" the list, however for not being able to find a way to displace the memory with the free() function, because if I go to displace using the "current" pointerfor example, I won’t be able to use it in other iterations to check the other elements of the list. I wanted a way to de-locate the element that I want to exclude and not just make the previous point to the next element on the list.

c list allocation chain-list

  • If I understand correctly you have a problem that is not so simple to solve a C. You have to control the lifetime of an element that can have multiple references. You would probably have to create a reference counter (and not allow cyclical references or have to use a weak reference). I don’t think you have any idea what I’m talking about. This shows that it is too complex a problem to attack in an exercise, unless the exercise is actually advanced and the intention is to apply the Counting. It has even more advanced techniques.

2 answers

2

Your code is confused in some ways - but to answer what you want, just rewrite the second if so:

    else if(atual->info == n)
    {
        ant->prox = atual->prox;
        free(atual);
        atual = ant->prox;
        flag++;
    } else {
         ant->prox = atual;
         atual = atual->prox;
    }

Note that it also changes to only advance the "ant" if the current number has not been removed - the lines outside the if changing ant and atual should not be executed if the node has been removed (the ant the same and the atual advances).

Tip: Avoid using a variable named "l"- is a hard symbol to distinguish from "1". Another tip: your variable is a counter or is a flag - if it is a counter, avoid calling it "flag".

  • No, further down in the code it repositions both pointers, so it will skip checking a node.

  • Thanks @Daviaragao - corrected.

  • This current = current->Prox; it is necessary?

  • Yes - without it the whole loop will always stay at the same node, and will not go through the list.

2

Creating an additional pointer and causing it to point to the position of atual before atual receive the next you isolate the memory address to be released, then you can use the free normally.

Lista* retira_n(Lista *l, int n)
{
    Lista *atual, *ant, *atual2, *morto;
    int flag = 0;

    atual = l->prox;
    ant = l->prox;

    while(atual != NULL)
    {
        if(atual == l->prox && atual->info == n)
        {
            l->prox = atual->prox;
            morto = atual;
            atual = atual->prox;
            flag++;

        }
        else if(atual->info == n)
        {
            ant->prox = atual->prox;
            morto = atual;
            atual = atual->prox;
            flag++;
        }
        else
        {
            ant = atual;
            atual = atual->prox;
        }
        free(morto);
    }

    if(flag == 0)
    {
        printf("O elemento nao esta na lista");
    }

    return l->prox;
}

Browser other questions tagged c list allocation chain-list

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