From: alelvb@inwind.it   
      
   Hello everyone,   
   I've got stuck with this problem:   
      
   I'd like to insert a node in a linked list in a sorted manner.   
   from smaller to bigger   
      
   I have a linked list that inserts nodes at the top or at the   
   bottom of the list, but I can't get it working if I try to sort the   
   inserting.   
      
   here is my code:   
      
   #include    
      
   using std::cout;   
   using std::endl;   
   using std::cerr;   
      
   class Node;   
      
   // Base class to Head and Node classes   
      
   class List_Element   
   {   
         public:   
      
             List_Element(): next(0) { }   
             ~List_Element() { }   
      
             Node * next;   
   };   
      
   class Head : public List_Element   
   {   
         public:   
      
             Head() { List_Element(); }   
             ~Head() { cout << "head deleted." << endl; }   
   };   
      
   class Node : public List_Element   
   {   
         public:   
             Node(int value): List_Element(), itsDatum(value) { }   
            ~Node() { cout << "node " << itsDatum << " deleted." << endl; }   
             int getValue() const { return itsDatum; }   
         private:   
             int itsDatum;   
   };   
      
   class Linked_List   
   {   
         public:   
             Linked_List() { head = new Head(); }   
             ~Linked_List() { delete head; }   
             void empty_list();   
              int pop();   
             void print_list();   
             void push(int);   
             void push_back(int);   
             void insert_sorted(int);   
         private:   
             Head *head;   
             int insert(Node *, Node *);   
   };   
      
   // the function main of the program   
      
   int main()   
   {   
         Linked_List * ll = new Linked_List();   
      
         ll->insert_sorted(7);   
         ll->insert_sorted(3);   
         ll->insert_sorted(-2);   
         ll->insert_sorted(1);   
         ll->insert_sorted(-9);   
         ll->insert_sorted(5);   
         ll->insert_sorted(-2);   
         ll->insert_sorted(-3);   
         ll->insert_sorted(-7);   
      
         ll->print_list();   
      
         ll->empty_list();   
      
         delete ll;   
      
         return 0;   
   }   
      
   // insert a node after another node   
      
   int Linked_List::insert(Node * new_node, Node * after_me)   
   {   
         Node *temp = 0;   
      
         temp = after_me->next;   
         after_me->next = new_node;   
         new_node->next = temp;   
      
         return 0;   
   }   
      
   void Linked_List::insert_sorted(int value)   
   {   
         Node * temp = head->next;   
      
         if(temp == 0) // if the list is empty   
         {   
             push(value); // insert the first element   
         }   
         else   
         {   
             while(temp != 0)   
             {   
                 if( value > temp->getValue() )   
                 {   
                     Node * new_node = new Node(value);   
                     insert(new_node, temp);   
                     break;   
                 }   
                 else   
                 {   
                     push(value);   
                     break;   
                 }   
                 temp = temp->next;   
             }   
         }   
   }   
      
   // insert an element to the top of the list   
      
   void Linked_List::push(int value)   
   {   
         Node * n = new Node(value);   
      
         Node * temp = head->next;   
      
         head->next = n;   
         n->next = temp;   
      
   }   
      
   // adds an element to the end of the list   
      
   void Linked_List::push_back(int value)   
   {   
         Node *temp = new Node(value);   
      
         List_Element *index = head;   
      
         while(index->next != 0)   
         {   
             index = index->next;   
         }   
         index->next = temp;   
   }   
      
   // pops an element from the top of the list   
      
   int Linked_List::pop()   
   {   
         Node * popped = head->next;   
         int to_return = popped->getValue();   
      
         head->next = popped->next;   
      
         delete popped;   
         return to_return;   
   }   
      
   // prints the list checking whether it is an empty list   
      
   void Linked_List::print_list()   
   {   
         if(head->next != 0)   
         {   
             Node *to_print = head->next; // to_print points to the first Node   
      
             while(to_print != 0)   
             {   
                 cout << to_print->getValue() << " ";   
                 to_print = to_print->next;   
             }   
             cout << endl;   
         }   
         else   
         {   
             cout << "\athe list is empty." << endl;   
         }   
   }   
      
   // delete the entire list   
      
   void Linked_List::empty_list()   
   {   
         while(head->next != 0)   
         {   
             pop();   
         }   
   }   
      
      
   --   
         [ See http://www.gotw.ca/resources/clcm.htm for info about ]   
         [ comp.lang.c++.moderated.    First time posters: Do this! ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)