linked lists

[shellcode]

i wrote this liked lists test program. it works, but im just wonderding
if i did everything relating to NULL and memory allocation correctly or
if i missed out on some important checks. thank's

--------single.c---------
#include <stdlib.h>
#include <stdio.h>

struct node {
int data;
struct node* next;
};

struct node* addtotail(struct node* head, int num);
void printlist(struct node* head);

int main()
{
struct node* head;
int i;
head = malloc(sizeof(struct node));
for(i = 0; i <= 100; i++)
{
addtotail(head, i);
}
printlist(head);
return 0;
}

struct node* addtotail(struct node* head, int num)
{
struct node* current;
struct node* newnode;
newnode = malloc(sizeof(struct node));
newnode->data = num;
newnode->next = NULL;
current = head;
while (current->next != NULL)
current=current->next;
current->next = newnode;
return current->next;
}

void printlist(struct node* head)
{
struct node* current;
current = head;
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}
----------eof----------

[Arthur J. O'Dwyer]

On Sat, 21 Feb 2004 sh*******@adelphia.net wrote:

[i] wrote this [linked] lists test program. [i]t works, but [I'm] just
[wondering] if [i] did everything relating to NULL and memory allocation
correctly or if [i] missed out on some important checks. [Thanks.]
(Amusingly, the OP hit every possible miscapitalization and
"mis-apostrophization," but got the adverb "correctly" correct. :)
--------single.c---------
#include <stdlib.h>
#include <stdio.h>

struct node {
int data;
struct node* next;
};

struct node* addtotail(struct node* head, int num);
void printlist(struct node* head);

int main()
{
struct node* head;
int i;
head = malloc(sizeof(struct node));
The common practice in these parts is

head = malloc(sizeof *head);

This way, you don't even have to care what type 'head' is, and
that really pays off when you start dealing with complicated
types. (It's also an extra "typ[eo] check" when you have, let's say,
'struct node' and 'struct mode' with different sizes!)

If 'head' is NULL at this point, you'll crash and burn when you
call 'addtotail' inside the loop. Insert some lines like these:

if (head == NULL) {
puts("Out of memory!");
exit(EXIT_FAILURE);
}
for(i = 0; i <= 100; i++)
This is an *extremely* weird loop condition! In C, loops almost
invariably go

for (i = 0; i < number_of_iterations; ++i) ...

To loop while "i <= 100" is a sign of a programmer who hasn't been
absorbing common practice. ;) Did you really mean to make a list of
the numbers from 0 to 100, or did you mean 0 to 99?
{
addtotail(head, i);
}
printlist(head);
return 0;
Whoops! You've just created a memory leak! You malloc'ed a
whole lot of memory... where does it get free'd? Answer: it
doesn't. You need to free it yourself. So, *before* you return
from 'main', you need to write

while (head != NULL) {
void *tmp = head;
head = head->next;
free(tmp);
}

and only *then* can you

return 0; }

struct node* addtotail(struct node* head, int num)
{
struct node* current;
struct node* newnode;
newnode = malloc(sizeof(struct node));
Ditto on the malloc style and the error-checking. Think: what's
a good reasonable thing to do if 'malloc' returns NULL here?
Hint: you're returning a value from this function that just gets
discarded at the moment. Maybe you could use that value to indicate
success or failure!...
newnode->data = num;
newnode->next = NULL;
current = head;
while (current->next != NULL)
Blam! Another crash and burn! What's 'head->next' the first
time you call this function? That's right... you don't know, because
you never assigned anything to it. So you have no idea what this
comparison is going to do. Maybe it'll "work," maybe it won't, maybe
demons will fly out of your nose.
Solution: remember to initialize the fields of '*head' before
starting the loop in 'main'.
current=current->next;
current->next = newnode;
return current->next;
I.e., return newnode. Whatever floats your boat.
}

void printlist(struct node* head)
{
struct node* current;
current = head;
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}
----------eof----------

Now for the fun part. A good C programmer might do this whole
program much more idiomatically like this:

--------single-updated.c---------

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

struct node {
int data;
struct node *next;
};

int addtotail(struct node **p, int data);
void printlist(struct node *head);

int main(void)
{
struct node *head = NULL;
int i;

for (i=0; i < 101; ++i) {
if (addtotail(&head, i) != 0) {
puts("Out of memory!");
goto free_all;
}
}

printlist(head);

free_all:
while (head != NULL) {
void *tmp = head;
head = head->next;
free(tmp);
}

return 0;
}

int addtotail(struct node **p, int data)
{
struct node *q = malloc(sizeof *q);
if (q == NULL)
return -1;

q->data = data;
q->next = NULL;

/* Find the tail of the list */
for (; (*p) != NULL; p = &(*p)->next)
continue;
*p = q;
return 0;
}

void printlist(struct node *p)
{
for (; p != NULL; p = p->next)
printf("%d\n", p->data);
}

----------eof----------
And a Real Programmer (TM) would do it like this:

--------single-final.c---------

#include <stdio.h>

int main(void)
{
int i;
for (i=0; i < 101; ++i)
printf("%d\n", i);
return 0;
}

----------eof----------

;-)

