#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

class Node;

class List{
public:
    List();
    void setNode( int );
    bool isEmpty( void );
    void printList( void );

private:
    Node *firstPtr;
    Node *lastPtr;
};

class Node{
    friend class List;
public:
    Node( int );                                
    int getData( void );
private:
    int data;
    Node *nextPtr;
};

int main(){

    srand( time( 0 ) );

    List myList;

    for( int i = 1; i <= 25; i++ )
        myList.setNode(1+ rand() % 100 );
    

    myList.printList();
    cout<<endl;

    return(0);
}

List::List() : firstPtr( 0 ), lastPtr( 0 )
{
    
}

void List::setNode( int d ){

    Node *newPtr = new Node( d ); //new temp node

    Node *temp = firstPtr;
    Node *trailTemp = firstPtr;


    if( isEmpty() )
        firstPtr = newPtr;

    else if( newPtr->getData() > temp->getData() )
    {
            while( newPtr->getData() > temp->getData() && temp->nextPtr != 0 ){
        
                temp = temp->nextPtr;
                trailTemp->nextPtr = temp;
            }

            if( temp->nextPtr == 0 ){
                newPtr->nextPtr = temp->nextPtr;
                temp->nextPtr = newPtr;
            } else{
                newPtr->nextPtr = temp;    
                trailTemp->nextPtr = newPtr;
            }
    
    } else{
        newPtr->nextPtr = temp->nextPtr;
        firstPtr = newPtr;
    }
}

bool List::isEmpty() {

    return( firstPtr == 0 );
}

void List::printList( void ){
    
    Node *temp = firstPtr;

    temp = temp->nextPtr;

    while( temp->nextPtr != 0 ){            //traverse the list
        cout << temp->getData() << " ";    // print out at each node.
        temp = temp->nextPtr;
    }

    cout << temp->getData();
}

Node::Node( int d ) :  data( d ), nextPtr( 0 )
{

}

int Node::getData()
{
    return( data );
}