Remove the first element from a double chained list - C

Question

I’m having trouble removing the first node from my double-stranded list. I created a function that returns the list type (Value) to perform the operation, by showing the list elements within the function it is possible to see that it performs the removal of the first element, however by returning it to main and listing it using the printList() function it seems to show the first element that was supposedly removed.

Follow my complete code below. Thanks in advance.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CLEAN "cls"
#define PAUSE "pause"

typedef struct Value{
  int value;
  struct Value *next;
  struct Value *prev;
} Value;

Value *list;

Value *start(){
  return NULL;
}

void freeList(Value *list){
    Value *v = list;
    while(v != NULL){
        printf("Liberando o canal: %d\n", v->value);
        Value *temp = v->next;
        free(v);
        v = temp;
    }
}

int isEmptyList(Value *list){
    return (list == NULL);
}

void menu(){
    printf("\t _______________________________________________________________");
    printf("\n\t|O que Voce Deseja Fazer?\t\t\t\t\t|\n\t|");
    printf("\t\t\t\t\t\t\t\t|\n\t|[01] - Adicionar valor de forma ordenada;\t\t\t|");
    printf("\n\t|[02] - Adicionar valor no fim da lista;\t\t\t|");
    printf("\n\t|[03] - Listar todos os valores;\t\t\t\t|");
    printf("\n\t|[04] - Mostrar o maior valor;\t\t\t\t\t|");
    printf("\n\t|[05] - Mostrar o menor valor;\t\t\t\t\t|");
    printf("\n\t|[06] - Remover ultimo valor;\t\t\t\t\t|");
    printf("\n\t|[07] - Remover primeiro valor;\t\t\t\t\t|");
    printf("\n\t|[08] - Sair;\t\t\t\t\t\t\t|");
    printf("\n\t|_______________________________________________________________|\n");
    printf("\t Opcao: ");
}

Value *insertOrdered(Value *list){
  int value;
  Value *aux = list;
  Value *aux2 = list;
  Value *new = (Value*) malloc(sizeof(Value));

  printf("Informe um valor: ");
  scanf("%d", &value);
  new->value = value;
  if(aux == NULL){
    new->next = aux;
    new->prev = NULL;
  }else{
    while(aux != NULL){
      if(new->value < aux->value){
        new->next = aux;
        if(aux->prev != NULL){
          aux2->next = new;
          aux->prev = new;
          new->prev = aux2;
          return list;
        }else{
          new->prev = NULL;
          aux->prev = new;
          return new;
        }
      }else if(aux->next == NULL){
        aux->next = new;
        new->prev = aux;
        new->next = NULL;
        return list;
      }
      aux2 = aux;
      aux = aux->next;
    }
  }
  return new;
}

Value *insertEnd(Value *list){
  int value;
  Value *aux = list;
  Value *new = (Value*) malloc(sizeof(Value));

  printf("Informe um valor: ");
  scanf("%d", &value);
  new->value = value;
  while(aux != NULL){
    if((aux->next == NULL) && (new->value > aux->value)){
      aux->next = new;
      new->prev = aux->next;
      new->next = NULL;
    }else if((aux->next == NULL) && (new->value < aux->value)){
      printf("O numero informado e menor que o ultimmo valor\n");
      printf("A ordem da lista sera comprometida\n");
      break;
    }
    aux = aux->next;
  }
  return new;
}

void printList(Value *list){
    Value *v = list;
    if(isEmptyList(v)){
        printf("Essa lista está vazia!\n");
    }
    else{
        while(v != NULL){
            printf("\nValor: %d\n", v->value);
            v = v->next;
        }
    }
}

void findBigger(Value *list){
  Value *v = list;
  while(v != NULL){
    if(v->next == NULL){
      printf("O maior valor da lista e: %d\n", v->value);
    }
    v = v->next;
  }
}

void findSmaller(Value *list){
  printf("O maior valor da lista e: %d\n", list->value);
}

Value *removeLast(Value *list){
    Value *v = list;
  if(isEmptyList(v)){
        printf("Essa lista está vazia!\n");
    }else{
    while(v != NULL){
      if(v->next == NULL){
        v->prev->next = NULL;
        printf("Ultimo elemento removido com sucesso\n");
        return list;
      }
      v = v->next;
    }
  }
}

Value *removeFirst(Value *list){
  Value *v = list;
  if(isEmptyList(v)){
        printf("Essa lista está vazia!\n");
    }else{
    if(v->next != NULL){
      v->next->prev = NULL;
    }
    list = v->next;
    v->next = NULL;
    printf("\nValor: %d\n", list->value);
    return list;
  }
}