HTH,
-Arthur

[shellcode]

thank you for that helpful and informative reply. there is one thing
that I do not understand.

int addtotail(struct node **p, int data);

why do you have a pointer to a pointer to a node p??

thank's again.

[Arthur J. O'Dwyer]

On Sat, 21 Feb 2004 sh*******@adelphia.net wrote:

thank you for that helpful and informative reply. there is one thing
that I do not understand.

int addtotail(struct node **p, int data);

why do you have a pointer to a pointer to a node p??

Because I need to modify the original pointer 'head'. So I
must pass the address of 'head' to 'addtotail'. So I must type
'addtotail' so that it correctly takes an address of a 'struct
node *', which is a 'struct node **'. Q.E.D. :)

Alternatively, I could have passed in the old value of 'head'
and returned the new value of 'head', but then I'd need extra
bookkeeping to handle the NULL case correctly -- and that would
have been quite a pain.

So you understood the part marked /* Find the end of the list */
(or whatever) just fine; you just needed help with pointers? ;-D

-Arthur

[Darrell Grainger]

On Sat, 21 Feb 2004 sh*******@adelphia.net wrote:

i wrote this liked lists test program. it works, but im just wonderding
if i did everything relating to NULL and memory allocation correctly or
if i missed out on some important checks. thank's

--------single.c---------
#include <stdlib.h>
#include <stdio.h>

struct node {
int data;
struct node* next;
};

struct node* addtotail(struct node* head, int num);
void printlist(struct node* head);

int main()
{
struct node* head;
int i;
head = malloc(sizeof(struct node));
Never assume that malloc() will be successful. Check that it did not
return NULL. If it returns NULL and you use head your program will most
likely crash (or worse corrupt the system).

Additionally, why are you allocating a block of memory for head to point
to? I believe I know why but you might want to put a comment explaining
your design decision.
for(i = 0; i <= 100; i++)
{
addtotail(head, i);
You realize that head is a pointer to a structure *BUT* you have not
initialized anything within the structure. You need to explicitly
initialize head->next before you use it.
}
printlist(head);
return 0;
}
The rest of main() is pretty straight forward. I see nothing wrong with
what is here. I don't however see any calls to free(). For every call to
malloc() there should be a call to free().

It could be argued that your program is a work in progress and once you
are sure the addtotail() is working you are going to add a
deletefromtail() or deletefromhead() function. Right now you have a memory
leak.
struct node* addtotail(struct node* head, int num)
{
struct node* current;
struct node* newnode;
newnode = malloc(sizeof(struct node));
Again, you are failing to confirm that malloc() was successful.
Additionally, I would put a safe guard in this program. I would check that
head does not equal NULL. If head equals NULL then your while loop
expression will be dereferencing a NULL pointer. Most likely resulting in
a crash.
newnode->data = num;
newnode->next = NULL;
current = head;
while (current->next != NULL)
current=current->next;
Since current equals head, using current->next is the same as using
head->next on the first iteration of this loop. You never initialized
head->next back in main(). This is undefined behaviour. You are probably
just lucky that your compiler initialized it to NULL for you. You should
not rely on that.
current->next = newnode;
return current->next;
}
The addtotail() function assumes something about the linked list. You
should add a comment indicating what that assumption is.
void printlist(struct node* head)
{
struct node* current;
current = head;
Again, check that head does not equal NULL. You know that it will not
because you wrote main() but what if you turn this into a library for
someone else to use? They might call printlist() with a NULL pointer
(accidents happen).
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}

This function also makes the same assumption that addtotail() is making.
Put a comment indicating what that assumption is.

The majority of the code here is very good. It is plain and simple. It is
easy to maintain and fairly straight forward. You are just missing some of
the details I noted above.

--
Send e-mail to: darrell at cs dot toronto dot edu
Don't send e-mail to vi************@whitehouse.gov

[Darrell Grainger]

On Sat, 21 Feb 2004 sh*******@adelphia.net wrote:

thank you for that helpful and informative reply. there is one thing
that I do not understand.

int addtotail(struct node **p, int data);

why do you have a pointer to a pointer to a node p??

Arthur J. O'Dwyer needs a pointer to a pointer to a node p because he is
being more memory efficient. You can create a linked list with a dummy
node at the beginning. You never use the dummy node at the beginning of
the list (things like add, delete, print will skip over the first node).
By having a dummy node at the beginning you avoid needing to change the
head pointer but you waste the memory for that dummy node.

By using a pointer to a pointer to a node p you can alter the head
pointer. This eliminates the need for a dummy node at the beginning. If
you are just learning C, your code is fine. You can be a little waste
full. As you get better and learn more you will start looking at ways to
be more efficient. My philosophy for students is get it right first, get
it efficient second. Mind you, you want to start making small little code
snippets that are right. Once you start working on intermediate to large
projects you need to have your code right and efficient; trying to create
a large project that is right then later going back and making it
efficient can often be the wrong choice (too time consuming and risky).

--
Send e-mail to: darrell at cs dot toronto dot edu
Don't send e-mail to vi************@whitehouse.gov

[David Resnick]

sh*******@adelphia.net wrote in message news:<sl*********************@ph33r.shellcode.net> ...

i wrote this liked lists test program. it works, but im just wonderding
if i did everything relating to NULL and memory allocation correctly or
if i missed out on some important checks. thank's

--------single.c---------
#include <stdlib.h>
#include <stdio.h>

struct node {
int data;
struct node* next;
};

struct node* addtotail(struct node* head, int num);
void printlist(struct node* head);

int main()
{
struct node* head;
int i;
head = malloc(sizeof(struct node));
for(i = 0; i <= 100; i++)
{
addtotail(head, i);
}
printlist(head);
return 0;
}

struct node* addtotail(struct node* head, int num)
{
struct node* current;
struct node* newnode;
newnode = malloc(sizeof(struct node));
newnode->data = num;
newnode->next = NULL;
current = head;
while (current->next != NULL)
current=current->next;
current->next = newnode;
return current->next;
}

void printlist(struct node* head)
{
struct node* current;
current = head;
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}
----------eof----------

A few comments:
1) You never initialize the next pointer of the original
head before it is used. Nor do you initialize its data,
but I guess that is OK because you don't print the
data of head. Do you mean head to hold no data?
Anyway, you MUST initialize its next pointer for this
code to be valid. I assume you tried the code and it worked,
that was just that you were "lucky" that the system
returned zero'd out memory from the malloc (not guaranteed)
and that corresponded to NULL on your system (also not guaranteed).

