Linked-list's different insertions, help

[dam_fool_2003]

friends,
I wanted to learn the various ways of inserting a single list. so:
Method 1:

#include<stdlib.h>
#include<stdio.h>
struct node
{
unsigned int data;
struct node *next;
};
void init(void)
{
unsigned int data;
struct node *p;
p= malloc(sizeof *p);
if(p == NULL)
exit(EXIT_FAILURE);
for(data =0;data <10;data++)
{

p->data = data;
p->next = NULL;
printf("%d\n",p->data);
p=p->next;
}
free(&p);
printf("after del =%d\n",p->data);
}

int main(void)
{
init();
return 0;

}

In this method the value is getting printed up to the last printf
statement and throws a runtime error at the end. This method looks
ugly and also wrong.

Method 2:

#include<stdio.h>
#include<stdlib.h>
struct node
{
unsigned int data;
struct node *next;
};

struct node *insert(unsigned int data,struct node **p) /*C's functions
are pass-by-value*/
{
struct node *temp;
temp = malloc(sizeof *p);
if(temp == NULL)
printf("MEM ERROR\n");
temp = *p;
temp->data = data;
temp = temp->next;
temp->next = NULL;
return temp;

}

void disp(struct node **temp) /*C's functions are pass-by-value*/
{
struct node *p;
p=*temp;
while(p->next != NULL)
{
printf("%d\n",p->data);
p=p->next;
}
}

int main(void)
{
struct node *p,*q;
unsigned int data;
p = malloc(sizeof *p);
q= malloc(sizeof *q);
for(data = 0;data<10;data++)
{
p=insert(data,&q);
if(p != NULL)
disp(&p);
else
printf("(ERROR)\n");
}
return 0;
}

In the above method I am not getting any output at all. I am sure the
mistake is with the argument passing but I am unable to sort it out.
Can any body answre the following question:

1)Is there any correct way of insertion in a ls or is it depend on the
situation?
2)Can any one tell me the error I made in the above simple programs?

[Irrwahn Grausewitz]

da***********@yahoo.com wrote:

friends,
I wanted to learn the various ways of inserting a single list. so:
Method 1:

#include<stdlib.h>
#include<stdio.h>
struct node
{
unsigned int data;
struct node *next;
};
void init(void)
{
unsigned int data;
struct node *p;
p= malloc(sizeof *p);
if(p == NULL)
exit(EXIT_FAILURE);
You want to put the memory allocation inside the loop to get this
working. for(data =0;data <10;data++)
{

p->data = data;
p->next = NULL;
printf("%d\n",p->data);
p=p->next; The value of p->next is NULL at this point, you invoke undefined
behaviour.
}
free(&p);
printf("after del =%d\n",p->data);
}

int main(void)
{
init();
return 0;

}

In this method the value is getting printed up to the last printf
statement and throws a runtime error at the end. This method looks
ugly and also wrong. Indeed. :-)

Method 2:

#include<stdio.h>
#include<stdlib.h>
struct node
{
unsigned int data;
struct node *next;
};

struct node *insert(unsigned int data,struct node **p) /*C's functions
are pass-by-value*/
{
struct node *temp;
temp = malloc(sizeof *p); You allocated space to hold a pointer to struct node.
if(temp == NULL)
printf("MEM ERROR\n"); You want to bail out here, not only print an error message.
temp = *p; You dropped your reference to the memory you just allocated! temp->data = data; You successfully invoked UB here. temp = temp->next; And again. temp->next = NULL; You successfully invoked UB here. Change this whole section to:

temp = malloc( sizeof **p );
if ( temp == NULL )
{
printf("MEM ERROR\n");
exit( EXIT_FAILURE );
}
temp->data = data;
temp->next = *p;
(*p) = temp;
return temp;
}

void disp(struct node **temp) /*C's functions are pass-by-value*/
{
struct node *p;
p=*temp;
while(p->next != NULL)
{
printf("%d\n",p->data);
p=p->next;
}
} Change this function to:

void disp( struct node *head )
{
for ( ; head != NULL; head = head->next )
printf( "%d\n", head->data );
}

