473,320 Members | 1,867 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

linked list implementation

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

Nov 14 '05 #1
8 1671

fa*****@servihoo.com wrote:
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

Nov 14 '05 #2
fa*****@servihoo.com wrote:
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
Nov 14 '05 #3
fa*****@servihoo.com wrote:
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 */
}

Nov 14 '05 #4
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.

Nov 14 '05 #5
fa*****@servihoo.com wrote:


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.)
Nov 14 '05 #6
Richard Bos wrote:
fa*****@servihoo.com wrote:
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?


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

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #7
fa*****@servihoo.com wrote:
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.

Nov 14 '05 #8
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

Nov 14 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: George M Jempty | last post by:
Is there a good linked list implementation in the public domain? Or that someone on this group has already written that they'd like to put in the public domain, right here on this newsgroup? I've...
5
by: Darryl B | last post by:
I can not get anywhere on this project I'm tryin to do. I'm not expecting any major help with this but any would be appreciated. The assignment is attached. The problem I'm having is trying to set...
12
by: Eugen J. Sobchenko | last post by:
Hi! I'm writing function which swaps two arbitrary elements of double-linked list. References to the next element of list must be unique or NULL (even during swap procedure), the same condition...
13
by: XXXXXX.working.in.my.blood | last post by:
hi all, i need help with linked lists... the problem is this, "reverse the contents of a singly linked list without using a temporary node"... solution with code will be appreciated...
4
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event...
6
by: Fazana | last post by:
I was doing one of the question but my program was not working properly. Can anyone help me with it pliz........ Here is the question for the program Question. Part 1. Add the function...
51
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort...
9
by: william | last post by:
When implementing Linked list, stack, or trees, we always use pointers to 'link' the nodes. And every node is always defined as: struct node { type data; //data this node contains ... node *...
8
by: Jeff Bown | last post by:
Consider implementing a (doubly) linked list. The simplest strategy is to provide functions item_t add_item(item_t predecessor); void delete_item(item_t item); where add_item allocates memory...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.