How to remove the first node from a list?

Question

void Inserts (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 being the following :

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--;
    }

Answer 1

Removing the first node is done by changing the pointer head for NULL and dislocating 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
}

Though it’s subtle, it does answer the question:

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

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

If list->head for NULL the list is already empty and there is nothing left to do in a deletion. If list->head is not NULL then it is possible to access list->head->prox, although this may be NULL. And in this case is exactly what is intended because we put NULL in the head through this instruction:

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

Thus passing from 1 element to none.

Edit:

with the code you gave me, I couldn’t remove the first knot

It did not do it correctly with the code I indicated, possibly because it has specific logic that had not been explained until then, or because it did not use it properly.

Here’s an example of Remove working exactly as I wrote it on Ideone

Considering the code you added in the edition:

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

If that’s the case then be the 0 or the head is the same thing.

If atual corresponds to list->head then

list->head = atual->ant;

Corresponds to:

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

That as it is NULL and equal to prox, corresponds in fact to what I had written!

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

The logic for removing a middle node in 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 number is actually the last one because atual->prox->ant crashes the program if atual->prox for NULL then a specific test should be made for that case, and the same happens in the code presented.

Edit 2:

Looking for the whole code indicated on ideone, I see that there are several small things that need adjustments, which is visible by the amount of warnings nominee.

However, to put it to work on the remove part just change the function to not have the first if because it’s the same as the second one just as I indicated, and if it’s there it doesn’t do anything soon it doesn’t remove, because the removal is being done in the if then it will no longer perform if you enter the first.

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 adjustments:

• The function of Busca is making a comparison char to char. Simplify using strcmp library <string.h> . 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 stay:

  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
  }
  

• In the RemoverDados the auxiliary nodes are no longer being used, these:

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

  And so they can be removed, however, these also would 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 to say:

  No* aux; //cria só o ponteiro
  

  It’s quite different from this:

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

  Which creates the pointer and allocates memory to the corresponding structure, and which is not the correct one to remove and was previously creating a memory leak. Whenever we need pointers just to navigate a list we’re not supposed to use malloc, but only create the pointer.

• In the main to make it totally correct also help to have a return, something like

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

  Or using the #define that already in stdlib.h:

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

Edit 3:

Trying not to make my answer too extensive (and it is already quite extensive), the biggest problem is in fact in the insertion because it does not build the previous pointers correctly. It should be as follows:

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’re doing 2º->ant = 1º. Without the former built when the RemoverDados tries to access the previous ones do not get correct values and so simply did not work.

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

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 must 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--;
}