#include <iostream>
using namespace std;

struct ListNode {
    string data;
    struct ListNode* next;
};
void insert(ListNode& node, string value);
bool del(ListNode& node, string value);
int isEmpty(const ListNode& node);
void printList(const ListNode& start);
void instructions(void);
int main(void) {
    ListNode start = {"dummy", nullptr};
    int choice;
    string item;
    instructions();
    cout << "? ";
    cin >> choice;
    while (choice != 3) {
        switch (choice) {
            case 1:
                cout << "Enter a string: ";
                cin >> item;
                insert(start, item);
                printList(start);
                break;
            case 2:
                if (!isEmpty(start)) {
                    cout << "Enter string to be deleted: ";
                    cin >> item;
                    if (del(start, item)) {
                        cout << item << " deleted." << endl;
                        printList(start);
                    } else {
                        cout << item << " not found." << endl << endl;
                    }
                } else {
                    cout << "List is empty." << endl;
                }
                break;
            default:
                cout << "Invalid choice." << endl;
                instructions();
                break;
        }
        cout << "? ";
        cin >> choice;
    }
    cout << "End of run." << endl;
}
void instructions(void) {
    cout << "Enter your choice:\n"
         << " 1 to insert an element into the list.\n"
         << " 2 to delete an element from the list.\n"
         << " 3 to end." << endl;
}
void insert(ListNode& node, string value) {
    if (node.next) {
        if (value < node.next->data) {
            ListNode* next = node.next;
            ListNode* newNode = new ListNode({value, next});
            node.next = newNode;
        } else {
            insert(*(node.next), value);
        }
        return;
    }
    ListNode* newNode = new ListNode({value, nullptr});
    node.next = newNode;
}
bool del(ListNode& node, string value) {
    if (node.next != nullptr) {
        if (node.next->data == value) {
            ListNode* tmp = node.next;
            node.next = node.next->next;
            free(tmp);
            return true;
        } else {
            return del(*(node.next), value);
        }
    }
    return false;
}
int isEmpty(const ListNode& node) {
    return node.next == nullptr;
}
void printList(const ListNode& start) {
    if (isEmpty(start)) {
        cout << "List is empty." << endl;
        return;
    }
    cout << "The list is:" << endl;
    ListNode tmp = start;
    while (tmp.next != nullptr) {
        cout << tmp.next->data << " --> ";
        tmp = *(tmp.next);
    }
    cout << "NULL" << endl;
}