Pointer to beginning of linked list

Question

I am practicing linked list structure while learning pointers and I have problem with appending item in list. Here is my code

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

typedef struct node node_t;
struct node {
    int data;
    node_t* next;
};

void append(node_t *head, int data) {
    if (head == NULL) {
        node_t *node = (node_t*)malloc(sizeof(node_t*));
        node->data = data;
        node->next = NULL;
        head = node;
    } else {
        node_t *node = (node_t*)malloc(sizeof(node_t*));
        node->data = data;
        node->next = NULL;

        if (head->next == NULL) {
            head->next = node;
        } else {
            node_t *current = head;
            while (1) {
                if (current->next == NULL) {
                    current->next = node;
                    break;
                }
                current = current->next;
            }
        }
    }
}

int main(void) {
    node_t *head = NULL;

    append(head, 4);
    append(head, 6);
    printList(head);

    return 0;
}

My code breaks when I do head = node; It doesn't change value of head in main. I think I'm missing something but not sure what. Thank you in advance

Remember that in C arguments to functions are *passed by value*. This means the value is *copied* into the argument variable. Modifying the argument variable (being a copy) does not modify the original value. Please do some research about *emulating pass by value in C*. — Some programmer dude, Feb 09 '20 at 12:33

Vlad from Moscow · Answer 1 · 2020-02-09T14:48:53.303

You are passing the pointer head by value in the function append. So the function deals with a copy of the passed to it pointer. Changing the copy does not influence on the original pointer. Either pass it by reference or return updated head from the function.

The first approach is much better.

The function can look the following way

int append( node_t **head, int data )
{
    node_t *node = malloc( sizeof( node_t ) );
    int success = node != NULL;

    if ( success )
    {
        node->data = data;
        node->next = NULL;

        while ( *head != NULL ) head = &( *head )->next;

        *head = node;
    }

    return success;
}

Here is a demonstrative program.

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

typedef struct node node_t;
struct node
{
    int data;
    node_t *next;
};

int append( node_t **head, int data )
{
    node_t *node = malloc( sizeof( node_t ) );
    int success = node != NULL;

    if ( success )
    {
        node->data = data;
        node->next = NULL;

        while ( *head != NULL ) head = &( *head )->next;

        *head = node;
    }

    return success;
}

void printList( node_t *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }

    puts( "null" );
}

int main(void) 
{
    node_t *head = NULL;

    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        append( &head, i );
    }

    printList( head );

    return 0;
}

Its output is

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

einpoklum · Answer 2 · 2020-02-09T12:42:18.443

0

It seems the problem is you are passing the head pointer by value, so when you change it inside append(), you're only changing a local variable in that function - as opposed to the head variable within main().

This may be a bit confusing - if you pass a pointer, how can you be passing by value? Well, you might want to have a look at this question:

Is passing pointer argument, pass by value in C++?

... and the bottom line is that append() needs to take a node_t** head, and you'll call it from main with append(&head, 4);. See it working on Coliru.

Also you're allocating sizeof(node_t*) per node. You should be allocating sizeof(node_t).

edited Feb 09 '20 at 12:42

answered Feb 09 '20 at 12:34

einpoklum

102,731
48
279
553

if i make it global it still doesnt change it but it should right? – lukaa123 Feb 09 '20 at 12:36
@lukaa123 If you make `head` a global variable, then it depends on whether or not it is 'hidden' by another local variable with the same name. Also, you shouldn't use global variables - it's bad practice that leads to bugs and headaches with larger programs. – einpoklum Feb 09 '20 at 12:37

chqrlie · Answer 3 · 2020-02-09T16:30:04.460

You pass the head of the list by value, so the append function cannot update the pointer in the caller's space, that happens to have the same name head. The head argument in append is a separate variable from the head local variable in main.

You should either pass a pointer to the head node so append can modify it:

void append(node_t **headp, int data) { ...

Or return the possibly modified head node to the caller which will store it back to its own variable:

node_t *append(node_t *head, int data) { ...

In both cases, it is advisable to signal memory allocation failure to the caller. Returning an error code in the first approach is easy, while returning a null pointer in the second approach can work, as long as the caller does not store the return value directly into its head variable, as in case of failure the previous value would be lost.

Here is a modified version with the first approach:

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

typedef struct node node_t;
struct node {
    int data;
    node_t *next;
};

// append a new node to the list, return 0 for success, -1 for allocation failure
int append(node_t **headp, int data) {
    node_t *node = (node_t *)malloc(sizeof(node_t *));
    if (node == NULL)
        return -1;
    node->data = data;
    node->next = NULL;
    if (*headp == NULL) {
        *headp = node;
    } else {
        node_t *current = *headp;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = node;
    }
    return 0;
}

int main(void) {
    node_t *head = NULL;

    if (append(&head, 4) || append(&head, 6))
        printf("node allocation error\n");
    printList(head);
    // should free the list
    return 0;
}

score 0 · Answer 4 · answered Feb 09 '20 at 16:09

It doesn't change value of head in main

Nor should it! If the value of head in main changed when you call append(), then your call to printList() would only print the last node in the list, and you'd have no way to refer to the other nodes in the list.

The reason that head isn't changed has been well explained in other answers, i.e. you're passing the head pointer by value. It's important to understand that the head in main() and the head parameter in append() are entirely different variables.

Pointer to beginning of linked list

4 Answers4