int main(void)
{
struct node *p,*q; You need only one pointer; drop q.
unsigned int data;
You do the memory allocation in insert(), so drop the following two
lines (not to mention you forgot to check the return value of malloc()): p = malloc(sizeof *p);
q= malloc(sizeof *q);
Instead, initialize p to NULL:

p = NULL;
for(data = 0;data<10;data++)
{
p=insert(data,&q);
if(p != NULL)
disp(&p);
else
printf("(ERROR)\n");
}
Insert will change the value of p, so all you have to do is:

for ( data = 0; data < 10; data++ )
insert( data, &p );
disp( p );
return 0;
}

In the above method I am not getting any output at all. I am sure the
mistake is with the argument passing but I am unable to sort it out.
Can any body answre the following question:

1)Is there any correct way of insertion in a ls or is it depend on the
situation? You can insert at the beginning, at the end or at another position,
dending on what you want to do with the list. You can do it like in
the (corrected!) second example, where the insert function changes the
pointer to the first element of the list, or you can do this in the
calling funtion; it's merely a question of style and personal
preference.
2)Can any one tell me the error I made in the above simple programs?

See above.

In C sometimes things are much simpler as one might think. ;-)

Regards

Irrwahn
--
My other computer is a abacus.

[Barry Schwarz]

On 21 Sep 2003 10:05:28 -0700, da***********@yahoo.com wrote:

friends,
I wanted to learn the various ways of inserting a single list. so:
Method 1:
Unfortunately, this does not build a linked list at all. At no time
does the member next of a struct node point to any other struct node.

#include<stdlib.h>
#include<stdio.h>
struct node
{
unsigned int data;
struct node *next;
};
void init(void)
{
unsigned int data;
struct node *p;
p= malloc(sizeof *p);
if(p == NULL)
exit(EXIT_FAILURE);
for(data =0;data <10;data++)
{

p->data = data;
When data is 0, p contains the value returned by malloc. Storing into
p->data is OK.

As noted below, when data > 0, p contains NULL. Any attempt to
dereference p invokes undefined behavior. On my system, the code
failed after printing 0.
p->next = NULL;
printf("%d\n",p->data);
p=p->next;
Since p->next is NULL, p is also.
}
free(&p);
I don't believe it is ever proper to use the & operator on the
argument to free. By definition, free expects to receive a value
previously returned by malloc (or a related function). p is a defined
variable whose storage is not allocated by malloc. &p is the address
of this storage and is therefore not a malloc generated value.

What you probably want is to store the address of allocated memory in
p and later free this allocation with
free (p);
printf("after del =%d\n",p->data);
After you free p, you are not allowed to dereference it. You cannot
print the value of data after the memory has been freed because the
object no longer exists.
}

int main(void)
{
init();
return 0;

}

In this method the value is getting printed up to the last printf
statement and throws a runtime error at the end. This method looks
As noted above, it should have failed after the first printf. In any
case, you have at least three examples of undefined behavior (one
inside a loop)
Dereferencing a NULL pointer.
Passing an invalid value to free.
Dereferencing a freed pointer.

Any one of them could cause the symptoms you are seeing.
ugly and also wrong.

Method 2:

#include<stdio.h>
#include<stdlib.h>
struct node
{
unsigned int data;
struct node *next;
};

struct node *insert(unsigned int data,struct node **p) /*C's functions
are pass-by-value*/
{
struct node *temp;
temp = malloc(sizeof *p);
temp is a pointer to struct. Therefore you must allocate enough space
to hold this struct. p is a pointer to pointer to struct so *p is
simply a pointer to struct. It is guaranteed that sizeof *p is too
small. You need either sizeof **p or better sizeof *temp.
if(temp == NULL)
printf("MEM ERROR\n");
temp = *p;
You have now thrown away the value that malloc just returned. temp
now points to the struct allocated to q in main.
temp->data = data;
temp = temp->next;
That struct was never initialized in main so any attempt to evaluate
temp->next leads to undefined behavior. If you code survives this,
temp now contains an indeterminate value.
temp->next = NULL;
You have just stepped on some unknown part of memory that temp happens
to point to. More undefined behavior.
return temp;
You pass back the address of some unknown and possibly non-existent
part of memory.

}

void disp(struct node **temp) /*C's functions are pass-by-value*/
{
struct node *p;
p=*temp;
while(p->next != NULL)
{
printf("%d\n",p->data);
p=p->next;
Nowhere is the member next on any struct node ever initialized.
}
}

