Adding head node to singly linked list gives segmentation fault error

2
votes

I started writing this very simple function in C to add node to a singly link list at the head. Here is my function. head parameter is pointer to the first node of the linked list. It can come as NULL if linked list is empty. data is the number to be put in data field of the new node to be added:

Node* InsertAtHead(Node *head, int data)
{
    Node newHeadNode;
    newHeadNode.data = data;
    newHeadNode.next = NULL;

    if (head == NULL)
    {
        head = &newHeadNode;
    }
    else
    {
        newHeadNode.next = head;
        head = &newHeadNode;
    }

    return head;
}

Definition of Head is as below:

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

This works on my machine but not on my colleague's machine. At the other machine the program gives segmentation fault error. What is wrong in my function?

2
cdata-structureslinked-list
Dont you think you need to allocate space for newHeadNode? – SMA
@SMA will that not happen on its own? – RBT
ohhh! I think that gives me some clue @user3121023 . newHeadNode will get allocated on stack since it is local to the function but will get lost once function scope is gone. – RBT
This is not your code..Node* .. won't compile! it should be struct Node* .. unless there is a typedef you are not showing in the question. – ThunderWiring
Maybe your IDE knows how to deal with this. Also, according to correct 'grammar', there is no type called Node, there is struct Node however. – ThunderWiring

2 Answers

1
votes

Your function returns the address of a local variable with automatic storage (aka on the stack) newHeadNode. Using this in the rest of the program invokes undefined behavior. You should instead allocate the node with malloc() and return the pointer to the allocated object:

#include <stdlib.h>

Node *InsertAtHead(Node *head, int data) {
    Node *node = malloc(sizeof(*node));
    if (node != NULL) {
        node->data = data;
        node->next = head;
    }
    return node;
}

Remember to store the return value into the heap pointer of the list unless it is NULL. An alternate safer API is this:

Node *InsertAtHead(Node **head, int data) {
    Node *node = malloc(sizeof(*node));
    if (node != NULL) {
        node->data = data;
        node->next = *head;
        *head = node;  // update the head pointer
    }
    return node;
}

With this API, you pass the address of the head pointer, which only gets updated if allocation succeeds.

0
votes

You have used a local variable for the new node, which will become invalid on function exit. There is also no need to make a separate condition when head == NULL.

Node* InsertAtHead(Node *head, int data)
{
    Node *newNode = malloc(sizeof *newNode);   // note: check the pointer
    newNode->data = data;
    newNode->next = head;
    return newNode;
}