C++ Add to linked list in sorted order

Question

Hi I have a linked list using structs. Right now I got it to add every element at the end. However I'd like to add each element in sorted order based on the ID. The struct has two elements: string name, and long ID.

node* temp = new node;
temp->name = nameRead;
temp->id = idRead;
//check if first item, if so add as head
if(head == NULL)
{
 head = temp;
}
else
{
 node* temp2 = head;
 while(temp2->next != NULL)
 {
 temp2 = temp2->next;
 }
 temp2->next = temp;
}

• James McNellis: Do you have any thoughts as to how you might tackle this problem? If you draw out a linked list on a piece of paper, can you walk through the steps that you would have to take to insert new nodes in the correct places? What have you tried and where are you stuck? The more you can explain about what you've tried, the better we can help you to understand how to solve this problem.
• Karl Knechtel: This is for an assignment of some sort, right? You do know that C++ has a linked list and several other containers built into the standard library, yes?

Answer 1

node* temp = new node;
temp->name = nameRead;
temp->id = idRead;
node* temp2 = head;
node** temp3 = &head;
while(temp2 != null && temp2->id < temp->id)
{
 temp3 = &temp2->next;
 temp2 = temp2->next;
}
*temp3 = temp;
temp->next = temp2;

EDIT: Explanation: The 'temp3' pointer points to where 'temp' would need to go. Initialize temp2 to head, and keep looping until we reach the end of the list, or until temp2's id is>= than temp's id. In each iteration of the loop, advance both temp3 and temp2.

At the end of the loop, 'temp3' will hold the address of the pointer where temp should be. So assign *temp3 to point to temp, and assign temp->next to point to temp2 (which at this point would either be null, or would point to the item that has larger id than temp->id).

• Shezan Baig: @James McNellis I have added an explanation. would appreciate the non-downvote if it makes sense to you. thanks
• musiphil: IMO, names like temp, temp2 and so on are not any more descriptive but only longer and harder to type than simple names like i, j, etc. or p, q, etc.
• Floyd: very elegant indeed!
• Arnis Juraga: Dosn't c++ requires NULL instead of null? Otherwise - great and short solution!

Answer 2

Taken from my student notebook:

void addSorted(node * head, int id){
 node* newNode = new node;
 newNode->number = n;
 newNode->next = NULL;
 if(head == NULL || head->number >= id ){
 newNode->next = head;
 head = newNode;
 return;
 }else if(head->next != NULL && head->next->id >= id){
 node * nextNode = head->next;
 newNode->next = nextNode;
 head->next = newNode;
 return;
 }else{
 node * left;
 node * right = head;
 while(right != NULL && right->next->id <= id){
 left = right;
 right = right->next;
 }
 left->next=newNode;
 newNode->next = right;
 }
 }

• JacobSiegel: newNode->next = id; doesn't make sense.

Answer 3

Most of the modification to the code is pretty trivial -- just add a comparison based on the ID so you only walk through the list until you get to a node with an ID larger then the new one you need to insert (or reach the end of the list).

This is where things get slightly tricky: before you "realize" you've reached the right spot in the list, you've already gone one node too far (and in a singly linked list, there's no way to go back). The trick to fix that is pretty simple: allocate a new (empty) node and insert it after the too-large node you found. Copy that too-large node's contents into the new one you just inserted, and then copy the data for the new node into the spot it just vacated.

I should add, however, that all of this is mostly a moot point. If you want a sorted collection of items, a linked list is usually a really lousy choice. Unless you're doing something like homework where you have no choice but to do whatever brain-dead crap you've been assigned, look up std::set [Edit: or std::multiset, if duplicates are allowed -- or possibly std::map or std::multimap, if you want to be able to find a node based on an ID] and forget about implementing it yourself.