468,771 Members | 1,922 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,771 developers. It's quick & easy.

Linked List

13
I'm messing around with linked lists and so far I was able to do a little something. However, I want to improve this code so I would like for any help.

First, I want improve the function insertFirst() so that it tests if memory allocation worked.

Second, I want improve main() so that it tests if insertFirst() returns NULL. If it does, main() should write out an error message and terminate any loop.

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stddef.h>
  3. #include <stdlib.h>
  4. struct NODE
  5. {
  6. struct NODE *link;
  7. int value;
  8. };
  9. typedef struct NODE Node;
  10. Node *insertFirst( Node **head, int val )
  11. {
  12. Node *node = (Node *)malloc( sizeof( Node ) );
  13. node->value = val;
  14. node->link = *head;
  15. *head = node;
  16. return node;
  17. }
  18. void traverse( Node *p )
  19. {
  20. while ( p != NULL )
  21. {
  22. printf("%d ", p->value );
  23. p = p->link;
  24. }
  25. }
  26. void freeList( Node *p )
  27. {
  28. Node *temp;
  29. while ( p != NULL )
  30. {
  31. temp = p;
  32. p = p->link;
  33. free( temp );
  34. }
  35. }
  36. int main()
  37. {
  38. Node *head = NULL;
  39. int j;
  40. for ( j=0; j<13; j++ )
  41. insertFirst( &head, j );
  42. traverse( head );
  43. freeList( head );
  44. return 1;
  45. }
Nov 3 '06 #1
8 3343
sicarie
4,677 Expert Mod 4TB
I'm messing around with linked lists and so far I was able to do a little something. However, I want to improve this code so I would like for any help.

First, I want improve the function insertFirst() so that it tests if memory allocation worked.

Second, I want improve main() so that it tests if insertFirst() returns NULL. If it does, main() should write out an error message and terminate any loop.

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stddef.h>
  3. #include <stdlib.h>
  4. struct NODE
  5. {
  6. struct NODE *link;
  7. int value;
  8. };
  9. typedef struct NODE Node;
  10. Node *insertFirst( Node **head, int val )
  11. {
  12. Node *node = (Node *)malloc( sizeof( Node ) );
  13. node->value = val;
  14. node->link = *head;
  15. *head = node;
  16. return node;
  17. }
  18. void traverse( Node *p )
  19. {
  20. while ( p != NULL )
  21. {
  22. printf("%d ", p->value );
  23. p = p->link;
  24. }
  25. }
  26. void freeList( Node *p )
  27. {
  28. Node *temp;
  29. while ( p != NULL )
  30. {
  31. temp = p;
  32. p = p->link;
  33. free( temp );
  34. }
  35. }
  36. int main()
  37. {
  38. Node *head = NULL;
  39. int j;
  40. for ( j=0; j<13; j++ )
  41. insertFirst( &head, j );
  42. traverse( head );
  43. freeList( head );
  44. return 1;
  45. }
DeFault-

Are you set in C, and not C++? You could do those things very easily in C++, but if you need C, you can always just put the insertFirst() inside the condition of an 'if' statement, and a break in the body:

Expand|Select|Wrap|Line Numbers
  1. if ( (insertFirst(&head, j) ) {
  2.    break;
  3. }
  4.  
Though the infamous story of the crashing PBX that caused an almost nationwide phone outage comes to mind - and you might (if you don't want to do anything else) consider 'return 0;' instead of 'break;'

As for 'malloc' this link http://www.opengroup.org/onlinepubs/009695399/functions/malloc.html says that errno is set if malloc fails (or you get a null pointer, which is easy to check for). So you would need to include <errno.h> but then it's as easy as

Expand|Select|Wrap|Line Numbers
  1. if ( (*node == NULL) || (errno != 0) ) {
  2.    printf("Malloc failed!\n");
  3. }
  4.  
PS - you can look more in to that here: http://publib.boulder.ibm.com/infocenter/iadthelp/v6r0/index.jsp?topic=/com.ibm.etools.iseries.pgmgd.doc/cpprog416.htm
They suggest setting errno immediately before any tests and then resetting it immediately after you check.
Nov 4 '06 #2
DeFault
13
-Sicarie

Thanks I'll give that a try.

I was also thinking about adding a function called insertLast() I haven't tried yet it but what do you think of this.

Expand|Select|Wrap|Line Numbers
  1. Node* insertLast ( Node **head, int val)
  2. {
  3.  
  4. Node *last;
  5. Node *temp;
  6.  
  7. if (*head != NULL)
  8.  
  9.    last = (Node *)malloc( sizeof( Node ));
  10.    last->value = val;
  11.  
  12.    last->link=temp; 
  13.    last=temp;
  14.  
  15. }
You think that will get the job then.
Nov 4 '06 #3
sicarie
4,677 Expert Mod 4TB
DeFault-

If you're eventually going for the full functionality I would recommend creating a head and tail node that carry sentinel values to identify them, so that doing such insertions are easier.

As for inserting to the tail, it seems that you pass it a node and a value, however the 'last' node is only set to temp, not joined to any nodes in the list (such as the 'head' or any nodes after it). But it's possible that I have been staring at my screen for too long today and I'm just not seeing it - I've been known to do that ;)

If you were to add a 'previous' pointer to the nodes as well, then you could set the tail nodes pretty easily, and create iterators to go through the list backwards as well, it's all a matter of how you want to implement it (how big you want them to be, how much you want to do with them, etc...).
Nov 5 '06 #4
DeFault
13
Is this any better?

Expand|Select|Wrap|Line Numbers
  1. Node* insertLast ( Node **head, int val)
  2. {
  3.  
  4. Node *current;
  5. Node *previous;
  6. Node *last;
  7.  
  8.  
  9. current = (Node *)malloc(sizeof(Node));
  10.  
  11. if (current != NULL)
  12.  
  13.    previous = current;
  14.    current = current->link;
  15.  
  16.    last = (Node *)malloc( sizeof( Node ));
  17.    last->value = val;
  18.  
  19.    last->link=current; 
  20.    previous->link = last;
  21.  
  22. }
Nov 6 '06 #5
sicarie
4,677 Expert Mod 4TB
Better? I think you covered 'better' when you decided to program your own linked list set to better understand the workings of the language.

The only thing I can see (with a quick glance - I will take a better look at it later, so ignore me if I'm wrong), is that you pass this **head, but then don't do anything with it. What is being passed to insertLast()? Are you passing it the current 'last' node, and the value you want it to hold? I think the only thing you're missing is something tying it to the rest of the list, something along the lines of:

Expand|Select|Wrap|Line Numbers
  1. head->next = current;
  2. current->previous = head;
  3. current->next = 
  4. /* and here is where you need to decide what you are going to do, 
  5. *  if it is going to be a sentinal 'end' node, or if you're going to tie it
  6. *  back around to the first node, etc...
  7. */
  8.  
Does that make sense, or am I on something and just missed where you did that?
Nov 6 '06 #6
DeFault
13
Better? I think you covered 'better' when you decided to program your own linked list set to better understand the workings of the language.

The only thing I can see (with a quick glance - I will take a better look at it later, so ignore me if I'm wrong), is that you pass this **head, but then don't do anything with it. What is being passed to insertLast()? Are you passing it the current 'last' node, and the value you want it to hold? I think the only thing you're missing is something tying it to the rest of the list, something along the lines of:

Expand|Select|Wrap|Line Numbers
  1. head->next = current;
  2. current->previous = head;
  3. current->next = 
  4. /* and here is where you need to decide what you are going to do, 
  5. *  if it is going to be a sentinal 'end' node, or if you're going to tie it
  6. *  back around to the first node, etc...
  7. */
  8.  
Does that make sense, or am I on something and just missed where you did that?
To answer your question about what is being passed to insertLast() that is basically inserting a node containing val at the end of a linked list.

For the code you wrote I would have a sentinal 'end' node so could you so me how it would be then by your code.
Nov 8 '06 #7
sicarie
4,677 Expert Mod 4TB
To answer your question about what is being passed to insertLast() that is basically inserting a node containing val at the end of a linked list.

For the code you wrote I would have a sentinal 'end' node so could you so me how it would be then by your code.
Hang on, I'm gonna run it and look into it - I was just spot reading that, I could be totally missing something. It's just weird to me that you are passing a node and a value - not just one or the other (a node to just insert, or a value from which insertLast will create a node to add onto the list), but I probably am missing something, I'm not feeling too well today.
Nov 8 '06 #8
DeFault
13
This is a silly question but when I ask how to improve insertFirst() and the code you wrote I would have to put that in insertFirst() right? The same goes to the malloc part I would have to put that in main right?
Nov 10 '06 #9

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

11 posts views Thread by C++fan | last post: by
5 posts views Thread by Dream Catcher | last post: by
6 posts views Thread by Steve Lambert | last post: by
12 posts views Thread by Eugen J. Sobchenko | last post: by
12 posts views Thread by joshd | last post: by
51 posts views Thread by Joerg Schoen | last post: by
reply views Thread by Atos | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.