2) malloc can return NULL if memory allocation fails.
You should always check for this

3) Iterating through the list each time may not be your best choice
given how you are constructing it. You return the tail, perhaps
just adding new nodes to the tail would be better?

4) Instead of malloc(sizeof(struct node));, consider
malloc(sizeof *head), it is more maintainable in that if you
change the type of head you won't have a mismatch.

-David

[David Rubin]

sh*******@adelphia.net wrote:

[snip]

void printlist(struct node* head)
{
struct node* current;
current = head;
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}

No one seems to have commented yet that this function will never print
the tail element. I'm sure you realized this when you tested your program.

/david

--
"As a scientist, Throckmorton knew that if he were ever to break wind in
the echo chamber, he would never hear the end of it."

[David Rubin]

David Resnick wrote:

[snip]

struct node* addtotail(struct node* head, int num)
{
struct node* current;
struct node* newnode;
newnode = malloc(sizeof(struct node));
newnode->data = num;
newnode->next = NULL;
current = head;
while (current->next != NULL)
current=current->next;
current->next = newnode;
return current->next;
}

[snip] 3) Iterating through the list each time may not be your best choice
given how you are constructing it. You return the tail, perhaps
just adding new nodes to the tail would be better?

Along these same lines, it is typical to insert nodes at the head of the
list since this is much easier to do; you don't have to search for the
tail. Likewise, the extra memory used to keep track of the tail is
probably always worth the time you save searching for it:

