//----------------

#include <iostream.h>

class List
{
        protected:
                struct node
                {
                        int info;
                        struct node *next;
                };
                typedef struct node *NODEPTR;
                NODEPTR listptr;        // the pointer to the first node of the list

        public:
                List();
                ~List();
                int emptylist();
                void insertafter(int oldvalue,int newvalue);
                void push(int newvalue);
                void deletevalue(int oldvalue);
                void insertback(int newvalue);
                void deletefromback();
                void merge(List);
                int pop();
                void print();
};

List::List()
{
        listptr = 0;
}

List::~List()
{
        if (!emptylist())
        {
                NODEPTR currentptr = listptr,tempptr;

                while (currentptr != 0)
                {
                        tempptr = currentptr;
                        currentptr = currentptr->next;
                        delete tempptr;
                }
        }
}

int List::emptylist()
{
        return (listptr == 0);
}

void List::insertafter(int oldvalue,int newvalue)
{
        NODEPTR p, q;

        for (p = listptr;p != 0 && p->info != oldvalue; p = p->next);

        if (p == 0)
                cout << "ERROR: value sought is not on the list\n";

        else
        {
                q = new node;
                q -> info = newvalue;
                q -> next = p -> next;
                p -> next = q;
        }
}

void List::push(int newvalue)
{
        NODEPTR p;

        p = new node;
        p -> info = newvalue;
        p -> next = listptr;
        listptr = p;
}

void List::insertback(int newvalue)
{
        NODEPTR currentptr,tempptr;
        NODEPTR p;

        p = new node;
        p -> info = newvalue;
        p -> next = 0;

        if (emptylist())
                listptr = p;
        else
        {
                currentptr = listptr;

                while(currentptr != 0)
                {
                        tempptr = currentptr;
                        currentptr = currentptr->next;
                }

                tempptr->next = p;

        }

}

void List::deletefromback()
{

        if (!emptylist())
        {

                if (listptr->next == 0)
                        listptr = 0;

                else
                {

                        int nodenumber = 0,i;

                        NODEPTR currentptr,tempptr;
                        currentptr = listptr;

                        while(currentptr != 0)
                        {
                                currentptr = currentptr->next;
                                nodenumber++;
                        }

                        currentptr = listptr;

                        for (i=1;i<nodenumber-1;i++)
                                currentptr = currentptr->next;

                        currentptr->next = 0;
               }
        }


}

void List::deletevalue(int oldvalue)
{
        NODEPTR p, q;
        for (q=0, p=listptr; p!= 0 && p->info!=oldvalue; q=p, p=p->next);

        if (p == 0)
                cout << "ERROR: value sought is not on the list" << endl;

        else
        {
                if (q == 0)
                        listptr = p->next;
                else
                        q->next = p->next;

                delete p;
        }
}

int List::pop()
{

        if (!emptylist())
        {
                NODEPTR p;
                int x;

                p = listptr;

                listptr = p->next;
                x = p->info;
                delete p;
                return x;
        }
}

void List::print()
{

        if (emptylist())
                cout <<"The list is empty";
        else
        {
                NODEPTR currentptr;

                cout <<"\nThe list is:";

                currentptr = listptr;

                while(currentptr != 0)
                {
                        cout << currentptr->info <<' ';
                        currentptr = currentptr->next;
                }
        }
}

//---------------------------------------------------------------
//------ YOU WILL IMPLEMENT THE FOLLOWING FUNCTION---------------
void List::merge(List L1)
{
// This function will merge the given linked list L1 and itself.
// New list must also be sorted so that don't forget to sort while
// merging!

}
//---------------------------------------------------------------
//---------------------------------------------------------------

//Write the main function
void main()
{
        // Create two linked lists. Insert 5 -sorted- elements to each of them.
        // Then merge these two linked lists by calling the merge function.
        //
        // Example call of the function: l1.merge(l2)
        //
        // Note that as you can see from the prototype, merge function won't return the new list,
        // instead the new list will be stored in the l1 list. l2 list won't be changed
        //
        // If you didn't understand the merge function, you can ask to us.
        //
        // Good Luck!
}