C adding node to head of linked list

Question

I have created a linked list struct in c

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

a method to add a node at the start of the list :

void addFirst(struct node *list, int value){
    struct node *new_node = (struct node*) malloc (sizeof (struct node));
    new_node->value = value;
    new_node->next = list;
    list = new_node;
   }

I create a list (malloc and everything), then call this method, it adds the new node inside the method but when i get back to my main my old list remains unchanged. Using DDD debugger to check everything. How is this possible? I am not able to change the method signature so it has to be done like this.

Solution 1

If you really need to do it this way, you have to re-cast the pointer. Something like this:

struct node *my_list = null;
addFirst((struct node *)&my_list, 123);

void addFirst(struct node *list, int value){
    struct node **real_list = (struct node **)list;
    struct node *new_node = (struct node*) malloc (sizeof (struct node));
    new_node->value = value;
    new_node->next = *real_list;
    *real_list = new_node;
}

Solution 2

the node pointer could not be changed into the function in this way. in the function you are able to change the content of the pointer and not the address of the pointer. To do you have to pass your pointer of pointer struct node **list

here after how to do it:

void addFirst(struct node **list, int value){
    struct node *new_node = (struct node*) malloc (sizeof (struct node));
    new_node->value = value;
    new_node->next = *list;
    *list = new_node;
}

or you can do it in this way

struct node * addFirst(struct node *list, int value){
    struct node *new_node = (struct node*) malloc (sizeof (struct node));
    new_node->value = value;
    new_node->next = list;
    return new_node;
}

and in your cod you can get the head after the call of this function

head = addfirst(head,45);

Solution 3

In C, if you want a function to be able to change a value it received in its arguments, you need to pass the address of that value. So, to change the value of the list pointer, you need to pass the address of the list pointer. Your addFirst() function should look like this :

void addFirst(struct node **list, int value){
     struct node *new_node = (struct node*) malloc (sizeof (struct node));
     new_node->value = value;
     new_node->next = *list;
     *list = new_node;
}

And when calling that function, you call it like this :

addFirst(&list, value);

Now, if you want to keep the function's signature, a possibility is to change the way you consider the head node. If you state that your head node is purpose is only to hold a pointer to the first value, but does not contain a value by itself, you can do something like this :

struct node *head;

void addFirst(struct node *list, int value){
     struct node *new_node = (struct node*) malloc (sizeof (struct node));
     new_node->value = value;
     new_node->next = list->next;
     list->next = new_node;
}

addFirst(head, 45);

Now, you only have all your functions that work on the list to be change so they work the same, to consider that 'head' is only pointing to the real first node of the list but is not a member of the list itself. The 'real' head is, for all practical purpose, head->next.

Solution 4

I have learned @Vlad Lazarenko answer,and I made the code like this ,is it right?

addFirst((struct node**)head,123);

void addFirst(struct node **list,int value)
{
    struct node *new_node=malloc(sizeof(struct node));
    new_node->value=value;
    new_node->next=*list;
    list=&new_node;
}

Solution 5

void addFirst(struct node **list, int value){
    struct node *new_node = (struct node*) malloc (sizeof (struct node));
    new_node->value = value;
    new_node->next = *list;
    *list = new_node;
}

This is the correct code. the problem is that the poineter struct node *list You are passing can't be changed as it is a stack variable. If you change it to struct node **list you are passing a pointer to the first node of the list. now you can change that to point to the new first node of the list.

View more solutions

Comments

[Onica Radu]

I knew it can be done like this (node** as argument) but isnt there a way to do it like i wrote ? :(

[Onica Radu]

There has to be a way because on the PC next to me this works ~X( :(((((

[johntday]

sure?!? it cannot. excpet: you have a global variable "head" which is used as the head of the linked list and set by the addFirst() call. BUT that would be very ugly.

[johntday]

extremly ugly and not maintainable. (like calling a "child" variable "parent"; or building a linked list with "last" instead of "next" pointers)

[Johnny Mopp]

I never said it was pretty. I wouldn't do things this way. But it answers the OPs question.