#include <iostream>

using namespace std;
class Node{
public:
    friend class LinkedList;
    Node(int value){

        data = value;
    }

private:
    int data = NULL;
    Node*  next = 0;

};
class LinkedList{
public:

    void unshift(int value){
        current=first;
        Node* newPtr = new Node(value);
        if (current == 0){

            current = newPtr;
            first = newPtr;
            last = newPtr;
        }
        else {
            newPtr -> next = first;
            first = newPtr;
        }
    }
    int shift(){

        if (first == last){
            int tempData = first->data;
            first = last = 0;
            return tempData;
        }
        else {

            Node* tempPtr = first;
            first = first->next;
            int tempData = tempPtr->data;
            delete tempPtr;
            return tempData;
        }
    }
    void push(int value){
        current = first;
        Node* newPtr = new Node(value);
        if (current == 0){

            current = first = last = newPtr;
        }
        else{
            last->next = newPtr;
            last = newPtr;
        }
    }
    int pop(){

        if (first == last){
            int tempData = first->data;
            first = last = 0;
            return tempData;
        }
       else{
       		current = first;
       		while(current->next != last)
      		    current=current->next;

        	current->next=0;

            Node* tempPtr = last;
            last = current;
            int tempData = tempPtr->data;
            delete tempPtr;
            return tempData;
        }
    }
    void insert(int position, int value){
        Node* newPtr = new Node(value);

        current=first;
        for(int i = 1; i < position; i++)
        current=current->next;

        newPtr->next = current->next;
        current->next=newPtr;
    }
    void showList(){
        current = first;
        while (current!=0){
            cout<<current->data<<' ';
            current = current->next;
        }

    }
    ~LinkedList(){
        current = first;
        Node* tempPtr = current;

        while (current!=0){
            tempPtr = current;
            current = current->next;
            delete tempPtr;
        }
    }
private:
    Node* first = 0;
    Node* last = 0;
    Node* current = 0;
};

int main(){
    LinkedList d;
    int x;
    int value;
    int position;

    cout << "1 dlya vstaski v nachalo" << endl
    << "2 dlya vzyatiya s nachala" << endl
    << "3 dlya vstavki v konec" << endl
    << "4 dlya vzatia s konca" << endl
    << "5 dlya vstavki v seredinu" << endl
    << "0 dlya vihoda" << endl;

    while (x !=0){
        cout<<endl<<"Vvedi nomer ";
        cin>>x;
        switch(x){
            case 1: cout << "vvedi chislo ";
                    cin >> value;
                    d.unshift(value); break;
            case 2: cout<<d.shift()<<endl;break;

            case 3: cout << "vvedi chislo ";
                    cin >> value;
                    d.push(value); break;

            case 4: cout<<d.pop()<<endl;break;

            case 5: cout << "vvedi positsiyu: "; cin >> position;
           			cout << endl << "vvedi chislo: "; cin >> value;
					d.insert(position, value);break;
        }
        cout << "Spisok seychas: "; d.showList();

    }
    d.~LinkedList();

return 0;

}