int main(void)
{
struct node *p,*q;
unsigned int data;
p = malloc(sizeof *p);
q= malloc(sizeof *q);
for(data = 0;data<10;data++)
{
p=insert(data,&q);
if(p != NULL)
disp(&p);
else
printf("(ERROR)\n");
}
return 0;
}

In the above method I am not getting any output at all. I am sure the
mistake is with the argument passing but I am unable to sort it out.
You have many more problems than just the arguments. Before
attempting linked lists, you need a really firm understanding of
pointers
dynamic allocation
passing/returning values to/from called functions
avoiding undefined behavior
Can any body answre the following question:

1)Is there any correct way of insertion in a ls or is it depend on the
situation?
Yes there is at least one (preferred) correct method (algorithm) to
insert items into a linked list. If you have access to Knuth's books
(in most school libraries), that is probably the definitive source.
Most programming books also discuss it since it is a very common
topic. google probably has several on-line references.

On the other hand, how you implement the algorithm may indeed depend
on the situation. That is why program development should start with
design and not with coding.
2)Can any one tell me the error I made in the above simple programs?

I have identified some. You have coding errors, logic errors, and
design errors. I recommend you put the list project on hold for a
while and study the suggested topics first.
<<Remove the del for email>>

[dam_fool_2003]

Changed code: (not fully)

#include<stdio.h>
#include<stdlib.h>
struct node
{
unsigned int data;
struct node *next;
};

struct node *insert(unsigned int data,struct node **p)
{
struct node *temp;
temp = malloc(sizeof **p);
if(temp == NULL)
{
printf("MEM ERROR\n");
exit(EXIT_FAILURE);
}
else
{

temp->data = data;
temp->next = *p;
temp->next = NULL;
*p = temp;
return *p;
}
return NULL;

}

void disp(struct node *head)
{
for(;head !=NULL;head=head->next)
printf("%d\n",head->data);

}

int main(void)
{
struct node *p=NULL,*q;
unsigned int data;
for(data = 0;data<10;data++)
{
q=insert(data,&p);
if(q != NULL)
disp(q);
else
printf("(ERROR in program)\n");
}
return 0;
}

By making the changes I have some doubts.

1)when I took off the and temp->next = NULL along with your suggested
changes in insert() function I am getting output like this:
0
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
6
5
4
3
2
1
0
7
6
5
4
3
2
1
0
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0

Is node->next = NULL is updating the current node? I coded with out
the node->next = NULL is got the above output. But when I added the
node->next=NULL (pls look the full code above) I got the answer as 0
to 9.

2)node = node->next is moving the list. I made the list traversal in
the function disp().By
avoiding the line temp=temp->next in the function insert() is that
mean that we should no move the list again?

3)What is the difference between

*p = temp;
(*p) = temp;
Since both works fine

4)In the main() I have used two node pointers p,q and assigned the
return value of function insert() to q. You have suggested that one
node pointer is enough. Is it because of optimization?
Irrwahn Grausewitz <ir*****************@freenet.de> wrote in message news:<hm********************************@4ax.com>. ..

da***********@yahoo.com wrote:

friends,
I wanted to learn the various ways of inserting a single list. so:
Method 1:

#include<stdlib.h>
#include<stdio.h>
struct node
{
unsigned int data;
struct node *next;
};
void init(void)
{
unsigned int data;
struct node *p;
p= malloc(sizeof *p);
if(p == NULL)
exit(EXIT_FAILURE);

You want to put the memory allocation inside the loop to get this
working.

for(data =0;data <10;data++)
{

p->data = data;
p->next = NULL;
printf("%d\n",p->data);
p=p->next;

The value of p->next is NULL at this point, you invoke undefined
behaviour.

}
free(&p);
printf("after del =%d\n",p->data);
}

int main(void)
{
init();
return 0;

}

In this method the value is getting printed up to the last printf
statement and throws a runtime error at the end. This method looks
ugly and also wrong.

Indeed. :-)

Method 2:

#include<stdio.h>
#include<stdlib.h>
struct node
{
unsigned int data;
struct node *next;
};

