Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > linked lists

Reply
Thread Tools

linked lists

 
 
shellcode@adelphia.net
Guest
Posts: n/a
 
      02-21-2004
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----------
 
Reply With Quote
 
 
 
 
Arthur J. O'Dwyer
Guest
Posts: n/a
 
      02-21-2004

On Sat, 21 Feb 2004 http://www.velocityreviews.com/forums/(E-Mail Removed) 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
 
Reply With Quote
 
 
 
 
shellcode@adelphia.net
Guest
Posts: n/a
 
      02-21-2004
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.
 
Reply With Quote
 
Arthur J. O'Dwyer
Guest
Posts: n/a
 
      02-21-2004

On Sat, 21 Feb 2004 (E-Mail Removed) 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
 
Reply With Quote
 
Darrell Grainger
Guest
Posts: n/a
 
      02-21-2004
On Sat, 21 Feb 2004 (E-Mail Removed) 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 (E-Mail Removed)
 
Reply With Quote
 
Darrell Grainger
Guest
Posts: n/a
 
      02-21-2004
On Sat, 21 Feb 2004 (E-Mail Removed) 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 (E-Mail Removed)
 
Reply With Quote
 
David Resnick
Guest
Posts: n/a
 
      02-21-2004
(E-Mail Removed) wrote in message news:<(E-Mail Removed)> ...
> 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
 
Reply With Quote
 
David Rubin
Guest
Posts: n/a
 
      02-21-2004
(E-Mail Removed) 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."

 
Reply With Quote
 
David Rubin
Guest
Posts: n/a
 
      02-21-2004
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."

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      02-21-2004
"Arthur J. O'Dwyer" wrote:
> On Sat, 21 Feb 2004 (E-Mail Removed) 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 ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
List of lists of lists of lists... =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==?= Python 5 05-15-2006 11:47 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments