Thread: sorting in linked list

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    18

    sorting in linked list

    can someone give me an idea how i will create a sorting function for the linked list.. m pasting the code for my insert function of the linked list. i just want to know the logic of how i will sort the numbers as the user enters them.
    thanks..

    Code:
    void insert (struct node**start, int value)
    {
    	if ((*start)== NULL)
    	{
    		*start= (struct node*) malloc(sizeof(struct node));
    		(*start)-> value = value;
    		(*start)->next = NULL;
    	}else
    	{
    		struct node*temp = *start;
    		while ((temp->next)!= NULL)
    		{
    			temp= temp->next;
    		}
    		temp->next = (struct node*) malloc(sizeof(struct node));
    		temp->value = value;
    		temp = temp->next;
    		temp->next=NULL;
    	}
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    If you are going to sort the items as you insert them, you just need to search for the correct spot and insert there. If none of the items in the list are less than the new item, insert the new item at the tail.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    18
    but suppose i want to insert a value between to nodes... how will i tell my pointer to go 1 step back to insert a new node between those two?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    but suppose i want to insert a value between to nodes... how will i tell my pointer to go 1 step back to insert a new node between those two?
    Maintain a pointer to the previous node. It could be done within the node, upon which you will have a doubly linked list, or it could be local to the search and insert function.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by esi View Post
    but suppose i want to insert a value between to nodes... how will i tell my pointer to go 1 step back to insert a new node between those two?
    For a doubly linked list, you use the "prev" pointer to get the previous node. If the list is singly linked, the general pattern is this:

    Code:
    node *prev, *curr;
    prev = NULL;
    curr = list;
    if(curr)
    {
        if(!found(curr))
        {
            prev = curr;
            for(curr = prev->next; curr; curr = curr->next)
            {
                if(found(curr))
                {
                    break;
                }
                prev = curr;
            }
        }
        if(curr)
        {
            /* Found it. At this point, prev points to the previous node, curr to the current node.
             * If prev is NULL, the node which was found is at the head of the list, and you may
             * have to handle that case specially.
             */
            /* Do whatever you need to do here */
        }
    }
    if(!curr)
    {
        /* Never found it. */
    }
    In this example, the found() function determines which node to stop at. The if(curr) followed by if(!curr) might seem redundant, but if you try to code it otherwise you will find that you have to duplicate the "never found it" code.

  6. #6
    Registered User Noir's Avatar
    Join Date
    Mar 2007
    Posts
    218
    Or you can have your algorithm look ahead:
    Code:
    if ( !head || value < head->value ) {
      // insert at the front
    } else {
      struct node *temp = head;
    
      while ( temp->next && value > temp->next->value ) {
        temp = temp->next;
      }
    
      // insert after temp
    }

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Noir View Post
    Or you can have your algorithm look ahead:
    Code:
    if ( !head || value < head->value ) {
      // insert at the front
    } else {
      struct node *temp = head;
    
      while ( temp->next && value > temp->next->value ) {
        temp = temp->next;
      }
    
      // insert after temp
    }
    Dangit, you make me look bad by putting your opening braces on the same line Makes my code look longer.

  8. #8
    Registered User Noir's Avatar
    Join Date
    Mar 2007
    Posts
    218
    Shorter code isn't the same as better code.

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Noir View Post
    Shorter code isn't the same as better code.
    True enough.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM