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

---

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.

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?

Quote:

---

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 esi

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.

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
}

---

Quote:

---

Originally Posted by Noir

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.

Shorter code isn't the same as better code. ;)

Quote:

---

Originally Posted by Noir

Shorter code isn't the same as better code. ;)

---

True enough.