simple linked list failing to print

Question

I am learning how to make a linked list, but its failing to print out anything at all, and I cant figure out why??? please help. I believe it has something to do with my pointers but I don't know what it is.

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

// typedef is used to give a data type a new name
typedef struct node * link ;// link is now type struct node pointer

/*
    typedef allows us to say "link ptr"
    instead of "struct node * ptr"
*/

struct node{
    int item ;// this is the data
    link next ;//same as struct node * next, next is a pointer
};

void printAll(link head); // print a linked list , starting at link head
void addFirst(link ptr, int val ); // add a node with given value to a list
link removeLast(link ptr); // removes and returns the last element in the link

//prints the link
void printAll(link head){
    link ptr = head;
    printf("\nPrinting Linked List:\n");
    while(ptr != NULL){
        printf(" %d ", (*ptr).item);
        ptr = (*ptr).next;// same as ptr->next
    }
    printf("\n");
}

//adds to the head of the link
void addFirst(link ptr, int val ){
    link tmp = malloc(sizeof(struct node));// allocates memory for the node
    tmp->item = val;
    tmp->next = ptr;
    ptr = tmp;
}

// testing
int main(void) {
    link head = NULL;// same as struct node * head, head is a pointer type

    //populating list
    for(int i = 0; i<3; i++){
        addFirst(head, i);
    }

    printAll(head);

    return 0;
}

output:

Printing Linked List:

Process returned 0 (0x0) execution time : 0.059 s

Press any key to continue

Answer 1

It's because you're passing a null pointer to your function and the condition for exiting the loop is for that pointer to be null, so nothing happens. Your addFirst function takes a pointer's value, but it cannot modify the head that you declared inside of main(). To modify head you need to pass a pointer to link, then you can dereference that pointer to access your head and you can then change it.

void addFirst(link *ptr, int val ){
    link tmp = malloc(sizeof(struct node));// allocates memory for the node
    tmp->item = val;
    tmp->next = *ptr;
    *ptr = tmp;
}

Now you can change the head pointer. Just remember to pass the address to it when calling the function. addFirst(&head,i)

Answer 2

In the for loop

for(int i = 0; i<3; i++){
    addFirst(head, i);
}

you create a bunch of pointers which all point to NULL. head is never changing since pointer itself is passed "by value". E.g. head is copied and all modifications to the pointer itself in addFirst are not visible outside.

This is the same as with say int. Imagine void foo(int x);. Whatever this function does to x is not visible outside.

However changes to the memory which link ptr points to are visible of course.

E.g. this line does nothing:

   tmp->next = ptr;
   ptr = tmp;      <=== this line
}

You can fix this in several ways. One is to return new node from addFirst and another one is to make link ptr to be a pointer to pointer: link *ptr. Since in this case you want to change pointer value (not pointee value):

//link *ptr here a pointer to pointer
void addFirst(link * ptr, int val ){
    link tmp = malloc(sizeof(struct node));// allocates memory for the node
    tmp->item = val;
    tmp->next = *ptr; //<<changed
    *ptr = tmp;    //<<changed
}

Do not forget to update declaration above also. And the call:

void addFirst(link * ptr, int val ); // add a node with given value to a list

...
for(int i = 0; i<3; i++){
    addFirst(&head, i);
}

Then this code produces:

Printing Linked List:
 2  1  0

Added: It's important to understand that working with linked list requires working with two different types of data.

First is struct node and you pass around this type of data using links.

Second is head. This is a pointer to the very first node. When you would like to modify the head you find it is not a "node". It is something else. It's a "name" for the first node in the list. This name by itself is a pointer to node. See how memory layout for head is different from the list itself.

head[8 bytes]->node1[16 bytes]->node2[16 bytes]->...->nodek[16 bytes]->NULL;

by the way - the only thing which have lexical name here is head. All the nodes do not have name and accessible through node->next syntax.

You can also imagine another pointer here, link last which will point to nodek. Again this will have different memory layout from nodes itself. And if you would like to modify that in a function you will need to pass to function pointer to that (e.g.pointer to pointer).

Pointer and data it points to are different things. In your mind you need to separate them. Pointer is like int or float. It is passed "by value" to functions. Yes link ptr is already pointer and that permits you to update the data it points to. However the pointer itself is passed by value and updates to pointer (in your case ptr=tmp) are not visible outside.

(*ptr).next=xxx will be visible of course because data is updated (not pointer). That means you need to do one extra step - make changes to your pointer visible outside of function, e.g. convert the pointer itself (head) into data for another pointer, e.g. use struct node **ptr (first star here says this is pointer to a node, and the second star converts that pointer to data for another pointer.