Insertion at the end of the list resulting in 'Segmentation fault'

Question

When implementing a chained list, I found the following problem in the function that inserts nodes at the end of the list:

Program Received Signal SIGSEGV, Segmentation fault. 0x000000400d2f in insere_fim (ref=0x0, value=1) at main.cpp:82
82 if(ref == nullptr) ref->Prox = newNo;

Program terminated with Signal SIGSEGV, Segmentation fault.
The program no longer exists.

If I insert the third node of the list through the end inserts the program works, but if I call the end inserts before that, the above error occurs. The line that presents the error is this:

if(ref == nullptr) ref->prox = novoNo;

I have tried redoing the function and using other compilers, but the error persists. Below is the code of the structure and functions inserts and inserts end and menu function, responsible for calling the other functions:

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

lista* criaLista() {
  cout << "Lista criada." << endl;
  return nullptr;
}  

lista* insere(lista* ref, int valor) {
  lista* novoNo = nullptr;
  novoNo = new lista;
 if(!novoNo){
  printf("Sem memoria disponivel!\n");
  return ref;
 }
  novoNo->info = valor;
  novoNo->prox = ref;
  ref = novoNo;
  cout << "Nodo com valor " << novoNo->info << " inserido." << endl;
  return ref;
}     

void insere_fim(lista* ref, int valor)
{
 lista* novoNo=nullptr;
 novoNo= new lista;
 if(!novoNo){
  printf("Sem memoria disponivel!\n");
  return;
 }
 novoNo->info=valor;
 novoNo->prox = nullptr;

 if(ref == nullptr) ref->prox = novoNo;
 else{
  lista* p = ref->prox;

  while(p->prox != nullptr)
   p = p->prox;

  p->prox = novoNo;
 }
  cout << "Nodo com valor " << novoNo->info << " inserido." << endl;
}

void menu(int* op, lista* ref) {
  int valor, aux=1;
  cout << "\033[2J\033[1;1H";
  cout << "                 --- Lista encadeada ---\n" << endl;
  while(true) {
    cout << "\n     1-    Criar lista          5-   Inserir no fim da lista\n     2-    Inserir nodo         6-   Liberar memoria\n     3-    Imprimir lista       7-   Encerrar programa\n     4-    Remover nodo\n\nSelecione uma acao: ";
    cin >> *op;
    if((aux==1) && ((*op!=1) && (*op!=7))) {
      cout << "ERRO! Inicie o programa criando uma lista.\n";
      continue;
    }
    switch (*op) {
      case 1 : ref=criaLista(); aux=0;break;
      case 2 : {
        cout << "Valor do nodo: ";
        cin >> valor;
        ref=insere(ref, valor); break;
      }
      case 3 : imprime(ref); break;
      case 4 : {
        cout << "Valor do nodo: ";
        cin >> valor;
        ref=remove(ref, valor); break;
      }
      case 5 : {
        cout << "Valor do nodo: ";
        cin >> valor;
        insere_fim(ref, valor); break;
      }
      case 6 : libera(&ref); break;
      case 7 : break;
      default : cout << "Acao invalida! Tente novamente." << endl;
    }
    if (*op==7) {
      cout << "\n                   Fim do programa! :D     ";
      break;
    }
  }
}

int main () {
  int op; lista* ref;
  menu(&op, ref);
}

Answer 1

Let us begin precisely by if who mentioned:

if(ref == nullptr) ref->prox = novoNo;

If we imagine that the list is empty, and so ref has the value nullptr then ref->prox represents undefined behavior as you are trying to access the pointer value by nullptr, and normally this instruction will generate a Segmentation fault straight. In the end it’s like doing:

(nullptr)->prox = novoNo;

That makes no sense and will never work properly.

How to solve ?

Well, here’s another problem, because in function insere_fim the pointer ref that you have is a copy of what exists in menu and so make ref = novoNo does not change the original pointer.

Two common solutions in C are to pass the pointer pointer of the list, or return the new pointer to stay as the list (this was the solution you used in the function insere). But since this is C++ it would be much better to use something idiomatic, like a reference passage, with &.

Another situation you have in your code is that your first valid element is the second node, as you for the loop on the list starts at ref->prox and not ref, which won’t make sense unless you’re creating a watch list.

Simplify and transform all your insere_fim in:

void insere_fim(lista* &ref, int valor) {
//                     ^-- passagem por referencia
    lista* novoNo = new lista;
    if(!novoNo) {
        cout << "Sem memoria disponivel!" << endl;
        return;
    }
    novoNo->info=valor;
    novoNo->prox = nullptr;

    if(ref == nullptr) ref = novoNo;
    else {
        lista* p = ref; //agora apenas ref
        while(p->prox != nullptr)
            p = p->prox;

        p->prox = novoNo;
    }
    cout << "Nodo com valor " << novoNo->info << " inserido." << endl;
}

Now it will make sense to change also the insere to follow the same principle:

void insere(lista* &ref, int valor) {
//^-- agora void   ^-- passagem por referencia
    lista* novoNo = new lista;
    if(!novoNo) {
        cout << "Sem memoria disponivel!" << endl;
        return;
    }
    novoNo->info = valor;
    novoNo->prox = ref;
    ref = novoNo;
    cout << "Nodo com valor " << novoNo->info << " inserido." << endl;
}

Watch it work on Ideone

Some final notes:

• If you’re doing c++ code, it’s much more natural to use a class, not a structure. This made it possible to create a class for each node in the list and define a constructor, which made it easy enough in the code not to have to assign the info and prox manually.

• No need to pass the op as a pointer to the function menu if it is not used within the main again. It is best to create it as local variable within menu. Don’t go around creating pointers for everything that is there. Just create the ones that are really needed, but end up complicating the code for nothing.

• Remember that if you create a new list over an existing one with option 1 in your menu the first one is lost in memory, creating a memory leak. Soon it would be better to play it safe and delete the entire existing list before creating a new one.