Sorted link list

This is a discussion on Sorted link list within the C Programming forums, part of the General Programming Boards category; Hello, Following is my code for link list which positions the node depending uppon the data value at run time. ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    175

    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;
    	}
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    ># 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.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    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.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Last edited by quzah; 09-05-2004 at 07:25 PM.
    Hope is the first step on the road to disappointment.

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >while( p->next && p->value < n->value );
    Missing something quzah?
    My best code is written with the delete key.

  8. #8
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    >#
    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.

  9. #9
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    if( n->value < (*l)->value
    )

    And also my *l will be zero first time.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Prelude
    >while( p->next && p->value < n->value );
    Missing something quzah?
    AHaha. Yeah I suppose I should increment p some place.

    Quote Originally Posted by Roaring_Tiger
    )

    And also my *l will be zero first time.
    You wanted a different else, not a different if.

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  12. #12
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    >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

  13. #13
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    read it as a string and then parse it

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  2. Link List Insert prob
    By Bebs in forum C Programming
    Replies: 8
    Last Post: 12-03-2008, 09:28 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21