Sorted Linked List Problem

i was looking over my program again, and i found out that it lets you insert more than 2 numbers on specific situations. Lets say you insert a 1, and then a 12. you can then insert numbers lower than a 12 in there and they will go in, but if you insert a 13, it will overwrite the 12, and then there will only be 2 numbers again. Another thing is, i dont think the transversal is checking throuhg the entire linked list, it only compares it with the first node in the list, and i dont get how to compare it to all the nodes in the list.

to email me, email me at [email protected]

and heres a link to my C++ program

http://sourcepost.sytes.net/source/s...source_id=1661

the while loop in the insert function is on line 00160: youll know what im talking about when you see the page.

By your description you want to sort the opposite way that your code is trying to. Start by finding the last node that was less than the new node, then insert after it.

Code:

---

while ( cur != NULL )
{
  cur = cur->next;
  if ( newPtr->item >= cur->item ) {
    whisker = cur->next;
    cur->next = newNode;
    newNode->next = whisker;
    break; // No need to continue traversing, so bail
  }
}

---

The whisker variable performs the the opposite function of your prev variable, it feels ahead instead of holding a position behind.

-Prelude

Code:

---

while(cur!=NULL && newPtr->item>cur->item) {       
        prev = cur;
        cur = cur->next;
       
        newPtr->next = cur;
        prev->next = newPtr;   
}

---

You don't really want to do this, you want

Code:

---

while(cur!=NULL && newPtr->item>cur->item) {       
        prev = cur;
        cur = cur->next;
}

---

And now insert, right past prev
Suppose that you have an array such as 3 4 6 7 8

case 1: now suppose that you want to insert 5.
prev points to item link with 4 and cur points to the link with 7.
We want to set prev->next to newPtr and newPtr->next to cur.

case 2: Now suppose we want to insert 2. prev points to NULL and curr points to the link with 3. We therefore want to change head so that it points to newPtr and newPtr->next so that it points to the old head which is curr.

case 3: Now suppose that we want to insert 10. We have prev points to the link with 8 and curr to NULL so what we want to do is set prev->next to newPtr and newPtr->next to NULL as curr = NULL this cases code is the same as case 3 and so we just have to handle case 1 (when prev != NULL) and case 2 (when prev == NULL).