Adding head node to singly linked list gives segmentation fault error

Question

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?

Dont you think you need to allocate space for `newHeadNode`? — SMA, Oct 29 '16 at 13:43
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, Oct 29 '16 at 13:47
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, Oct 30 '16 at 15:26
@ThunderWiring it is compiling successfully in the current state without defining any `typedef`. The reason being I'm using a C++ project template to run my C code. Unfortunately, Visual Studio doesn't support any C language specific project template. So I'm forced to write my C language program in *.cpp files. — RBT, Oct 31 '16 at 01:16
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, Oct 31 '16 at 04:57

chqrlie · Accepted Answer · 2016-10-29T15:37:50.807

1

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.

edited Oct 29 '16 at 15:37

answered Oct 29 '16 at 14:03

chqrlie

131,814
10
121
189

I am getting few compilation errors in first line of your first code snippet. I changed it to `Node *node = (Node*) malloc(sizeof(Node)); ` to make it work. – RBT Oct 29 '16 at 14:58
1

Your compiler might be configured as a C++ compiler. The cast is not necessary and considered counter-productive in C. Do you include ``? – chqrlie Oct 29 '16 at 15:36
But for writing C Programs in Visual Studio there is no specific way I believe. I simply use new C++ console project template wizard. There is no project template specific to C projects in Visual Studio. I simply write my C programs in code files having *.cpp extension. As long as I'm restricting myself to using structs, pointers etc it is as good as a C program. Essentially I refrain from using C++ constructs like new operator. – RBT Oct 29 '16 at 16:01
2

@RBT: I did suspect you were using Microsoft tools, and I understand the constraints. Be aware that C++ and C are different languages, even if you restrict yourself to the subset of C++ that looks like C. You can try enclosing your C code in a `extern "C" {` ... `}` block to force the compiler to use C semantics, but Visual Studio is not a C99 compliant compiler / library combination. You can also install cygwin or a linux virtual machine to get a *real* C environment. – chqrlie Oct 29 '16 at 16:12
Interesting indeed! I got some details of this extern stuff [here](http://stackoverflow.com/questions/1041866/in-c-source-what-is-the-effect-of-extern-c). I'll try Ubuntu on an unallocated partition on my hard drive if that's the case. Cheers! – RBT Oct 30 '16 at 01:31
I enclosed my entire main function inside an `extern "C" {...}` block but then it starts giving error `'initializing': cannot convert from 'void *' to 'Node *` if I don't use the cast for pointer. In the line `Node *node = malloc(sizeof(*node));` you have put the asterisk sign before `node` variable. Is that correct? – RBT Oct 30 '16 at 02:08
1

@RBT: yes, that's correct. Your C++ compiler cannot behave exactly like a C compiler. This difference is not significant here as you can fix it by adding the cast. `void*` pointers cannot be converted implicitly to other pointer types in C++. – chqrlie Oct 30 '16 at 09:24
I was able to reach bit closer to `C` specific code compilation. Every C++ project in Visual Studio has a setting `Project Properties -> Configuration Properties -> C/C++ -> Advanced -> Compile As`. I set this option to `Compile As C Code (/TC)`. Now I don't require the pointer casting as you had advised earlier. Now this piece of code `Node *node = malloc(sizeof(*node));` works as is for me as well. Hurrah! – RBT Oct 31 '16 at 02:00
1

@RBT: good find! also change the extension from `.cpp` to `.c` to avoid confusion. – chqrlie Oct 31 '16 at 11:52

score 0 · Answer 2 · answered Oct 29 '16 at 14:02

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;
}

Adding head node to singly linked list gives segmentation fault error

2 Answers2