struct node *insert(unsigned int data,struct node **p) /*C's functions
are pass-by-value*/
{
struct node *temp;
temp = malloc(sizeof *p);

You allocated space to hold a pointer to struct node.

if(temp == NULL)
printf("MEM ERROR\n");

You want to bail out here, not only print an error message.

temp = *p;

You dropped your reference to the memory you just allocated!

temp->data = data;

You successfully invoked UB here.

temp = temp->next;

And again.

temp->next = NULL;

You successfully invoked UB here. Change this whole section to:

temp = malloc( sizeof **p );
if ( temp == NULL )
{
printf("MEM ERROR\n");
exit( EXIT_FAILURE );
}
temp->data = data;
temp->next = *p;
(*p) = temp;

return temp;
}

void disp(struct node **temp) /*C's functions are pass-by-value*/
{
struct node *p;
p=*temp;
while(p->next != NULL)
{
printf("%d\n",p->data);
p=p->next;
}
}

Change this function to:

void disp( struct node *head )
{
for ( ; head != NULL; head = head->next )
printf( "%d\n", head->data );
}

int main(void)
{
struct node *p,*q;

You need only one pointer; drop q.

unsigned int data;

You do the memory allocation in insert(), so drop the following two
lines (not to mention you forgot to check the return value of malloc()):

p = malloc(sizeof *p);
q= malloc(sizeof *q);

Instead, initialize p to NULL:

p = NULL;

for(data = 0;data<10;data++)
{
p=insert(data,&q);
if(p != NULL)
disp(&p);
else
printf("(ERROR)\n");
}

Insert will change the value of p, so all you have to do is:

for ( data = 0; data < 10; data++ )
insert( data, &p );
disp( p );

return 0;
}

In the above method I am not getting any output at all. I am sure the
mistake is with the argument passing but I am unable to sort it out.
Can any body answre the following question:

1)Is there any correct way of insertion in a ls or is it depend on the
situation?

You can insert at the beginning, at the end or at another position,
dending on what you want to do with the list. You can do it like in
the (corrected!) second example, where the insert function changes the
pointer to the first element of the list, or you can do this in the
calling funtion; it's merely a question of style and personal
preference.

2)Can any one tell me the error I made in the above simple programs?

See above.

In C sometimes things are much simpler as one might think. ;-)

Regards

Irrwahn

[Irrwahn Grausewitz]

da***********@yahoo.com wrote:

Changed code: (not fully)

#include<stdio.h>
#include<stdlib.h>
struct node
{
unsigned int data;
struct node *next;
};

struct node *insert(unsigned int data,struct node **p)
{
struct node *temp;
temp = malloc(sizeof **p);
if(temp == NULL)
{
printf("MEM ERROR\n");
exit(EXIT_FAILURE);
}
else
{

temp->data = data;
temp->next = *p;
temp->next = NULL;
You just broke your list: you created a new node and then failed to link
it to the rest of the list by assigning NULL to temp->next.
*p = temp;
return *p;
}
return NULL;
This return statement will never be executed.

}

void disp(struct node *head)
{
for(;head !=NULL;head=head->next)
printf("%d\n",head->data);

}

int main(void)
{
struct node *p=NULL,*q;
You don't need q;
unsigned int data;
for(data = 0;data<10;data++)
{
q=insert(data,&p);
insert(data,&p);

And, if you /really/ want to print the list you have so far after each
insert operation:

disp( p );
if(q != NULL)
disp(q);
else
printf("(ERROR in program)\n");
The else part will never get executed (insert will never return NULL).
}
return 0;
}

By making the changes I have some doubts.

1)when I took off the and temp->next = NULL along with your suggested
changes in insert() function I am getting output like this: <output SNIPPED>
Is node->next = NULL is updating the current node? I coded with out
the node->next = NULL is got the above output. But when I added the
node->next=NULL (pls look the full code above) I got the answer as 0
to 9.
Yes, but this just indicates you broke your list, as explained above;
you should get something like (newlines stripped):
0
1 0
2 1 0
3 2 1 0
....
9 8 7 6 5 4 3 2 1 0

2)node = node->next is moving the list.
No, it's traversing the list.
I made the list traversal in
the function disp().By
avoiding the line temp=temp->next in the function insert() is that
mean that we should no move the list again?
No, it means you produce no list at all, because you fail to link the
nodes together to form a list.

3)What is the difference between

