Thread: Sorting by int (low to high) in linked list

Hello, I need to sort the following by ID as I enter them into a linked list by while loop. So far I can build through the list, but I'm not sure how to sort by ID as they are entered:


Albert 1000 55.5 150
Babs 3000 60 110
Freida 1150 71 175.5
Big_Al 2000 77 244
Tiny 1550 44 77

Code:

    nodeType *first, *newNode, *last;
    
    first = NULL;
    last = NULL;
    
    while (inFile)
    {
        newNode = new nodeType; //01x
        inFile >> newNode->info.firstname;
        inFile >> newNode->info.id;
        inFile >> newNode->info.height;
        inFile >> newNode->info.weight;
        newNode->link = NULL;
        
        if (first == NULL) //first case init
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            last->link = newNode;
            last = newNode;
        }
        
}

Thanks for the help!

Well basically, you walk the list to find the place to insert the item.

Code:

prev = NULL, curr = head;
while ( curr && curr->info.id > newNode->info.id ) {
  prev = curr;
  curr = curr->next;
}

You then have 3 cases
- before the start
- somewhere in the middle
- after the end.