Linked-list's different insertions, help

D

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?
 
I

Irrwahn Grausewitz

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);
Click to expand...

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;
Click to expand...
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.
Click to expand...
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);
Click to expand...
You allocated space to hold a pointer to struct node.
if(temp == NULL)
printf("MEM ERROR\n");
Click to expand...
You want to bail out here, not only print an error message.
temp = *p;
Click to expand...
You dropped your reference to the memory you just allocated!
temp->data = data;
Click to expand...
You successfully invoked UB here.
temp = temp->next; And again.
temp->next = NULL;
Click to expand...
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;
}
}
Click to expand...
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;
Click to expand...
You need only one pointer; drop q.
unsigned int data;
Click to expand...

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);
Click to expand...

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");
}
Click to expand...

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?
Click to expand...
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?
Click to expand...
See above.

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

Regards

Irrwahn
 
B

Barry Schwarz

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

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;
Click to expand...

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;
Click to expand...

Since p->next is NULL, p is also.
}
free(&p);
Click to expand...

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);
Click to expand...

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
Click to expand...

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);
Click to expand...

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;
Click to expand...

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;
Click to expand...

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;
Click to expand...

You have just stepped on some unknown part of memory that temp happens
to point to. More undefined behavior.
return temp;
Click to expand...

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;
Click to expand...

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.
Click to expand...

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?
Click to expand...

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?
Click to expand...

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>>
 
D

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?
 
I

Irrwahn Grausewitz

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;
Click to expand...

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;
Click to expand...

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;
Click to expand...

You don't need q;
unsigned int data;
for(data = 0;data<10;data++)
{
q=insert(data,&p);
Click to expand...

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");
Click to expand...

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:
Click to expand...
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.
Click to expand...

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.
Click to expand...

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?
Click to expand...

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
Click to expand...

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?
Click to expand...

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
 
D

dam_fool_2003

Barry Schwarz said:
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.


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.
Click to expand...

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);


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.
Click to expand...

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().
 
I

Irrwahn Grausewitz

Would you mind explaining a little bit more?
Click to expand...

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.
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().
Click to expand...

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Infinite loop problem 1
Queue in C 25
Adding adressing of IPv6 to program 1
Stack using doubly linked list 1
double linked list 4
linked list 19
Amazon Interview Question on Doubly Linked List, Plz help 1
Queue in C 0

Members online

No members online now.
Total: 32 (members: 0, guests: 32)
Robots: 221

Forum statistics

Threads
473,755
Messages
2,569,534
Members
45,008
Latest member
Rahul737

Latest Threads

Top