linked list implementation

[farhanb]

hello,

I am writing a simple linked list implementation. When I use function
insert1 I must allocate to head in my main to get it to work otherwise
list stays empty but when I use function insert2 there is no need to
allocate to head this is the correct way.

why does this happen? why do we need to have a pointer to a pointer to
head in the insert function for this to work?

thank you

/******************************************************************/
int insert1(int n,NODE *head)
{
NODE *temp,*newnode;
newnode =(NODE*)malloc(sizeof(NODE));
if(newnode == NULL)
{
printf("\ncould not allocate node !!!");
return;
}
newnode->x = n;
newnode->next = NULL;
temp = head;
if(isEmpty(head))
{ head = newnode;
printf("\nallocating to head!");
return; }
else
{ while(temp->next!=NULL && temp!=NULL)
temp = temp->next;
temp->next = newnode;
return newnode->x; }
}

this requires the following in main
NODE *head;
head = (NODE*)malloc(sizeof(NODE));
insert1(4,head);


/**********************************************************************/

int insert2(int n,NODE **head)
{
NODE *temp,*newnode;
newnode =(NODE*)malloc(sizeof(NODE));
if(newnode == NULL)
{
printf("\ncould not allocate node !!!");
return;
}
newnode->x = n;
newnode->next = NULL;
temp = *head;
if(isEmpty(*head))
{ *head = newnode;
printf("\nallocating to head!");
return; }
else
{ while(temp->next!=NULL && temp!=NULL)
temp = temp->next;
temp->next = newnode;
return newnode->x; }
}

this requires the following in main
NODE *head;
head = NULL;
insert(4,&head);

 

[Chris Williams]

hello,

I am writing a simple linked list implementation. When I use function
insert1 I must allocate to head in my main to get it to work otherwise
list stays empty but when I use function insert2 there is no need to
allocate to head this is the correct way.

why does this happen? why do we need to have a pointer to a pointer to
head in the insert function for this to work?

thank you

/******************************************************************/
int insert1(int n,NODE *head)
{
NODE *temp,*newnode;
newnode =(NODE*)malloc(sizeof(NODE));
[clip]

if(isEmpty(head))
{ head = newnode;
printf("\nallocating to head!");
return; }
[clip]

int insert2(int n,NODE **head)
{
NODE *temp,*newnode;
newnode =(NODE*)malloc(sizeof(NODE));
[clip]

if(isEmpty(*head))
{ *head = newnode;
printf("\nallocating to head!");
return; }

Think of the following code:

void foo(int x) { //local x == 0
x = 10; //local x == 10
} //local x ceases existing

int main(void) {
int x = 0;
foo(x);

printf("%i", x);
}

What will be printed, 0 or 10?

void foo(NODE* x) { //local x == NULL
x = 10; //local x == 10
} //local x ceases to exist

int main(void) {
NODE* x = NULL;
foo(x);

printf("%i", (int)x);
}

So what you have to do is make sure that the local version of head
isn't just a copy of the true head, but instead is a copy of the
_location_ of the real head so that you can effect it.

* I would also note that your insert functions are supposed to return
int, yet you aren't returning anything. If your compiler isn't
erroring, you might want a better one.

-Chris

 

[Richard Bos]

I am writing a simple linked list implementation. When I use function
insert1 I must allocate to head in my main to get it to work otherwise
list stays empty but when I use function insert2 there is no need to
allocate to head this is the correct way.

why does this happen? why do we need to have a pointer to a pointer to
head in the insert function for this to work?

Does <http://www.eskimo.com/~scs/C-faq/q4.8.html> help?

Richard

 

[Al Bowers]

hello,

I am writing a simple linked list implementation. When I use function
insert1 I must allocate to head in my main to get it to work otherwise
list stays empty but when I use function insert2 there is no need to
allocate to head this is the correct way.

why does this happen? why do we need to have a pointer to a pointer to
head in the insert function for this to work?

thank you

/******************************************************************/
int insert1(int n,NODE *head)
{
NODE *temp,*newnode;
newnode =(NODE*)malloc(sizeof(NODE));
if(newnode == NULL)
{
printf("\ncould not allocate node !!!");
return;
}
newnode->x = n;
newnode->next = NULL;
temp = head;
if(isEmpty(head))
{ head = newnode;
printf("\nallocating to head!");
return; }
else
{ while(temp->next!=NULL && temp!=NULL)
temp = temp->next;
temp->next = newnode;
return newnode->x; }
}

this requires the following in main
NODE *head;
head = (NODE*)malloc(sizeof(NODE));
insert1(4,head);


/**********************************************************************/

int insert2(int n,NODE **head)
{
NODE *temp,*newnode;
newnode =(NODE*)malloc(sizeof(NODE));
if(newnode == NULL)
{
printf("\ncould not allocate node !!!");
return;
}
newnode->x = n;
newnode->next = NULL;
temp = *head;
if(isEmpty(*head))
{ *head = newnode;
printf("\nallocating to head!");
return; }
else
{ while(temp->next!=NULL && temp!=NULL)
temp = temp->next;
temp->next = newnode;
return newnode->x; }
}

this requires the following in main
NODE *head;
head = NULL;
insert(4,&head);

Yes, the prototype you describe with function insert2 is the way to do
it. However, the
function definition is flawed. First, you are returning a value from the
function. Make it
a meaningful one that can signal the success or failure of the insert.
Also, as you seek
the tail of the list your code has a flaw in which an attempt to
dereference a NULL value
may occur. See a corrected solution below.

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

typedef struct NODE
{
int x;
struct NODE *next;
} NODE;

int Insert2NODE(int n,NODE **head); /* Insert at tail */
int Insert1NODE(int n,NODE **head); /* Insert at head */
void PrintNODE(const NODE *p); /* Print the list */
void FreeNODE(NODE **p); /* Free the list */

int main(void)
{
NODE *head = NULL;

puts("Inserting at tail of list");
Insert2NODE(22,&head);
Insert2NODE(33,&head);
Insert2NODE(44,&head);
PrintNODE(head);
FreeNODE(&head);

puts("\nInserting at head of list");
Insert1NODE(22,&head);
Insert1NODE(33,&head);
Insert1NODE(44,&head);
PrintNODE(head);
FreeNODE(&head);
return 0;
}

int Insert2NODE(int n,NODE **head)
{ /* Insert new node at tail of list */
NODE **temp,*newnode;
newnode =malloc(sizeof *newnode);
if(newnode != NULL)
{
newnode->x = n;
newnode->next = NULL;
/* Seek end of linked list */
for(temp = head;*temp;temp = &(*temp)->next) ;
*temp = newnode;
return 1; /* Success */
}
return 0; /* Failure */
}

void PrintNODE(const NODE *p)
{
for( ;p; p = p->next)
printf("x = %d\n",p->x);
return;
}

void FreeNODE(NODE **p)
{
NODE *tmp;

for( ; *p; *p = tmp)
{
tmp = (*p)->next;
free(*p);
}
return;
}

int Insert1NODE(int n,NODE **head)
{ /* Place new node at head of linked list */
NODE *newnode;

newnode =malloc(sizeof *newnode);
if(newnode != NULL)
{
newnode->x = n;
newnode->next = *head;
*head = newnode;
return 1; /* Success */
}
return 0; /* Failure */
}

 

[farhanb]

Thank you very much gentlemen you have been of immense help. However, I
still have two queries.

1) I can see the point Chris is making that insert1 modifies a local
variable, however is that not a problem solved by a single pointer as
in if we do

/****************************************************************/
void foo1(int *x) { //local x == 0
x = 10; //local x == 10

} //local x ceases existing

int main(void) {
int *x = 0;
printf("before foo x = %i",*x);

foo(x);

printf("\nafter %i", x);

}
/********************************************************************/

this will print
before foo x = 0;
after 10;

so it works with single pointer reference the question is why then
should i do
/*****************************************************************88/
void foo2(int **x) { //local x == 0
**x = 10; //local x == 10

} //local x ceases existing

int main(void) {
int *x;
*x = 0;
printf("before foo x = %i",*x);

foo(&x);

printf("\nafter %i", *x);

}

prints
before foo x= 0
after 10
/*****************************************************************/
in this foo case foo1 matches insert1 while foo2 matches insert2. In
the case of foo the results are the same in the case of insert they are
not why?

2) enlighten me if you will sir on the meaning of
for(temp = head;*temp;temp = &(*temp)->next) ;
and "flaw in which an attempt to dereference a NULL value may occur".
what is the flaw where is it located and what can i do to fix it.

