Sorted link list

Hello,

Following is my code for link list which positions the node depending uppon the data value at run time. Though, I know that conceptually binary tree is better solution for such scenario, can anybody suggest me optimization on following code?

Code:

# include <stdio.h>
# include <malloc.h>

void sort_append(struct node **,int);
void display(struct node *);

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

main(void)
{
	int i;
	struct node *pHead;

	pHead = NULL;

	printf("Enter the numbers:\n");
	scanf("%d",&i);
	while (i)
	{
		sort_append(&pHead,i);
		scanf("%d",&i);
	}
	display(pHead);
                return 0;
}

// Inserts, appends or prepends depending upon its value.
void sort_append(struct node **ppHead,int i)
{
	struct node *new_node;

	new_node = (struct node*)malloc(sizeof(node));
	new_node->data = i;
	// First time when not even single node is generated
	if ( *ppHead == NULL )
	{
		new_node->next = NULL;
		*ppHead = new_node;
	}
	// When data is smaller than head
	else if ((*ppHead)->data > i)
	{
		new_node->next = *ppHead;
		*ppHead = new_node;
	}
	// new data is larger than head value or tal value
	else 
	{
		struct node *current, *forward;

		current = *ppHead;
		forward = (*ppHead)->next;
		while ( forward )
		{
			if ( (current->data < i) && (forward->data > i) )
			{	
				current->next = new_node;
				new_node->next = forward;
				return;
			}
			current = current->next;
			forward = forward->next;
		}
		// Make it as tail.
		current->next = new_node;
		new_node->next = NULL;
	}
}

// Displays entire link list
void display(struct node *walk)
{
	printf("\nLink list is:\n");
	while (walk)
	{
		printf("%d\n",walk->data);
		walk = walk->next;
	}
}

Here's an optimization for you, use a double linked list instead of a single. It's way way way easier for insertion and removal.

Quzah.

># include <malloc.h>
You spelled stdlib.h wrong.

>main(void)
Implicit int is no longer valid C. You're safe until C99 compilers start to make a presence, but even in C89 it's considered good style to be explicit.

>scanf("%d",&i);
Always check the return value of an input function.

>scanf("%d",&i);
Users never type what you want.

>new_node = (struct node*)malloc(sizeof(node));
The cast dutifully hides the fact that you misspelled stdlib.h, remove it since C blesses an implicit conversion to and from void *. sizeof(node) is a little funky, did you declare that variable for that sole purpose? A much better way is:

Code:

new_node = malloc ( sizeof *new_node );

sizeof doesn't evaluate its operand, so dereferencing a pointer results in the type pointed to without the nasty side effect of all hell breaking loose.

>new_node->data = i;
malloc does fail occasionally, I've seen it.

Your insertion algorithm is fine after a cursory glance. The only way to make it better is to use a data structure better suited for maintaining sorted order.

If told to program using this way only then what will be the optimization?

I am really looking at somebody will give some hints on optmizing 'else' part of sort_append function.

>If told to program using this way only then what will be the optimization?
Algorithms can be optimized only so much. If you really want something fast, get another algorithm. If you have no choice then live with what you have, because no amount of micro-optimization will be much of an improvement. And you'll also end up obscuring the code in the process.

Code:

void insert( Node **l, Node *n )
{
    if( *l == NULL )
    {
        *l = n; /* Because some people require everything done for them. */
    }
    else
    if( n->value < (*l)->value )
    {
        n->next = *l;
        (*l)->prev = n;
        *l = n;
    }
    else
    {
        Node *p = *l;
        while( p->next && p->value < n->value ) p = p->next;
        if( p->next )
        {
            p->next->prev = n;
            n->next = p->next;
            p->next = n;
            n->prev = p;
        }
        else
        {
            p->next = n;
            n->prev = p;
        }
    }
}

That looks about right. But then, I never use single linked lists, because they're
annoyingly painful for insertion and deletion. It may not be more "optimized", but
I like it better.

[edit]It helps if you actually move through the list...[/edit]

Quzah.

>while( p->next && p->value < n->value );
Missing something quzah?

>#

include <malloc.h>
You spelled stdlib.h wrong.

Do you mean mallo function is declared in stdlib.h?

>new_node->data = i;
malloc does fail occasionally, I've seen it.

Say for exapmple, I have mallocs at 5 different places, then everytime I check the return value of malloc, I need to exit if it is bad and I do not like multiple returns to single function.
Can you enlighten us telling how to balance these two aspects?


And lastly, is there anything wrong replacing malloc with calloc? I found it useful in your article related to binary tree search on the same site.

if( n->value < (*l)->value

)

And also my *l will be zero first time.

Originally Posted by Prelude

>while( p->next && p->value < n->value );
Missing something quzah?

AHaha. Yeah I suppose I should increment p some place.

Originally Posted by Roaring_Tiger

)

And also my *l will be zero first time.

You wanted a different else, not a different if.

Quzah.

>Do you mean mallo function is declared in stdlib.h?
Yes. malloc.h isn't a standard header.

>Can you enlighten us telling how to balance these two aspects?
Um...get over it? Forcing a single point of exit can result in a complex mess, especially if you have multiple unrelated chances for failure. If you can manage single entry/single exit without making the code worse then by all means, but make it easy to follow. Clarity comes first, idealism can wait its turn.

>And lastly, is there anything wrong replacing malloc with calloc?
Not at all, as long as you don't expect anything except integral values to be properly initialized to 0. For pointers, structures, and floating-point, all bits zero does not necessarily mean a zero value. In other words:

Code:

char **names = calloc ( 5, sizeof *names );

does not necessarily give you five null pointers.

>scanf("%d",&i);
Users never type what you want.

How do I check whether user has typed number only? Is there any standard function?

Please let me know..

RT

read it as a string and then parse it