typedef struct Node Node;
struct Node {
int data
Node *next;
};

typedef struct List List;
struct List {
Node *head;
Node *tail;
};

Now, there is no need for pointer-to-pointers or linear searches.

/david

--
"As a scientist, Throckmorton knew that if he were ever to break wind in
the echo chamber, he would never hear the end of it."

[CBFalconer]

"Arthur J. O'Dwyer" wrote:

On Sat, 21 Feb 2004 sh*******@adelphia.net wrote:

thank you for that helpful and informative reply. there is one
thing that I do not understand.

int addtotail(struct node **p, int data);

why do you have a pointer to a pointer to a node p??

Because I need to modify the original pointer 'head'. So I
must pass the address of 'head' to 'addtotail'. So I must type
'addtotail' so that it correctly takes an address of a 'struct
node *', which is a 'struct node **'. Q.E.D. :)

Alternatively, I could have passed in the old value of 'head'
and returned the new value of 'head', but then I'd need extra
bookkeeping to handle the NULL case correctly -- and that would
have been quite a pain.

So you understood the part marked /* Find the end of the list */
(or whatever) just fine; you just needed help with pointers? ;-D

I consider the following (untested) about the simplest list
creator possible. It always adds to the head, but a very simple
process can reverse the complete list whenever desired.

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

#define LEN 10

struct node {
struct node *next;
int data;
};

/* ----------------- */

/* returns NULL for out of memory error */
struct node *addtolist(struct node *head, int value)
{
struct node *newnode;

if ((newnode = malloc(sizeof *newnode))) {
newnode->next = head;
newnode->data = value;
}
return newnode;
} /* addtolist */

/* ----------------- */

void showlist(struct list *head)
{
while (head) {
printf("%d\n", head->data);
head = head->next;
}
} /* showlist */

/* ----------------- */

int main(void)
{
struct node *list, *temp;
int i;

list = NULL;
for (i = 0; i < LEN; i++) {
temp = addtolist(list, rand());
if (temp) list = temp;
else {
/* any error reporting goes here */
break;
}
}
showlist(list);
return 0;
} /* untested */

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Lewis Bowers]

David Rubin wrote:

sh*******@adelphia.net wrote:

[snip]

void printlist(struct node* head)
{
struct node* current;
current = head;
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}

No one seems to have commented yet that this function will never print
the tail element. I'm sure you realized this when you tested your program.

Take a careful look at the logic. In the loop, current is assigned
current->next. And then
the value of current->data is printed. This will skip over printing the head
data item but
will print the last(tail) data item.

[Peter Pichler]

"Lewis Bowers" <lb*******@cox.net> wrote:

David Rubin wrote:

sh*******@adelphia.net wrote:

[snip]

void printlist(struct node* head)
{
struct node* current;
current = head;
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}
No one seems to have commented yet that this function will never print
the tail element. I'm sure you realized this when you tested your

program.
Take a careful look at the logic. In the loop, current is assigned
current->next. And then
the value of current->data is printed. This will skip over printing the head data item but will print the last(tail) data item.

....and then it will happily crash ;-)

Delete the "->next" from the loop and swap the two lines inside the loop to
achieve what I believe was the desired effect. Better still, write it as a
for loop:

void printlist (struct node * current)
{
for (; current->next != NULL; current = current->next)
printf("%d\n", current->data);
}

You don't even need an extra variable. An explanation why is left as an
exercise for the reader.

Peter

[Lewis Bowers]

Peter Pichler wrote:

"Lewis Bowers" <lb*******@cox.net> wrote:

David Rubin wrote:

