#include<iostream>

using namespace std;

class lists
{

private:
    struct node{  //structure to hold the node
       int data; //value
       node *next; // pionter to the next list
    };
    node *head;  // pointer to the first list

public:
    lists()   //constructor
    {
        head= nullptr;
    }
    void add_node(int num)  // adding a node at the end
    {
        node *newnode= new node; //allocate a new node to temporarily store number to append
        node *nodeptr;   // for transversal
        newnode->data=num;
        newnode->next= nullptr;

        if(!head)  // if the list is empty
        {
            head=newnode;
        }
        else  // if the list is not empty append the number
        {
            nodeptr=head;
            while(nodeptr->next) // transverse to get to the last node
            {
                nodeptr=nodeptr->next;
            }
            nodeptr->next=newnode;
        }

    }

   void insert_node(int num) //to add a node in an organized ascending order
    {
        node *newnode= new node; // to store new data
        node *prvnode=nullptr;
        node *nodeptr;

        newnode->data=num;


        if(!head)  // if theres no existing list
        {
            head=newnode;
            newnode->next=nullptr;
        }else{
            prvnode=nullptr;
            nodeptr=head;

              while(nodeptr!=nullptr && nodeptr->data<num) //transverse through the list until u get a number greater
              {
                  prvnode=nodeptr;
                  nodeptr=nodeptr->next;
              }
              if(prvnode==nullptr) // if you don't get a data less than the actual number you want to insert, that means there will be no previous, the new number you want to insert will be the head
              {
                head=newnode;
                newnode->next=nodeptr;   // newnode becomes the head nd pionts to the next node
              }else{
                  prvnode->next=newnode;
                  newnode->next=nodeptr;
              }
        }


    }

    void show_list() // function to display all nodes
    {
        node *nodeptr; // for transversal
        nodeptr=head; // starting from the first list
        while(nodeptr)
        {
            cout<<nodeptr->data<<endl;
            nodeptr=nodeptr->next;
        }

    }


    void delete_node(int num) // function to delete a number/ a node
    {
        node *prvnode;
        node *nodeptr;

        if(!head) // if theres no list return
        {
            return;
        }
        if(head->data==num) //if the first list is the number we are looking for
        {
            nodeptr=head->next; //let nodeptr become what head was pointing to (i.e next list)
            delete head; // delete head
            head=nodeptr; // let head become nodeptr
        }
        else
        {
            nodeptr=head;
            prvnode = nullptr;
            while(nodeptr!=nullptr && nodeptr->data!=num) // transverse until we find the number
            {
                prvnode=nodeptr;
                nodeptr=nodeptr->next;
            }
            if(nodeptr) // if we find the number,
            {
                prvnode->next= nodeptr->next; // previous node should point to nodeptr node
                delete nodeptr; // delete nodeptr
            }
        }
    }
    ~lists() //de-constructor
    {
        node *nodeptr;
        node *nextnode;
        nodeptr=head; //assign nodeptr to the first list

        while(nodeptr!= nullptr) // transverse
        {
            nextnode=nodeptr->next;
            delete nodeptr;
            nodeptr=nextnode; //position nodeptr at the nextnode again
        }
    }
};