thank you very much.

 

[infobahn]

void foo1(int *x) { //local x == 0
x = 10; //local x == 10

Since x is a pointer, assigning an integer value to it is a diagnosable
error.

} //local x ceases existing

int main(void) {
int *x = 0;

Equivalent to int *x = NULL;

printf("before foo x = %i",*x);

Undefined behaviour. x doesn't currently point to an int object,
so dereferencing it is incorrect.

this will print
before foo x = 0;
after 10;

Actually, it could print "bananas". The behaviour is undefined.

(Similar problems with second code fragment.)

 

[CBFalconer]

Does <http://www.eskimo.com/~scs/C-faq/q4.8.html> help?

However he doesn't really need that. The following technique works
to insert items at the head of a list. The list can easily be
reversed later if desired.

struct node {
struct node *next;
whatever datum;
}

struct node *insert(struct node *root, whatever data)
{
struct node *new;

if (!(new = malloc(sizeof(*new)))) {
/* memory exhaustion error handling */
new = root; /* avoid losing existing list */
}
else {
/* assign data to new->datum */
/* may involve strcpy etc. */
new->next = root;
}
return new;
}

and the usage will be somewhere as:

struct node *root = NULL;

....
root = insert(root, newdata);

 

[Al Bowers]

Thank you very much gentlemen you have been of immense help. However, I
still have two queries.

In regrads to querie 2:

2) enlighten me if you will sir on the meaning of
for(temp = head;*temp;temp = &(*temp)->next) ;
and "flaw in which an attempt to dereference a NULL value may occur".
what is the flaw where is it located and what can i do to fix it.

The definition as posted:

int insert2(int n,NODE **head)
{
NODE *temp,*newnode;
newnode =(NODE*)malloc(sizeof(NODE));
if(newnode == NULL)
{
printf("\ncould not allocate node !!!");
return;
}
newnode->x = n;
newnode->next = NULL;
temp = *head;
if(isEmpty(*head))
{ *head = newnode;
printf("\nallocating to head!");
return; }
else
{ while(temp->next!=NULL && temp!=NULL)
temp = temp->next;
temp->next = newnode;
return newnode->x; }
}

Assuming that function isEmpty will identify a condition where *head
is NULL
then it appears that the else clause will work in reaching the end of
the list.
So, I misled you on the dereference of a NULL value in the function
definition.
However, you will need to correct the returns and make it more meaningful.

The loop:

for(temp = head;*temp;temp = &(*temp)->next) ;
where temp is type NODE **
is another way of seeking the end of the loop.

 

[ByteSurfer]

What is the difference by using *head, where we just put on pointer to
the head pointer rather than what you have been implemention, Putting
**head

What differnce did that make and what is the use .. as in your code.

int Insert2NODE(int n,NODE **head);

Thank you.

Regards,
Billy