Geek Answers Handbook

C ++ Add to a linked list in sorted form

Hi, I have a linked list using structs. Now I got it to add each item to the end. However, I would like to add each item in sorted order based on id. The structure has two elements: a string name and a long identifier.

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;
}
+5
source share
3 answers
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 indicates where "temp" will have to go. Initialize temp2 by head and continue the loop until we reach the end of the list, or until temp2 id> = than temp id. At each iteration of the loop, advance both temp3 and temp2. A.

"temp3" , temp. * temp3 temp temp- > temp2 ( , id, temp- > id).

+12

:

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

- , , node , , , ( ).

: "", , node ( ). : () node node, . node , , node , .

, , . , . - , , , , std::set [Edit: or std::multiset, - , , std::map std::multimap, node ] .

+1

More articles:


All Articles