#include <iostream>
#include <cstring>

using std::cout;
using std::endl;

class Node {

    int data;
    Node* next;

public:

    Node() { };
    void SetData(int aData) { data = aData; };
    void SetNext(Node* aNext) { next = aNext; };
    int Data() { return data; };
    Node* Next() { return next; };
};

class List {

    Node *head;

public:

    List() : head(NULL) { };
    void Print();
    void Append(int data);
    void Delete(int data);
};

void List::Append(int data) {

    // Create a new node
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->SetNext(NULL);

    // Create a temp pointer
    Node *tmp = head;

    if ( tmp ) {
        if ( tmp->Data() > newNode->Data() ) {
          newNode->SetNext(tmp);
          head = newNode;
        }
        else {
          // Nodes already present in the list
          // Parse to end of list anytime the next data has lower value
          while ( tmp->Next() && tmp->Next()->Data() <= newNode->Data() ) {
              tmp = tmp->Next();
          }

          // Point the lower value node to the new node
          Node* _next = tmp->Next();
          tmp->SetNext(newNode);
          newNode->SetNext(_next);
      }
    }
    else {
        // First node in the list
        head = newNode;
    }
}

void List::Print() {

    // Temp pointer
    Node *tmp = head;

    // No nodes
    if ( !tmp ) {
        cout << "EMPTY" << endl;
        return;
    }

    // One node in the list
    if ( !tmp->Next() ) {
        cout << tmp->Data();
        cout << " --> ";
        cout << "NULL" << endl;
    }
    else {
        // Parse and print the list
        do {
            cout << tmp->Data();
            cout << " --> ";
            tmp = tmp->Next();
        }
        while ( tmp );

        cout << "NULL" << endl;
    }
}

int main() {
    List l;
    l.Append(15);
    l.Append(40);
    l.Append(7);
    l.Print();
    return 0;
}