#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){
            first = newPtr;
            last = newPtr;
        }
        else {
            newPtr -> next = first;
            first = newPtr;
        }
    }
    int shift(){
         current = first;
        if (current == 0)
            return 0;

        if (first == last){
            int tempData = first->data;
            delete first;
            first = last = current = 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){

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

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

        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++) {

            if (current == 0) {
                cout<<"Ne mogu vstavit"<<endl;
                return;
            }
        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;

        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 = -1;
    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 << "vvedi chislo: "; cin >> value; d.insert(position, value);break;
        }
        cout << "Spisok seychas: "; d.showList();
    }
return 0;

}