understanding link list

[bitshadow]

I've been working on a link list implementation and I'm driving myself
crazy trying to understand something.

assuming i have a list and i have the following quasi pseudocode:

add(list *head):
if(head==NULL)
head=newnode
else
while (head)
head->data="something"
head=head->nextNode


I assumed that since head was a ptr whatever was done to in the
function would be reflected once this function terminated? is this true
or is head just a local var of a address? The reason i ask this is
because on my liist if head is null, on exit from the function head
still remains null even though i specfied it should get the new ptr.

HOWEVERRRRR....if head is not null, the program iterates through the
list and updates the list accordingly. If its only supposed to be a
copy how come the second part of the function retains the value after
the function terminates, and how come the first part doesn't. more
precisely how comes all the memory from head+1 and on is updated
seemingly by reference and head is not.

in fact if i write the follwoing:

delete(list *head):
while(head)
temp = head->next
free(head)
head=temp


on exit. everyone one of them is freed. EXCEPT head. obviously i'm not
freeing head but why? Please let me know if i've explained this
properly. i just feel like i'm going crazy trying to understand this.
thanks

 

[Morris Dovey]

bitshadow (in (e-mail address removed))
said:

| I've been working on a link list implementation and I'm driving
| myself crazy trying to understand something.
|
| assuming i have a list and i have the following quasi pseudocode:
|
| add(list *head):
| if(head==NULL)
| head=newnode
| else
| while (head)
| head->data="something"
| head=head->nextNode
|
|
| I assumed that since head was a ptr whatever was done to in the
| function would be reflected once this function terminated? is this
| true or is head just a local var of a address? The reason i ask
| this is because on my liist if head is null, on exit from the
| function head still remains null even though i specfied it should
| get the new ptr.
|
| HOWEVERRRRR....if head is not null, the program iterates through the
| list and updates the list accordingly. If its only supposed to be a
| copy how come the second part of the function retains the value
| after the function terminates, and how come the first part doesn't.
| more precisely how comes all the memory from head+1 and on is
| updated seemingly by reference and head is not.
|
| in fact if i write the follwoing:
|
| delete(list *head):
| while(head)
| temp = head->next
| free(head)
| head=temp
|
|
| on exit. everyone one of them is freed. EXCEPT head. obviously i'm
| not freeing head but why? Please let me know if i've explained this
| properly. i just feel like i'm going crazy trying to understand
| this. thanks

Your query would be much more clear if you showed your structure
definitions and an actual attempt at the C code.

I have a set of simple list manipulation functions at the link below
that may be of some help.

 

[Ben Pfaff]

assuming i have a list and i have the following quasi pseudocode:

add(list *head):
if(head==NULL)
head=newnode
else
while (head)
head->data="something"
head=head->nextNode


I assumed that since head was a ptr whatever was done to in the
function would be reflected once this function terminated? is this true
or is head just a local var of a address? The reason i ask this is
because on my liist if head is null, on exit from the function head
still remains null even though i specfied it should get the new ptr.

This part of your question, at least, is answered in the C FAQ:

4.8: I have a function which accepts, and is supposed to initialize,
a pointer:

void f(int *ip)
{
static int dummy = 5;
ip = &dummy;
}

But when I call it like this:

int *ip;
f(ip);

the pointer in the caller remains unchanged.

A: Are you sure the function initialized what you thought it did?
Remember that arguments in C are passed by value. The called
function altered only the passed copy of the pointer. You'll
either want to pass the address of the pointer (the function
will end up accepting a pointer-to-a-pointer), or have the
function return the pointer.

See also questions 4.9 and 4.11.

 

[stonemcstone]

I've been working on a link list implementation and I'm driving myself
crazy trying to understand something.

assuming i have a list and i have the following quasi pseudocode:

add(list *head):
if(head==NULL)
head=newnode
else
while (head)
head->data="something"
head=head->nextNode


I assumed that since head was a ptr whatever was done to in the
function would be reflected once this function terminated? is this true
or is head just a local var of a address? The reason i ask this is
because on my liist if head is null, on exit from the function head
still remains null even though i specfied it should get the new ptr.