sh*******@adelphia.net wrote:

[snip]
> void printlist(struct node* head)
> {
> struct node* current;
> current = head;
> while (current->next != NULL)
> {
> current=current->next;
> printf("%d\n", current->data);
> }
> }

No one seems to have commented yet that this function will never print
the tail element. I'm sure you realized this when you tested your

program.

Take a careful look at the logic. In the loop, current is assigned
current->next. And then
the value of current->data is printed. This will skip over printing the

head

data item but will print the last(tail) data item.

...and then it will happily crash ;-)

Their is a flaw in the code that will cause failure, but the instrument of
death is not the
last iteration of the loop If the argument head has a value of NULL, the
function will
crash because you dereference a NULL value..

Delete the "->next" from the loop and swap the two lines inside the loop to
achieve what I believe was the desired effect. Better still, write it as a
for loop:

void printlist (struct node * current)
{
for (; current->next != NULL; current = current->next)
printf("%d\n", current->data);
}

This function suffers a similiar flaw. If the argument, current, has the value
of NULL,
you are dead meat.


You don't even need an extra variable. An explanation why is left as an
exercise for the reader.

You do not need an extra variable.
Arthor O'Dwyer has already posted a correct solution for this function's
purpose.

void printlist(struct node *p)
{
for (; p != NULL; p = p->next)
printf("%d\n", p->data);
}

[Peter Pichler]

"Lewis Bowers" <lb*******@cox.net> wrote:

Peter Pichler wrote:

Delete the "->next" from the loop and swap the two lines inside the loop to
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ achieve what I believe was the desired effect. Better still, write it as a for loop:

void printlist (struct node * current)
{
for (; current->next != NULL; current = current->next)
printf("%d\n", current->data);
}
This function suffers a similiar flaw. If the argument, current, has the

value of NULL, you are dead meat.

I should have heeded my own advice. That's what I get for cut-and-paste ;-)

[David Rubin]

Lewis Bowers wrote:

David Rubin wrote:

sh*******@adelphia.net wrote:

[snip]

void printlist(struct node* head)
{
struct node* current;
current = head;
while (current->next != NULL)
{
current=current->next;
printf("%d\n", current->data);
}
}

No one seems to have commented yet that this function will never print
the tail element. I'm sure you realized this when you tested your program.

Take a careful look at the logic. In the loop, current is assigned
current->next. And then
the value of current->data is printed. This will skip over printing the head
data item but
will print the last(tail) data item.

Err, you're right. I was considering a list without a dummy head.

FWIW, If head->next is null, as would be the case for a single-item
list, nothing will be printed.

/david

--
"As a scientist, Throckmorton knew that if he were ever to break wind in
the echo chamber, he would never hear the end of it."

[Arthur J. O'Dwyer]

On Sat, 21 Feb 2004, Peter Pichler wrote:

"Lewis Bowers" <lb*******@cox.net> wrote:

David Rubin wrote:

sh*******@adelphia.net wrote:

[snip]
> void printlist(struct node* head)
> {
> struct node* current;
> current = head;
> while (current->next != NULL)
> {
> current=current->next;
> printf("%d\n", current->data);
> }
> }

No one seems to have commented yet that this function will never
print the tail element. I'm sure you realized this when you tested
your program.
Take a careful look at the logic. In the loop, current is assigned
current->next. And then the value of current->data is printed. This
will skip over printing the head data item but will print the last
(tail) data item.

...and then it will happily crash ;-)

What made you say that? The code works perfectly -- the only
real problem in the OP's code was the missing initialization of
'head->next' to NULL inside 'main'.
Delete the "->next" from the loop and swap the two lines inside the loop to
achieve what I believe was the desired effect. Better still, write it as a
for loop:

void printlist (struct node * current)
{
for (; current->next != NULL; current = current->next)
printf("%d\n", current->data);
}

This will crash and burn, given the OP's data structure. I think
you have forgotten the code under discussion, which was a linked list
with a dummy node at the head of the list.

The "better" code I posted uses a canonical linked list with no
dummy node, and I used the canonical method of printing the data
(essentially what you wrote above, but without the
'current->next'-for-'current' typo in the loop condition.)

HTH,
-Arthur