Inserting a node in LinkedList is giving segmentation error

user_14348290 0
Viewed 58
struct Node
{
   int data;
   Node * next;
   Node (int x)
   {
     data=x;
     next=NULL;
   }     
};

Node * insertInSorted(Node * head, int data)
{
    Node* temp = new Node(data);

    if (head == NULL){
       return temp;
    }

   if (data < head->data){
    temp->next = head
    return temp;
   }
    
    Node* curr = head;
    
    while (curr->next->data < data && curr->next != NULL){
        curr = curr->next;
    }

    temp->next = curr->next;
    curr->next = temp;
    return head;
}

Hi, I've recently learned C++ and have been practicing LinkedList, this question is simple all I've to do is insert an element at its correct position while maintaining the sorted order. My question is why am I getting segmentation fault. I noticed that in the while loop if I flip the order from while (curr->next->data < data && curr->next != NULL) to while (curr->next != NULL && curr->next->data < data) segmentation error does not occur. Can someone please help me understand this problem?

singly-linked-list while-loop data-structures linked-list c++
2 Answers

The way you wrote it, this:

curr->next->data < data

is evaluated before this:

curr->next != NULL

Therefore, curr->next can be NULL when you try to dereference it in curr->next->data, so you access some random part of memory and you get a segmentation fault.

As you said, changing the order fixes it, and that is the correct solution. When the first part of an AND expression is false, the second part is not evaluated, so you won't try to dereference an invalid address, so your problem is fixed.

user_172191850

This while loop

while (curr->next->data < data && curr->next != NULL){
    curr = curr->next;
}

can invoke undefined behavior because there is no check whether curr->next is equal to nullptr before accessing the data member curr->next->data. You need to exchange the operands of the logical AND operator like

while (curr->next != NULL && curr->next->data < data ){
    curr = curr->next;
}

In any case the function can be written without checks of numerous conditions the following way if to use pointer to pointer.

Node * insertInSorted( Node *head, int data )
{
    Node *temp = new Node( data );

    Node **current = &head;

    while ( *current && !( data < ( *current )->data ) )
    {
        current = &( *current )->next;
    }

    temp->next = *current;
    *current = temp;

    return head;
}

Pay attention to that you could pass the pointer to the head node to the function by reference. In this case there is no need to return the pointer to the head node from the function. The user of the original function can forget to assign the returned pointer from the function to the pointer within the caller of the function.

So a more safer function definition can look the following way

void insertInSorted( Node * &head, int data )
{
    Node *temp = new Node( data );

    Node **current = &head;

    while ( *current && !( data < ( *current )->data ) )
    {
        current = &( *current )->next;
    }

    temp->next = *current;
    *current = temp;
}
user_28772410
Related