#include <iostream>
using namespace std;

// Node class to represent each element in the list
class ListNode {
public:
    int data;
    ListNode* next;

    // Constructor
    ListNode(int val) : data(val), next(nullptr) {}
};

// List class that manages the linked list
class List {
private:
    ListNode* head;

public:
    // Constructor
    List() : head(nullptr) {}

    // Destructor to free memory
    ~List() {
        while (head != nullptr) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // Add a new node at the end of the list
    void append(int value) {
        ListNode* newNode = new ListNode(value);
        if (head == nullptr) {
            head = newNode;
        } else {
            ListNode* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }
    // Insert a node so that the list is sorted in ascending order
    void insert(int value) {
        ListNode* newNode = new ListNode(value);

        // Case 1: List is empty or insert before head
        if (head == nullptr || value <= head->data) {
            newNode->next = head;
            head = newNode;
        } else {
            // Case 2: Find the correct position to insert
            ListNode* current = head;
            while (current->next != nullptr && current->next->data < value) {
                current = current->next;
            }

            // Insert node after current
            newNode->next = current->next;
            current->next = newNode;
        }
    }
    // Print the list
    void print() const {
        ListNode* current = head;
        while (current != nullptr) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "NULL" << endl;
    }
};

// Main program
int main() {
    List myList;

    // Add some elements to the list
    myList.insert(30);
    myList.insert(20);
    myList.insert(10);
    myList.insert(25);

    // Print the list
    cout << "Linked List: ";
    myList.print();

    return 0;
}