How to fix Segmentation Fault in linked list

Question

I'm getting a segmentation fault error that I don't know how to fix. List.cpp and List.hpp are bigger, but I added just what I'm using in main.cpp. Here is the code:

List.hpp

#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <cstdlib>

struct Node{
    int _value;
    Node *_next;
};

struct List{
    Node *_head;
    int _size;

    List();
    void insert(int value);
    void print();
};

#endif

List.cpp

#include "List.hpp"

List::List(){
    _size = 0;
    _head = nullptr;
}

void List::insert(int value){
    Node* node;
    node->_value = value;
    node->_next = _head;
    _head = node;
}

void List::print(){
    Node* head = _head;
    if (_size > 0){
        while(head){
            std::cout << head->_value << " ";
            head = head->_next;
        }
        std::cout<<std::endl;
    }
    else{
        std::cout<<std::endl;
        return;
    }
}

main.cpp

#include <iostream>
#include "List.hpp"

int main(){
    List *L = new List();
    int N=0;
    std::cout << "type the N value"<< std::endl;
    std::cin >> N;

    for(int i=0; i<=N; i++){
        L->insert(i);
    }

    L->print();
    delete L;
    return 0;
}

console

▶ g++ -std=c++14 -Wall main.cpp List.cpp -o main && ./main out
List.cpp: In member function ‘void List::insert(int)’:
List.cpp:10:15: warning: ‘node’ is used uninitialized in this function [-Wuninitialized]
   10 |  node->_value = value;
      |  ~~~~~~~~~~~~~^~~~~~~
type the N value
3
[1]    13247 segmentation fault (core dumped)  ./main out

I actually don't know how to debug it either (I'm using VS Code), so I have no idea about what is happening with the variables that are being created on the stack and on the heap.

Answer 1

Inside the member function insert you are using an uninitialized pointer node

void List::insert(int value){
    Node* node;
    ^^^^^^^^^^^
    node->_value = value;
    node->_next = _head;
    _head = node;
}

that has an indeterminate value and trying to access memory using this pointer that results in undefined behavior.

You have to allocate a node that will be pointed to by the pointer and inserted in the list.

Also you forgot to increase the size of the list.

But I would like to point to some drawbacks of the implementation.

For starters do not use identifiers that start from underscore because according to the C++ Standard

(3.2) — Each identifier that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

So such names will confuse readers of your code.

The structure Node should be a private or protected data member of the structure List. The user shall not have a direct access to the structure Node. It is an implementation detail.

There is no sense to allocate an object of the type List dynamically.

Here is a demonstrative program that shows how the list can be implemented.

#include <iostream>
#include <functional>

class List
{
protected:
    struct Node
    {
        int value;
        Node *next;
    } *head = nullptr;

    size_t n = 0;

public: 
    List() = default;
    ~List() { clear(); }
    
    //  These special member functions you can define yourself if you will want
    List( const List & ) = delete;
    List & operator =( const List & ) = delete;
    

    void insert( int value );

    size_t size() const { return n; }
    
    void clear()
    {
        while ( head ) delete std::exchange( head, head->next );
        n = 0;
    }
    
    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current != nullptr; current = current->next )
        {
            os << current->value << " -> ";
        }
        
        return os << "null";
    }
};

void List::insert( int value )
{
    head = new Node { value, head };
    ++n;
}

int main() 
{
    const int N = 10;
    
    List list;
    
    for ( int i = N; i != 0; i-- )
    {
        list.insert( i );
    }
    
    std::cout << list << '\n';
    
    return 0;
}

The program output is

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null

Answer 2

As the error(warning) message says, in the insert function you are doing:

Node* node;

But this simply declares a pointer that is not yet pointing to valid memory. Accessing members of the object such as _value pointed at by node will invoke undefined behavior. This can cause a segmentation fault. If you're unlucky, there won't be a segfault, and the program will break at some later point.

You need to allocate memory for a Node like this:

Node* node = new Node{};

In fact, the entire insert function could simply be:

void List::insert(int value) {
    _head = new Node{value, _head};  // allocate Node, initialize to
                                     // appropriate values, and link _head
}

---

Also, you should default initialize the members of Node like this:

struct Node{
    int _value{};
    Node *_next = nullptr;
};

---

Also, there seems to be no need to allocate memory for a List in main:

List *L = new List();

Instead, you can simply have a List object like this:

List L{};