Double Chained List Removal Doubt (C/ Ordered Insertion)

Question

In a C++ class the teacher had proposed an activity where I had to do a program in the format of a double-chained list with ordered insertion. However, I have a problem on the Removal part. By removing all members from either end to the other (from start to finish or vice versa) the program "Chasha" when removing the last member from the list.

I would like to know the reason for the problem, I believe it is in the programming of ant/Prox since there comes a time when the beginning is equal to the end.

All other functions of the program work, just need to fix this detail in the removal. Below is the base structure, the remove function and the "localizar_search" sub-function it uses.

typedef struct aula{
aula *prox;
aula *ant;
int x;
};

aula *localizar_busca(aula *w, int v){
while (w!=NULL && w->x!=v){
    w=w->prox;
}
if(w == NULL)
    return NULL;
else
    return w;
}


void listar(aula **inicio){
aula *x_aux;
int contador=0;
if(*inicio == NULL){
    printf("\n");
    printf("Fila vazia...");
}
else{
    printf("\n");
    x_aux = *inicio;
    do{
        printf("Elemento %d da fila = %d\n", contador, (x_aux)->x);
        contador+=1;
        x_aux = x_aux->prox;
    }
    while(x_aux!= NULL);
}
}


void remover(aula **inicio, aula **fim){
int aux, contador = 0;
aula *enc;
if(*inicio == NULL){
    printf("\nLista vazia, nao ha elementos a serem removidos.");
}
else{
    printf("\nLista atual: \n");
    listar(&*inicio);
    printf("\n\nEscolha um elemento listado a ser removido: ");
    scanf("%d", &aux);
    enc = localizar_busca(*inicio, aux);
    if(enc == NULL){
        printf("\nElemento nao encontrado.");
    }
    else if(aux == (*inicio)->x){
        printf("\n%d removido com sucesso!", (*inicio)->x);
        (*inicio) = (*inicio)->prox;
        (*inicio)->ant = NULL;
    }
    else if(aux == (*fim)->x){
        printf("\n%d removido com sucesso!", (*fim)->x);
        (*fim) = (*fim)->ant;
        (*fim)->prox = NULL;
    }
    else{
        printf("\n%d removido com sucesso!", enc->x);
        enc->ant->prox = enc->prox;
        enc->prox->ant = enc->ant;
        free(enc);
    }
}
}

That is the main:

int main(){
aula *novo, *aux, *inicio = NULL, *fim = NULL;
char OP;

do{
    printf("\nEscolha o que deseja fazer: \n1 - Inserir\n2 - Listar\n3 - Buscar\n4 - Remover\n5 - Esvaziar\n6 - Sair\n");
    OP = getche();

    switch(OP){
    case '1':
        inserir(&inicio, &fim);
        break;
    case '2':
        listar(&inicio);
        break;
    case '3':
        buscar_lista(&inicio, &fim);
        break;
    case '4':
        remover(&inicio, &fim);
        break;
    case '5':
        esvaziar(&inicio, &fim);
        break;
    case '6':
        esvaziar(&inicio, &fim);
        break;
    default:
        printf("\nOP invalido");
        break;
    }
    }while(OP!='6');
return 0;
}

Answer 1

When we analyze what happens if we pass a list with a single node, the problem becomes obvious:

Just a reminder: when the list has only one node, **inicio == **fim and (*inicio)->prox == (*inicio)->ant == (*fim)->prox == (*fim)->ant == NULL.

void remover(aula **inicio, aula **fim) {
    int aux, contador = 0;
    aula *enc;

You start by checking if the list does not contain us, that is, if *inicio is empty. In this case, it is not.

    if(*inicio == NULL) {
        printf("\nLista vazia, nao ha elementos a serem removidos.");
    }
    else {

Since it is not, we show the current list and ask which item should be removed:

        printf("\nLista atual: \n");
        listar(&*inicio);
        printf("\n\nEscolha um elemento listado a ser removido: ");
        scanf("%d", &aux);

The user supposedly chooses the last node left, and then we do a linear search to find the requested node: If not found, we complain.

        enc = localizar_busca(*inicio, aux);
        if(enc == NULL){
            printf("\nElemento nao encontrado.");
        }

Having found, we tested the first case, in which the requested value is (*inicio)->x.

As it is, we enter the if:

        else if(aux == (*inicio)->x){
            printf("\n%d removido com sucesso!", (*inicio)->x);

First, we report success a little prematurely.

            (*inicio) = (*inicio)->prox;

Then we do inicio point to the successor of the initial node, (*inicio)->prox, that as we have seen above, it is NULL.

            (*inicio)->ant = NULL;

Finally, we make the predecessor node of this successor NULL, so that we remove the mention of the unsaved node from the list.

But, (*inicio) already is NULL! Thus, we are trying to write to an invalid memory position (since you cannot unset a null pointer). Result? Segfault.

Below are the other cases, in which we will not enter because they are in else. But note that only in the latter case the free(enc) é executado, de forma que todas as vezes que removemos um nó do princípio ou do fim da lista,sizeof(class)` bytes leak...

        }
        else if(aux == (*fim)->x){
            printf("\n%d removido com sucesso!", (*fim)->x);
            (*fim) = (*fim)->ant;
            (*fim)->prox = NULL;
        }
        else{
            printf("\n%d removido com sucesso!", enc->x);
            enc->ant->prox = enc->prox;
            enc->prox->ant = enc->ant;
            free(enc);
        }
    }
}

My recommendation, therefore, is to include a test case explicitly for enc == *inicio == *fim, in which only Seventh *inicio = *fim = NULL and whether it would give the free() at the remaining node. Finally, it is best to report success only after performing all other operations: it is more correct.