Segmentation fault while trying to insert node into a linked list

Question

I started learning C programming a few days ago through the book, Programming in C, and I have prior knowledge of java. Inserting a node into a linked list is very easy in java, but I thought if I could do the same in C. So, I came up with this program,

#include "node.h"

void insertEntry(struct node* root, struct node* after)
{
    struct node* first = root;
    while(first != (struct node*) 0)
    {
        if(first->value == after->value)
        {
            struct node ins;
            ins.value = 3456;
            ins.next = first->next;
            first->next = &ins;
        }
        first = first->next;
    }
}

int main(void)
{
    struct node n1, n2, n3;
    struct node* list_pointer = &n1;

    n1.value = 100;
    n1.next = &n2;

    n2.value = 200;
    n2.next = &n3;

    n3.value = 300;
    n3.next = (struct node*) 0;

    void insertEntry(struct node* root, struct node* after);

    while (list_pointer != (struct node*) 0)
    {
        printf("%i\n", list_pointer->value);
        list_pointer = list_pointer->next;
    }
    printf("\n");

    list_pointer = &n1;

    insertEntry(list_pointer, &n2);

    while (list_pointer != (struct node*) 0)
    {
        printf("%i\n", list_pointer->value);
        list_pointer = list_pointer->next;
    }

    return 0;
}

node.h

#include <stdio.h>

struct node
{
    int value;
    struct node* next;
};

Basically, this program takes pointer to the first element of the linked list and the pointer to the element after which it is to be inserted, and inserts a new node after this node.

But when I run this, my program crashes and I cannot find where or why this error occurs. I looked over to the code in java and tried to implement the same in C.

Thank you.

Have you used a debugger like gdb to find exactly where the segmentation fault occurs? — Fantastic Mr Fox
– Fantastic Mr Fox, Commented Jul 7, 2015 at 15:19

Dmitry Grigoryev · Accepted Answer · 2015-07-07 15:26:45Z

4

Here's your problem:

    {
        struct node ins;  // You create an object in the stack
        ins.value = 3456;
        ins.next = first->next;
        first->next = &ins;   // You reference your object
    }  // Your object is popped out of the stack and ceases to exist
    // Any access to first->next past this block may cause segfault

In order to avoid this, you could create ins with malloc(), but beware: this isn't java and you have to keep track of all objects you allocated in the heap yourself.

edited Jul 7, 2015 at 15:26

answered Jul 7, 2015 at 15:20

Dmitry Grigoryev

3,2331 gold badge29 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user2371524 · Accepted Answer · 2015-07-07 15:28:23Z

The main problem is you insert a node that is allocated on the stack -- it's invalid as soon as the function is left. To allocate new memory, you need malloc() (don't forget to free() when done, there is no garbage collection).

A few side notes:

It's utterly pointless to cast 0 when used as a pointer to any specific pointer type ... 0 is 0.
You don't need the root node for inserting, so why pass it in the first place?
declaring a prototype inside of a function (in that case: main) doesn't make too much sense ... it will work without because the function you want to call is already defined in the same file.
#include headers where they are needed! node.h doesn't need stdio, the main program does.

A version of roughly your program that would work:

#include <stdio.h>      
#include <stdlib.h>
#include <assert.h>

struct node
{
    int value;
    struct node *next;
};

struct node *insertEntry(struct node* after, int val)
{
    assert(after); /* not NULL */

    struct node *new = malloc(sizeof(struct node));
    new->value = val;
    new->next = after->next;
    after->next = new;
    return new;
}

void freeNodeList(struct node* root)
{
    struct node *current, *last;

    current = root;

    while (current)
    {
        last = current;
        current = current->next;
        free(last);
    }
}

int main(void)
{
    struct node *n1, *n2, *n3;
    struct node *ptr;

    n1 = malloc(sizeof(struct node));
    n2 = malloc(sizeof(struct node));
    n3 = malloc(sizeof(struct node));

    n1->value = 100;
    n1->next = n2;

    n2->value = 200;
    n2->next = n3;

    n3->value = 300;
    n3->next = 0;

    insertEntry(n2, 250);

    ptr = n1;
    while (ptr)
    {
        printf("%d\n", ptr->value);
        ptr = ptr->next;
    }

    freeNodeList(n1);
    return 0;
}

Actually, ins will become invalid as soon as you leave the if block. Once the variable is out of scope, the compiler is free to reuse the memory, even while still executing the same function.

J2R5M3 · Accepted Answer · 2015-07-07 15:21:32Z

0

You should read up on gdb and how to use it.

gcc -Wall -O0 -g x.c -o x

x being your program to compile with debuging information and no optimisation.

then run your program through gdb to find the location/occurrence of the fault. ie.

gdb x

answered Jul 7, 2015 at 15:21

J2R5M3

5753 silver badges9 bronze badges

3 Comments

LPs Over a year ago

This could be a comment not an answer

J2R5M3 Over a year ago

@LPs I'm not allowed to comment yet. Not enough reputation.

J2R5M3 Over a year ago

At least not on OP's post.

Collectives™ on Stack Overflow

Segmentation fault while trying to insert node into a linked list

3 Answers 3

Comments

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related