C linked list - head is always NULL-CodePudding

I want to implement a simple linked list in C. However I only have access to the list element locally, inside the list_append function, but not inside the main-function.

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

typedef struct list_element {
    struct list_element *next;
    int val;
} list_element_t;

typedef struct list {
    struct list_element *first;
} list_t;


int list_append(list_t *list, int value) {
    if (list->first == NULL) { // if case 1
        // This scope is accessed after each list_append-call. I'm expecting it to be accessed only once.
        list = (list_t *) malloc(sizeof(list_t));
        list_element_t *new_ele = (list_element_t *) malloc(sizeof(list_element_t));
        new_ele->next = NULL;
        new_ele->val = value;
        list->first = new_ele;

        printf("list first\n");
        printf("%d\n", list->first->val);
        return value;
    } else {
        printf("Do nothing.\n");
    }


    return -1;
}

int main (int argc, char* argv[]) {
    list_t list;
    list.first = NULL;

    printf("insert 47: %d\n", list_append(&list, 47));
    printf("insert 11: %d\n", list_append(&list, 11));
    printf("%d\n", list.first->val); // This will cause a seg fault.
}

I was expecting the if case 1 is only accessed in the first list_append call, but it's also accessed in the 2nd call (and any further calls).

CodePudding user response：

Your list_append function doesn't do what you think it does.

int list_append(list_t *list, int value) {
   if (list->first == NULL) { // if case 1
       // This scope is accessed after each list_append-call. I'm expecting it to be accessed only once.
       list = (list_t *) malloc(sizeof(list_t));
       list_element_t *new_ele = (list_element_t *) malloc(sizeof(list_element_t));
       new_ele->next = NULL;
       new_ele->val = value;
       list->first = new_ele;

       printf("list first\n");
       printf("%d\n", list->first->val);
       return value;
   }

The list parameter is local to the function. You've modified that, but you have not modified the list it points to. When the function exits, that list is unchanged.

You may have meant to do something like:

int list_append(list_t *list, int value) {
    if (list->first == NULL) { 
        list->first = malloc(sizeof(list_element_t));
        ...

list->first being equivalent to (*list).first where the dereference of the list pointer is more apparent.

CodePudding user response：

I will address the problem from a slightly different perspective. Let's look at these lines one by one:

int list_append(list_t *list, int value) {

So far, we know that list is a pointer. It may point at something or it may be NULL. Chances are, it does point at something at least sometimes, otherwise it wouldn't make much sense to pass it to a function! The object is a list.

if (list->first == NULL)

Now it is possible to say that list definitely points at something, otherwise list->first wouldn't have much sense. One can only use -> with pointers that do points at objects.

    list = malloc(sizeof(list_t));

This line makes list forget what it is pointing at, and make it point at a brand new thing (here, a list_t object just returned by malloc).

It's great when a pointer can be made to point at a new objects. But what about the old object? Where does it go? Is there some other pointer still pointing at it? If so, what are we going to do with two lists? If not, there is a memory leak. Maybe it is not needed anymore? If so, it should be freed before the last pointer that points at it ceases to do so. The objects pointed to by pointers inside the objects that is going to be freed should also be considered the same way. Are those objects still needed? are there other pointers pointing at them? etc etc.

These are questions that are genuinely hard to answer. You should not write code that begets difficult questions.

Compare this to the correct code:

int list_append(list_t *list, int value) {
    if (list->first == NULL) { 
        list->first = malloc(sizeof(list_element_t));

Should you worry about the object that list->first is pointing at? No, there is no such object. That pointer is NULL! So if you have checked a pointer for NULL, you can freely assign to that pointer.

Another situation where you should not worry about the old object is when you declare the pointer locally.

list_element_t* element = other_element;

Here too, there is no old object pointed-to by element before it is initialised.

Every single time you assign to a pointer, you should stop and ask yourself these questions. Is there an object that this pointer is pointing at before the assignment? If so, where does this object go? Do other pointers take care of it, or it is lost forever?

There are cases where you do need to answer these questions, for example, when traversing a linked list:

while (current != NULL) { 
    // do something
    current = current->next;

Here current definitely points at an object. Will that object be lost? Is there something else that points at that object? YES! It's a pointer in the previous node in the list (or the list itself, if current is a head). And the list with all its nodes is not going anywhere. So that object is not going to be lost, it is safe to assign current.

Of course, if you do assign something to a function parameter, you should know that the new value is only seen inside the function. But this is quite a different story.