Thread: Sorted link list

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

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.