Seg Fault: Linked List Node Insertion Function [C++]

Question

I have created a function called 'Insert' for inserting a new node in a Linked List. It takes the value and the head node for insertion. When I manually add the nodes myself, the program runs as expected however I get a segmentation fault when I use the function for adding a node.

I am able to make the function work with a couple of little tweaks but there's another catch, I lose the head node's property of just being a pointer, it now contains some garbage data in it which gets printed when I print the LinkedList.

The tweak I perform is:

Change Line 26 to: A->next = NULL;
Change Line 17 to: while(temp->next != NULL)

The 'segmentation fault' occurs at Line 20 (when the tweak is not done):

Line 20 ----->  temp->next = addTo;

I've already tried passing the arguments by reference, using global variables for the head node and checking the logic of the function. The logic works for manually adding a node.

I have attached the complete code below:

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
int data;
ListNode *next;
};

void Insert(int x , ListNode* head)
{
    ListNode* addTo = new ListNode();
    addTo->data = x;
    addTo->next = NULL;

    ListNode* temp;
    temp = head;
    while(temp != NULL)
    temp = temp->next;

    temp->next = addTo;
}

int main()
{
    ListNode* A;
    A = NULL;

    //Inserting A Node Manually
    // ListNode* first = new ListNode();
    // first->data = 9;
    // first->next = NULL;
    // while(A != NULL)
    // A = A->next;
    //     A = first;

    //Inserting using Insert function.
   Insert(2,A);Insert(3,A);Insert(6,A);Insert(7,A);

    //Printing
    ListNode* temp = A;
    while(temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    return 0;
}

I expected the node to be added to the list as the logic seems to be correct, however I am getting a segmentation fault.

Any help/insight into this would help a lot.

Thank You.

Answer 1

Problem 1:

while(temp != NULL)
temp = temp->next;

temp->next = addTo;

Guarantees that temp will be NULL when while(temp != NULL) exits. that means there is no temp to get the next from.

Rather than solve this here, I'm going to move on to problem 2 and kill two birds with one stone.

Problem 2:

void Insert(int x , ListNode* head)

leaves you with no way to update the caller if head is changed in the Insert function. You can change the object pointed at by head, but head itself is just a copy of an address. If you change this copy to point at another address, the caller does not know.

This means every time you call Insert(<number>, A);, A will always be NULL.

Solution:

Pass head into Insert by reference so that it can be updated.

void Insert(int x , ListNode*& head)
                             ^ reference to pointer

head's job is to point at the first item in the list. This makes means it does the same thing as any next pointer: It points at the next item. The only difference is the name. We can get rid of this difference by adding an extra indirection, a pointer to head.

ListNode ** temp = &head;

Note that we cannot use a reference (ListNode *& temp) here because once you initialize a reference to refer to an object, it cannot be changed to refer to a different object. A pointer you can change, allowing us to iterate through the list and always point temp at the next next.

Now head or any next is simply temp. This makes head exactly the same as every other next variable and no special cases are required.

void Insert(int x , ListNode*& head)   
{
    ListNode* addTo = new ListNode(); 
    addTo->data = x;
    addTo->next = NULL; // consider making a smarter ListNode constructor that makes 
                        // it impossible to forget to set next.

    ListNode ** temp = &head; // we can now manipulate the address in head through temp
                  
    while(*temp != NULL) // note the dereference to get the pointed at pointer
                         // temp won't be null, but it could be pointing at a pointer 
                         // that is null, and that is the end of the list
    { // I always use the optional braces. They prevent confusion.
        temp = &(*temp)->next; //get pointer to the next next pointer
                               // we can now manipulate it exactly the same as head. 
    }
    // we exit the loop with a pointer to the next pointer that we wish to point at 
    // the new list item regardless of whether it's head or the next of some later
    // link in the list
    *temp = addTo; // update the pointed at pointer with the new Node.
}

The Community Addition the first answer of How do I properly delete nodes of linked list in C++ demonstrates how to use the same pointer-to-pointer trick to make removing nodes easy.