HOWEVERRRRR....if head is not null, the program iterates through the
list and updates the list accordingly. If its only supposed to be a
copy how come the second part of the function retains the value after
the function terminates, and how come the first part doesn't. more
precisely how comes all the memory from head+1 and on is updated
seemingly by reference and head is not.

The trick is that the pointer is just a copy, but the thing it points
to is the original.
If you want your function to alter the original pointer, you'll have to
actually pass a copy of the address of the original pointer:

void add( list *newNode, list **head )
{
if ( *head == NULL )
*head = newNode;
else
while ( *head )
{
*head->data = "something";
*head = *head->nextNode;
}
}

And then, rather than
"add( mynode, myhead )",
you would call "add( mynode, &myhead )"

Note that here I'm just copying your pseudocode (and translating it to
C), I'm not endorsing this as being a working "add" in any linked list
sort of sense. If head is not null then it doesnt actually add
anything at all, instead it sets each node's "data" field to point to a
string literal and sets head=NULL.

in fact if i write the follwoing:

delete(list *head):
while(head)
temp = head->next
free(head)
head=temp


on exit. everyone one of them is freed. EXCEPT head. obviously i'm not
freeing head but why? Please let me know if i've explained this
properly. i just feel like i'm going crazy trying to understand this.
thanks

That shouldnt be happening, but you should post the ACTUAL code, not
pseudocode. It's impossible to diagnose syntax errors from pseudocode.

 

[Dag Viken]

I've been working on a link list implementation and I'm driving myself
crazy trying to understand something.

assuming i have a list and i have the following quasi pseudocode:

add(list *head):
if(head==NULL)
head=newnode
else
while (head)
head->data="something"
head=head->nextNode


I assumed that since head was a ptr whatever was done to in the
function would be reflected once this function terminated? is this true
or is head just a local var of a address? The reason i ask this is
because on my liist if head is null, on exit from the function head
still remains null even though i specfied it should get the new ptr.

HOWEVERRRRR....if head is not null, the program iterates through the
list and updates the list accordingly. If its only supposed to be a
copy how come the second part of the function retains the value after
the function terminates, and how come the first part doesn't. more
precisely how comes all the memory from head+1 and on is updated
seemingly by reference and head is not.

in fact if i write the follwoing:

delete(list *head):
while(head)
temp = head->next
free(head)
head=temp


on exit. everyone one of them is freed. EXCEPT head. obviously i'm not
freeing head but why? Please let me know if i've explained this
properly. i just feel like i'm going crazy trying to understand this.
thanks

It is a bit hard to know for sure without the actual sample code but it
looks like you are passing just a pointer to the list to the add and delete
functions. You need to pass the address of the list pointer in order to
update it. My test program was compiled with MSVC++ 2002 as an ANSI C
Program and runs as expected. I modified the add function to add another
node for each call.

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

typedef struct list
{
struct list *next;
char data[20];
} list;

void add(list **phead);
void delete(list **phead);
void printlist(list *head, char *title);

int main()
{
int n;
list *head = NULL;
printlist(head, "At start:");
/* Add 3 nodes */
for (n = 1; n <= 3; n++)
{
add(&head);
printlist(head, "After add:");
}
delete(&head);
printlist(head, "After delete:");
return 0;
}

void add(list **phead)
{
list *head = *phead;
list* newnode = calloc(1, sizeof(list));
if (head == NULL)
{
sprintf(newnode->data, "1: head node");
*phead = newnode; /* will update ptr outside function */
}
else
{
/* Add another node at end of list */
int n;
for (n = 1; head->next; n++)
head = head->next;
sprintf(newnode->data, "%d: another node", n + 1);
head->next = newnode;
}
}

void delete(list **phead)
{
list *temp;
list *head = *phead;
while (head)
{
temp = head->next;
free(head);
head=temp;
}
*phead = NULL; /* updates ptr */
}

void printlist(list *head, char *info)
{
printf("%s%s\n", info, head ? "" : " <empty>");
for (; head; head = head->next)
printf("%s\n", head->data);
}

/* Expected output:

At start: <empty>
After add:
1: head node
After add:
1: head node
2: another node
After add:
1: head node
2: another node
3: another node
After delete: <empty>

*/



Hope this helps.
Regards,
Dag