Simple C Linked List

[Tim]

I can't seem to figure out why this very simple linked list wont
build..

I mean, there is no intelligence, just add to end.

Anyway, please let me know if something i can do will make head (the
root pointer) not be null.

/* LINKED LIST DEFINITIONS */
typedef struct a_fnode {
struct a_packet* data;
int chksum;
struct a_fnode* next;
}fnode,*fnodePTR;
/** ADD NODE TO LIST **/
void addNode (fnodePTR root, fnodePTR node){
fnodePTR temp = root;

int node_counter = 0;

if (root == NULL)
{
printf("HEAD IS NULL: ADDING\n");
root = node;
}
else
{
while (temp != NULL) {
if(DEBUG1)
printf("%d ",node_counter);
temp = temp->next;
}
temp = node;
}
if(DEBUG1)
printf("\nAdding Node %d\n",node->data->seq);
}

/** ALLOCATE NODE **/

fnodePTR allocateNode(packet* data) {
fnodePTR temp ;
/* Allocate memory for our node */
temp = (fnodePTR)malloc(sizeof(fnode));
/* Put in our data */
temp->data = data ;

/*temp->chksum = makeChecksum(data);*/
/* Ground the link pointer */
temp->next = NULL ;
/* Return the allocated node */
return temp ;

}
main {

fnodePTR head = NULL;
fnodePTR tempPtr = NULL;
fnodePTR myNode = NULL;

...

do
{

if( (myNode = allocateNode(myPacket)) == NULL )
printf("couldn't create node\n");
addNode(head, myNode);

} while (some file reading condition

if (head == NULL )
{
if(DEBUG1)
printf("head is null\n");
EOL = 1;
/*no more data left*/
break;
}

}
that last if statement in main, is ALWAYS true. I feel the allocation
of all structs and data is working, because I can extract data all the
way up to point after i "add" to the list, as you can see in the debug
statement in addNode();

thanks a lot for your help

[Arthur J. O'Dwyer]

On Mon, 11 Apr 2005, Tim wrote:

I can't seem to figure out why this very simple linked list wont
build..
(Side remark: Note that the verb "to build" has a different connotation
in most computing circles than the one you're apparently intending. This
code will "build" in the sense that it will compile; it just won't work.)
I mean, there is no intelligence, just add to end.

Anyway, please let me know if something i can do will make head (the
root pointer) not be null.
Huh? Have you tried 'root = foo;', where 'foo' is any non-null pointer?

[Typography fixed throughout; PLEASE PLEASE PLEASE don't use hard tabs
on Usenet!]
/* LINKED LIST DEFINITIONS */
typedef struct a_fnode {
struct a_packet* data;
int chksum;
struct a_fnode* next;
} fnode, *fnodePTR;
/** ADD NODE TO LIST **/
void addNode(fnodePTR root, fnodePTR node)
{
fnodePTR temp = root;
Here is your first problem. Where is 'temp' used? Not at this scope,
that's for sure! It's only way down inside another level of nested
braces that you use it. So it should be declared there.
int node_counter = 0;
Ditto. In fact, since 'node_counter' is /never/ modified, you could
just as well remove it and use '0' everywhere it's mentioned. This
probably indicates a bug, though not an important or interesting one.
if (root == NULL)
{
printf("HEAD IS NULL: ADDING\n");
root = node;
}
else
{
while (temp != NULL) {
if (DEBUG1)
printf("%d ",node_counter);
temp = temp->next;
}
This loop shows that you haven't learned what a 'for' loop is yet.
In C, 'for' loops contain an initializer, a condition, and an increment.
They don't have to involve integers, or "counting up or down." So we
can rewrite this Pascal-looking loop idiomatically in C as

fnodePTR temp;
for (temp=root; temp != NULL; temp = temp->next)
{
if (DEBUG1)
printf("0 ");
}

(Notice that I've pulled the definition of 'temp' down to where it's
used, and replaced the constant 'node_counter' with its value, 0.)
temp = node;
This line is actually the problem you're concerned about. Think
about what it's doing: It's taking the variable 'temp', which you
defined right in this function, and it's assigning a value to it.
But you don't care about the value of 'temp' --- 'temp' is going to
disappear as soon as you leave the function! What you want to do is
change the values associated with the linked list 'root'! So you
need to get a pointer to the last entry in 'root', and set that
entry's 'next' pointer to point to 'node', like this:

for (temp=root; temp->next != NULL; temp = temp->next)
;
temp->next = node;

So that will fix one of your problems. But what if 'root' is a null
pointer itself? Then you have no list entries to modify! So this
points out a design flaw in your code: You need to pass the linked
list by reference. [UNTESTED CODE]

void addNode(fnodePTR *root, fnodePTR node)
{
if (*root == NULL) {
*root = node;
}
else {
fnodePTR temp;
for (temp = *root; temp->next != NULL; temp = temp->next)
;
temp->next = node;
}
}

And there you go.
/** ALLOCATE NODE **/

fnodePTR allocateNode(packet *data)
{
fnodePTR temp ;

/* Allocate memory for our node */
temp = (fnodePTR)malloc(sizeof(fnode));
This is horrible. Write instead

temp = malloc(sizeof *temp);

You will be glad you did, because this way you don't have to worry about
two different type names in the expression --- you don't write any type
names!
main {
Okay, maybe it /won't/ build. :( The way to define a function in C
is with a type, an identifier, and some parentheses with optional
parameter declarations, like this:

int main(void) {

or (though I don't like this one as much) like this:

int main() {
fnodePTR head = NULL;
fnodePTR tempPtr = NULL;
fnodePTR myNode = NULL;

...

do
{

if( (myNode = allocateNode(myPacket)) == NULL )
printf("couldn't create node\n");
addNode(head, myNode);
This is actually safe, but it looks dubious and kind of silly when
you really analyze what's going on. Why are you bothering to insert
'myNode' into the list even when you know it's a null pointer? Sure,
inserting a null pointer doesn't do anything to the list, but it
wastes time and might be deadly if you decide to put back in the line

/* debugging output */
printf("%d\n", node->data->foo);

(Dereferencing a null pointer invokes undefined behavior.)
} while (some file reading condition

if (head == NULL )
{
if(DEBUG1)
printf("head is null\n");
EOL = 1;
/*no more data left*/
break;
}

}

Don't forget to 'free' all your allocated memory when you're done using
it.

HTH,
-Arthur

PS: "The Elements of Programming Style."