Search code examples
cmallocundefined-behaviorsingly-linked-liststorage-duration

Linked list without malloc


I'm starting to learn C myself, and based on the book "Programming in C (4th Edition)", the author defined a linked list as following:

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

struct entry *createNewLinkList(void)
{
    struct entry n1, n2, n3;
    struct entry *list_pointer = &n1;

    n1.value = 100;
    n1.next = &n2;
    n2.value = 200;
    n2.next = &n3;
    n3.value = 300;
    n3.next = NULL;
    return list_pointer;
}

void print_linked_list(struct entry *linked_list)
{
    struct entry *current = linked_list;
    while (current != NULL)
    {
        printf("%d\n", current->value);
        current = current->next;
    }
    printf("\n");
}

int main(void)
{
    struct entry *linked_list = createNewLinkList(); //DEBUG: This line is fine linked_list: {value:100, next:0x000000016fdff200}
    printf("Original list \n");
    print_linked_list(linked_list);   //DEBUG: it is wrong after entering this line linked_list:{value:1876947504, next:0x8b7a000100003f48}
}

I don't understand why the value of linked_list just changed to some address.

Is will work if I create a linked list with malloc like this:

struct entry *createNewLinkList(void)
{
    struct entry *n1 = (struct entry *)malloc(sizeof(struct entry));
    struct entry *n2 = (struct entry *)malloc(sizeof(struct entry));
    struct entry *n3 = (struct entry *)malloc(sizeof(struct entry));

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

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

    n3->value = 300;
    n3->next = NULL;
    return n1;
}

Thank you in advance,


Solution

  • The program in the book (if it is indeed the code from the book) has undefined behavior.

    The function createNewLinkList returns a pointer to a local object with automatic storage duration (n1) that will not be alive (along with other local variables that are chained through pointers) after exiting the function

    struct entry *createNewLinkList(void)
    {
        struct entry n1, n2, n3;
        struct entry *list_pointer = &n1;
    
        n1.value = 100;
        n1.next = &n2;
        n2.value = 200;
        n2.next = &n3;
        n3.value = 300;
        n3.next = NULL;
        return list_pointer;
    }
    

    So dereferencing the pointer (and other pointers stored in the data member next of the structure) within the function print_linked_list

    void print_linked_list(struct entry *linked_list)
    {
        struct entry *current = linked_list;
        while (current != NULL)
        {
            printf("%d\n", current->value);
            current = current->next;
        }
        printf("\n");
    }
    

    invokes undefined behavior.

    The program could be correct if the variables n1, n2, n3 had static storage duration that is if they would be declared like

    static struct entry n1, n2, n3;