RBT RBT - 1 month ago 10
C Question

Adding head node to singly linked list gives segmentation fault error

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?

Answer

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.