Thread: Sorted Linked List Problem

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    18

    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.

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

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with linked list and shared memory
    By Sirfabius in forum C Programming
    Replies: 10
    Last Post: 11-10-2008, 04:45 PM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  3. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  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