My linked list results in segmentation fault every time even though I cannot see a flaw

Viewed 57

I've been learning programming for some while now and I've seen this concept of "linked list" a few times and decided to give it a try:

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

typedef struct cell {
    int number;
    struct cell* next;
} cell;

typedef struct {
    cell* head;
} cell_list;


void push_front(cell_list* list, int number) {
    printf("here\n");
    cell* n;
    printf("here2\n");
    n->number = number;
    printf("here3\n");
    n->next = list->head;
    printf("here4\n");
    list->head = n;
}

int main(int argc, char* argv[]) {
    cell_list* L;

    push_front(L, 5);
    push_front(L, 8);
    push_front(L, 19);

    cell* n = L->head;

    // this should print "19 8 5"
    while(n != NULL) {
        printf("Val: %d\n", n->number);
        n = n->next;
    }

    return 0;
}

output:

here
here2
here3
Segmentation fault: 11

I am looking for an answer to the following two questions: (1) What is the correct way of doing this (2) What is actually happening in my example? What is going wrong?

I am thinking that it is the compiler that fails to assign "struct cell* next" to be equal to "cell* head", etc.) OR that the FIRST allocated memory for head and the fist cell with the next property is at fault here.

Also similar posts and questions have answer to questions identical to mine however they fail at multiple points: (1) the code example posted by OP is overly complex (2) the code answers are good but... check 3 (3) the code answers and not explained, just "omg just use malloc you are casting voids everywhere" (4) 1 - 3 results in a complete post with Q&A that is above my level. If your answer is "use malloc" or "the pointers point at random memory" or "you are pointing at null". Please explain because these are just programming jargon/language sentences that don't actually go into depth so that I, a beginner, can understand.

I am fully aware there are identical posts but none truly explain to a beginner like me why they allocate memory will malloc and cast the allocated space to become a linked list struct. If your answer is the same as in any of those posts, then please explain why this way is faulty and not just "This is how you do, there are 12893 posts about malloc and linked lists." I understand malloc and casting if that was not obvious but not how they properly fit in here and how my current program is created on the stack.

2 Answers

In the function push_front,

cell* n;

is a pointer of type cell and as David C Rankin rightly said it is uninitialized and currently holds an indeterminate address as its value until you initialize it by assigning a valid address. It does not point to a memory of type cell just like that until you make it point to a cell type.

Use malloc to allocate memory. You can refer the manual page for malloc.

cell *n= malloc(sizeof(cell));

The very next thing your code should do is to check if call to malloc has successfully allocated memory or not and some error handling if memory is not allocated.

if(NULL == n)
{
    //! handle memory allocation error here
}

You also need to free this memory once you are done using it, and make the pointer point to null.

free(n);
n = NULL;

Based on your critical rant/comment at the end of original post, let me explain the code you wrote to you.

void push_front(cell_list* list, int number)
{
    /// This print helps you understand where the code is.
    printf("here\n");
    /// This declares is a pointer variable pointing to a `cell` type. 
    /// Not yet pointing since not initialized.
    cell* n;
    /// This print helps you understand where the code is.
    printf("here2\n");
    /// Tries to assign value of 'number' to 'number' variable present in 
    /// some memory accessed as data type `cell` via a pointer. 
    /// But wait, is pointer really pointing to a valid memory location 
    /// that can be access as `cell` type? NO!
    n->number = number; // You try to sit in a chair which isn't there, you fall!
    printf("here3\n");
    n->next = list->head; // You try to sit on a chair which isn't there, you fall!
    printf("here4\n");
    list->head = n; // This is a different problem as of now. 
                    // With 'n' not initialized, list->head also get
                    // corrupted since assigned with a garbage value. 
}

Also, in your main() function,

cell_list* L;

and then you invoke

push_front(L, 5);

In this function, you do the following:

n->next = list->head;

You design does not consider if list->head is initialized or not. If it is NULL you just made n->next point to NULL.

I understand and agree to the fact that a lot of people find pointers hard to understand and use correctly. I'll suggest that you first get comfortable with pointers overall (in general) and then go for implementing data structures with them. We all started there! You can start here.

You have to allocate memory for nodes using malloc. Here is the updated code, I have tested it, it is working fine :)

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

typedef struct cell {
    int number;
    struct cell* next;
} cell;

typedef struct {
    cell* head;
} cell_list;


void push_front(cell_list* list, int number) {
    printf("here\n");
    cell* n = malloc(sizeof(cell));
    printf("here2\n");
    n->number = number;
    printf("here3\n");
    n->next = list->head;
    printf("here4\n");
    list->head = n;
}

int main(int argc, char* argv[]) {
    cell_list* L = malloc(sizeof(cell_list));

    push_front(L, 5);
    push_front(L, 8);
    push_front(L, 19);

    cell* n = L->head;

    // this should print "19 8 5"
    while(n != NULL) {
        printf("Val: %d\n", n->number);
        n = n->next;
    }

    return 0;
}
Related