int main(){

  int op;

  list = start();

  do{
    system(CLEAN);
    menu();
    scanf("%d", &op);
    switch(op){
    case 1:
      system(CLEAN);
      list = insertOrdered(list);
      system(PAUSE);
      break;
    case 2:
      system(CLEAN);
      insertEnd(list);
      system(PAUSE);
      break;
    case 3:
      system(CLEAN);
      printList(list);
      system(PAUSE);
      break;
    case 4:
      system(CLEAN);
      findBigger(list);
      system(PAUSE);
      break;
    case 5:
      system(CLEAN);
      findSmaller(list);
      system(PAUSE);
      break;
    case 6:
      system(CLEAN);
      removeLast(list);
      system(PAUSE);
      break;
    case 7:
      system(CLEAN);
      removeFirst(list);
      system(PAUSE);
      break;
    case 8:
      break;
    }
  }while(op != 8);

    system(CLEAN);
    printf("O programa esta liberando a memória\n");
    freeList(list);
    system(PAUSE);

  return 0;
}

Answer 1

I like the way you structured your program, but your problem happens because of a misunderstanding, or lack of attention in the removal both in the case of removing the first element, and in the case of removing the last, follows below as should be some details of these functions, commenting where you made a comparative mistake.

---

Value *removeLast(Value *list)
Value *removeFirst(Value *list)

First, if your function is not used to return any value, do not set it to return any value. In your code you just call these functions and the return of it does not go anywhere, do not do this, okay that in Windows there is neither Warning, but in other cases there is, and particularly I prefer to program in a way not cause warnings, but it is not a problem, just a advice.

Another problem in the declarations of these functions is that you pass a parameter whose name is identical to that of a global variable, it is okay that the variable you pass as parameter when calling these functions is equal, and it is even recommended that you create generic functions, in case it accepts any struct Value, and your function may end up getting confused as to whether to use the local or global variable whenever you use it list in it. I particularly condemnation the use of global variables, but if you prefer to continue using, do not pass any value to these functions, use list as a global variable, or change the name of the parameter to make it more generic, thus:

void removeLast()
void removeFirst()

---

As to the removeLast, you have some problems in the flow.

If your list is empty, you correctly print that it is empty, if it is not, you should check that its "next" is different from NULL, because then you know that this list does not have only a single value and you should use the variable v to scroll through the list to find the last Value.

If you do not do this check, there will be no "Prev" for you to do the "v->Prev-next=NULL" and the list reference will remain different from NULL as well, only the local reference of v will be void.

Then it would look like this:

if(isEmptyList(v))
    printf("Essa lista está vazia!\n");
else if(v->next != NULL)
{
    /*É possível otimizar porquê já sabemos que o primeiro elemento não é o último,
    mas por didática vou deixar assim*/

    while(v != NULL) 
    {
        if(v->next == NULL)
        {
            printf("Ultimo elemento, %d, removido com sucesso\n",v->value);
            v->prev->next=NULL;
            free(v);
            return;
        }
        v = v->next;
    }
}
else
{
    ...

In the case of Else, then, it’s only if the list nay is empty but the beginning of it is already the last, that is, it contains only one value, and therefore itself list should be released and its reference should be reset, setting it as NULL or starting it by the start() function again, which is basically the same thing:

else
{
    printf("Ultimo elemento, %d, removido com sucesso\n",list->value);
    free(list);
    list=start(); //list=NULL;
}

Understand what to define v as NULL in this case would not be correct, since that list would still save the address for the struct that was released, which is still in memory. Other operations like getting the value using v->value and free(v) would still work, but list would still hold the address for the structure you released.

It is important to know that the function free() does not erase the data from memory, they will remain there at that address, the free() function only warns the Operating System that that memory space can be used to save other data, and therefore any access to that memory area is allowed, But at any given time, you can have data that is no longer what you put in there, but what other processes put in. Memory is not zeroed when you release it, you just liberates she, she is now available to be used by other processes, which you have put there is still there until it is overwritten by another process or by yourself.

Therefore, if you do not define - in case the list contains only one element - that the variable itself list is NULL, everything done with the variable list will still work, as in your case, will still print on the screen this value because you just allowed the OS to overwrite the information there, they are no longer protected and this may cause unwanted effects.

---

The same problem also occurs to remove the first element, would look like this:

if(isEmptyList(list))
    printf("Essa lista está vazia!\n");
else
{
    printf("\nValor Removido: %d\n", list->value);
    if(list->next!=NULL)
    {
        list = list->next;
        free(list->prev);
        list->prev=NULL;
    }
    else
    {
        free(list);
        list = start(); //list = NULL;
    }
}

but in the example you provided, in removing the first element, you end up destroying access to all other values because you define that the list is next, and that the next one is NULL. The right thing to do is to basically release the root of the list, that is, the list itself, but make it list now be next to her, and let her next one have previous NULL, so there’s no reference to the original beginning of the list. I did it simply by moving list to the next and releasing the "Prev", which was the list formerly.

Note that there is also the list problem with a single element, because it will not have "next" to do this, so it must literally release itself list and restart it using start() or assign to NULL.

---

I hope these considerations have helped you, any doubt continue exploring the platform, I hope you have learned more about how it is the functioning of pointers and addressing, certainly my detail is confusing, sometimes it’s confusing even for those who already have experience with it, so don’t feel bad, programming, especially in C, is just like that!