*p = temp;
(*p) = temp;
Since both works fine
There is no difference.

4)In the main() I have used two node pointers p,q and assigned the
return value of function insert() to q. You have suggested that one
node pointer is enough. Is it because of optimization?

No, it's because your insert() function changes p, so you don't gain
anything by letting two pointers, p and q, point to exactely the same
object (the most recently inserted node).

<SNIP>

Below is the complete corrected program, for your convenience; the
output looks like I mentioned above, also note that there is no more
blank shortage nowadays ... ;-)
#include <stdio.h>
#include <stdlib.h>

struct node
{
unsigned int data;
struct node *next;
};

struct node *insert( unsigned int data, struct node **p )
{
struct node *temp;
temp = malloc( sizeof **p );
if ( temp == NULL )
{
printf( "MEM ERROR\n" );
exit( EXIT_FAILURE );
}

temp->data = data;
temp->next = *p;
*p = temp;
return *p;
}

void disp( struct node *head )
{
for( ; head !=NULL; head=head->next )
printf( "%d\n", head->data );
}

int main( void )
{
struct node *p = NULL;
unsigned int data;

for( data = 0; data<10; data++ )
{
insert( data, &p );
disp( p );
}
return EXIT_SUCCESS;
}

Regards

Irrwahn
--
My other computer is a abacus.

[dam_fool_2003]

Barry Schwarz <sc******@deloz.net> wrote in message news:<bk**********@216.39.134.131>...

On 21 Sep 2003 10:05:28 -0700, da***********@yahoo.com wrote:

friends,
I wanted to learn the various ways of inserting a single list. so:
Method 1:
Unfortunately, this does not build a linked list at all. At no time
does the member next of a struct node point to any other struct node.

#include<stdlib.h>
#include<stdio.h>
struct node
{
unsigned int data;
struct node *next;
};
void init(void)
{
unsigned int data;
struct node *p;
p= malloc(sizeof *p);
if(p == NULL)
exit(EXIT_FAILURE);
for(data =0;data <10;data++)
{

p->data = data;

When data is 0, p contains the value returned by malloc. Storing into
p->data is OK.

As noted below, when data > 0, p contains NULL.

Would you mind explaining a little bit more?
What you probably want is to store the address of allocated memory in
p and later free this allocation with
free (p);

printf("after del =%d\n",p->data);

After you free p, you are not allowed to dereference it. You cannot
print the value of data after the memory has been freed because the
object no longer exists.

printf cannot print the objects which has been freed by free().
Prototype of free is
void free(void *block);
We can check weather the malloc() allocated memmory to the object by
checking it's return value. Then how can we sure that the object
deallocated with free().

[Irrwahn Grausewitz]

da***********@yahoo.com wrote:

Barry Schwarz <sc******@deloz.net> wrote in message news:<bk**********@216.39.134.131>...

On 21 Sep 2003 10:05:28 -0700, da***********@yahoo.com wrote: <SNIP>

>void init(void)
>{
> unsigned int data;
> struct node *p;
> p= malloc(sizeof *p);
> if(p == NULL)
> exit(EXIT_FAILURE);
> for(data =0;data <10;data++)
> {
>
> p->data = data;
When data is 0, p contains the value returned by malloc. Storing into
p->data is OK.

As noted below, when data > 0, p contains NULL.

Would you mind explaining a little bit more?

The first time the loop body gets executed you set p->next = NULL and
then p = p->next; hence p == NULL. The second time the loop body
executes you try to assign data to NULL->data, which invokes dreaded
undefined behaviour.

What you probably want is to store the address of allocated memory in
p and later free this allocation with
free (p);

> printf("after del =%d\n",p->data);

After you free p, you are not allowed to dereference it. You cannot
print the value of data after the memory has been freed because the
object no longer exists.

printf cannot print the objects which has been freed by free().
Prototype of free is
void free(void *block);
We can check weather the malloc() allocated memmory to the object by
checking it's return value. Then how can we sure that the object
deallocated with free().

We cannot; we call free() and hopefully the implementation takes the
appropriate actions, whatever these are alike. However, we invoke
undefined behaviour if we try to access memory that has been free()'d.

In implementors we trust. 8^]

Regards

Irrwahn
--
My other computer is a abacus.

[dam_fool_2003]

thanks for all the answers