Linked lists in C

Question

void add ( struct node **q, int num )
{
    struct node *temp ;

    /* add new node */
    temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

    temp -> data = num ;
    temp -> link = *q ;
    *q = temp ;
}

This function is meant for adding a new item at the beginning of the list.

My doubt is that in most of the books the functions functions involving linked lists use pointer to the node structure rather that instance of the struct itself.

void add( struct node *q, int num )
{
    struct node temp ;

    temp.data = num ;
    temp.link = q ;
    q = &temp ;
}

Is there a reason the 1st form of the function is preferred or both methods are equally good?

The first method is preferred because the second method doesn't achieve anything. — Oliver Charlesworth, Jun 28 '14 at 08:56
The 2nd form doesn't do anything - assignment to `q` only changes what the local variable `q` points to without affecting the caller. Also, the storage of `temp` is invalid after `add` exits, so you may not retain a reference to it. — user4815162342, Jun 28 '14 at 08:57
also is recommended to not cast the return of malloc. look this http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc — sir psycho sexy, Jun 28 '14 at 09:11

haccks · Accepted Answer · 2014-06-29T12:02:14.583

2

Second method is completely wrong. It does nothing. Node is created when program enters function body and vanished on leaving the function body because it is not allocated dynamically and change to p will not be reflected to pointer passed in caller function.

edited Jun 29 '14 at 12:02

answered Jun 28 '14 at 09:01

haccks

104,019
25
176
264

BLUEPIXY · Answer 2 · 2014-06-28T11:23:13.363

The second example is simply wrong.
So you are wrong as well as an example of the question.
The following example probably work.

void add( struct node **q, int num){
    static int count = 0;
    static struct node pool[1024];

    if(count == 1024){
        fprintf(stderr, "Sold out!\n");
    } else {
        pool[count].data = num;
        pool[count].link = *q;
        *q = &pool[count];
        ++count;
    }
}

One of the reasons for using a pointer and dynamically allocated memory for the node is due to the existence period.
It is possible to use it if you create a node of survival period, such as global variables and static memory.

In addition, it can be used even in the automatic variables such as struct node temp;. It can be used when list is created inside a function and is local to it, like below :

#include <stdio.h>

struct node {
    int data;
    struct node *link;
};

void add( struct node *q, int num){
    if(num == 10){
        for( ; q ; q = q->link)
            printf("%d ", q->data);
        printf("\n");
    } else {
        struct node temp;
        temp.data = num;
        temp.link = q;
        add(&temp, num + 1);
    }
}

int main(){
    add(NULL, 0);
    return 0;
}

Linked lists in C

2 Answers2