Linked List

[DeFault]

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.

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
struct NODE
{
struct NODE *link;
int value;
};
typedef struct NODE Node;
Node *insertFirst( Node **head, int val )
{
Node *node = (Node *)malloc( sizeof( Node ) );
node->value = val;
node->link = *head;
*head = node;
return node;
}
void traverse( Node *p )
{
while ( p != NULL )
{
printf("%d ", p->value );
p = p->link;
}
}
void freeList( Node *p )
{
Node *temp;
while ( p != NULL )
{
temp = p;
p = p->link;
free( temp );
}
}
int main()
{
Node *head = NULL;
int j;
for ( j=0; j<13; j++ )
insertFirst( &head, j );
traverse( head );
freeList( head );
return 1;
}

[sicarie]

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.

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
struct NODE
{
struct NODE *link;
int value;
};
typedef struct NODE Node;
Node *insertFirst( Node **head, int val )
{
Node *node = (Node *)malloc( sizeof( Node ) );
node->value = val;
node->link = *head;
*head = node;
return node;
}
void traverse( Node *p )
{
while ( p != NULL )
{
printf("%d ", p->value );
p = p->link;
}
}
void freeList( Node *p )
{
Node *temp;
while ( p != NULL )
{
temp = p;
p = p->link;
free( temp );
}
}
int main()
{
Node *head = NULL;
int j;
for ( j=0; j<13; j++ )
insertFirst( &head, j );
traverse( head );
freeList( head );
return 1;
}

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:

if ( (insertFirst(&head, j) ) {
   break;
}
 

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

if ( (*node == NULL) || (errno != 0) ) {
   printf("Malloc failed!\n");
}
 

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.

[DeFault]

-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.

Node* insertLast ( Node **head, int val)
{
 
Node *last;
Node *temp;
 
if (*head != NULL)
 
   last = (Node *)malloc( sizeof( Node ));
   last->value = val;
 
   last->link=temp; 
   last=temp;
 
}

You think that will get the job then.

[sicarie]

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...).

[DeFault]

Is this any better?

Node* insertLast ( Node **head, int val)
{
 
Node *current;
Node *previous;
Node *last;
 
 
current = (Node *)malloc(sizeof(Node));
 
if (current != NULL)
 
   previous = current;
   current = current->link;
 
   last = (Node *)malloc( sizeof( Node ));
   last->value = val;
 
   last->link=current; 
   previous->link = last;
 
}

[sicarie]

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:

head->next = current;
current->previous = head;
current->next = 
/* and here is where you need to decide what you are going to do, 
*  if it is going to be a sentinal 'end' node, or if you're going to tie it
*  back around to the first node, etc...
*/
 

Does that make sense, or am I on something and just missed where you did that?

[DeFault]

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:

head->next = current;
current->previous = head;
current->next = 
/* and here is where you need to decide what you are going to do, 
*  if it is going to be a sentinal 'end' node, or if you're going to tie it
*  back around to the first node, etc...
*/
 

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.

[sicarie]

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.

[DeFault]

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?