How to remove the first node from a list?

0

void Insert (List * list) {

DadoNo dado;
int p = list->size;
No* n = (No*) malloc(sizeof(No));
n->ant = list->head;

scanf("%s", dado.nome);

if (Busca(list, dado.nome) == NULL){

    n->dado = dado;
    n->prox = list->head;
    list->head = n;
    list->size++;
    n->pos = p;     

So, how to access n-> prox or n-> ant, for n = pioneer node, in a possible removal?

My removal code is as follows:

if (!listVazia(list)){   // Verifico se a linha está vazia

    if (atual != NULL){   // atual é o ponteiro que retorna da busca

        if (atual->pos == 0 ){   // o primeiro nó inserido na lista

           atual = atual->prox;
        }

        else if( atual == list->head){  // este funciona OK

            list->head = atual->ant;
        }

        else {      // este tammbém apresenta problemas p remover um nó do meio

            aux = atual->ant;
            aux1 = atual->prox;

            aux->prox = aux1;

        }

        free(atual);
        list->size--;
    }
    
asked by anonymous 30.07.2017 / 02:28

1 answer

1

Removing the first node is done by changing the pointer head to NULL and deallocating in memory the node that is there. An implementation that contemplates this scenario would be:

//remover à cabeça
void Remove (Lista* list){ 
     if (list == NULL || list->head == NULL) return; //se vazia nada a fazer senão sair

     No* NoARemover = list->head; //guarda um ponteiro para o nó que vai ser removido
     list->head = list->head->prox; //faz o head passar a ser o seguinte
     free(NoARemover); //desaloca o antigo head de memoria
     list->size--; //reajusta o size para o valor correto
}

Although it is subtle, it answers the question:

  

your next and previous parameters are null [...]

     

So, how to access n-> prox or n-> ant, for n = pioneer node, in a   possible removal?

If list->head is NULL the list is already empty and there is nothing else to do in a removal. If list->head is not NULL then it is possible to access list->head->prox , although it can be NULL . And in this case it is exactly what we want because we put NULL in head through this statement:

list->head = list->head->prox; //faz o head passar a ser o seguinte

Turning from 1 element to none.

Edit:

  

With the code you gave me, I could not remove the first node

You did not do it correctly with the code I indicated, possibly because you have specific logic that you did not explain before, or because you did not use it properly.

Here is an example of Remove to work exactly as I wrote it on Ideone

Considering the code you added in the edit:

if (atual->pos == 0 ){ and else if( atual == list->head){ are actually the same thing, assuming their positions are incremental starting from 0 at start.

If it is the case then the 0 or head is the same thing.

If atual corresponds to list->head then

list->head = atual->ant;

Corresponds to:

list->head = list->head->ant;

Since it is NULL and equal to prox , it corresponds to what I wrote!

list->head = list->head->prox;

The logic to remove a middle node from a double-linked list is usually the following:

//o seguinte ao Nó a remover define como anterior o anterior do corrente
atual->prox->ant = atual->ant; 
//o anterior ao Nó a remover define como o próximo do próximo do corrente
atual->ant->prox = atual->prox;
//liberta memoria do no corrente, o a remover
free(atual);
It is also important to mention that this logic will not work if the middle one is actually the last because atual->prox->ant crash the program if atual->prox is NULL soon a specific test must be done for this case, and the same thing happens in the given code.

Edit 2 :

Looking at the whole code indicated in ideone , I see that there are several small things that need adjustment, which is visible by the amount of warnings

However, in order to work in the remove part, simply change the function to not have the first if because it is the same as the second as it was indicated, and if there is nothing, it does not remove it since the removal is to be done on the if below that will no longer execute if you enter the first one.

You should then stay:

    if (atual != NULL){
        /*if (atual->pos == 0){

        }
        else */if( atual == list->head){

            list->head = atual->ant;
        }
        else {

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

        free(atual);
        list->size--;
    }

Relevant settings:

  • The Busca function is comparing char to char . Simplify using strcmp of <string.h> library. This same function is not returning NULL when it does not find the searched text, which is something necessary for the rest of the code to work correctly.

    This function could simply be:

    No* Busca ( Lista *list, char *nome){
        No* ptr = list->head;
    
        while (ptr != NULL){
            //agora compara com strcmp da biblioteca de strings
            if (strcmp( nome, ptr->dado.nome) == 0){ //strcmp devolve 0 quando são iguais
                return ptr;
            }
    
            ptr = ptr->prox;
        }
    
        return NULL; //agora retorna NULL caso não nenhum
    }
    
  • As% nodes are no longer in use, these are:

    void RemoverDados ( Lista *list){
        ...
        No* aux = (No*)malloc(sizeof(No));
        No* aux1 = (No*)malloc(sizeof(No));
    

    And so they can be removed, however, these would also not be correct in a remove function. Creating a pointer is different from creating a pointer and allocating memory to the corresponding structure.

    That is this:

    No* aux; //cria só o ponteiro
    

    It's very different from this:

    No* aux = (No*)malloc(sizeof(No)); 
    

    It creates the pointer and allocates memory for the corresponding structure, and it is not the correct one to remove and was previously creating a memory leak. Whenever we need pointers just to navigate a list we are not supposed to use RemoverDados , but rather just create the pointer.

  • In main to make it totally right, you should also have a return, something like

    int main(){
        ...
        return 0;
    }
    

    Or using malloc already in #define :

    int main(){
        ...
        return EXIT_SUCCESS;
    }
    

Edit 3 :

Trying not to make my answer very extensive (and that's enough), the biggest problem is actually in the insert because it does not build the previous pointers correctly. It should look like this:

if (Busca(list, dado.nome) == NULL){
    ...
    n->dado = dado;
    n->prox = list->head;

    //faltava este if para construir o ant caso não seja o primeiro
    if (list->head != NULL){ 
        list->head->ant = n; //construção do anterior aqui
    }

    list->head = n;
    list->size++;

    n->pos = p;
}

In short, we are doing stdlib.h . Without the previous ones built when 2º->ant = 1º tries to access the previous ones they do not get correct values and therefore simply did not work.

The RemoverDados is also not complete, according to what I said before:

  

It is also important to mention that this logic will not work if the   in the middle is actually the last

And to be complete you should then become:

if (atual != NULL){

    if( atual == list->head){
        list->head = atual->prox;
    }
    else if (atual -> prox == NULL){ //caso que faltava para o ultimo!
        atual->ant->prox = NULL; //o proximo do penultimo passa a apontar para NULL
    }
    else {
        atual->prox->ant = atual->ant;
        atual->ant->prox = atual->prox;
    }

    free(atual);
    list->size--;
}
    
30.07.2017 / 04:03