#include <iostream>

using namespace std;

struct node
{
    int val;
    node* next, *prev;
};

void del(node* p, node*& head, node*& tail)
{
    node* usun = new node;
    if (p == head)
    {
        usun = head;
        head = head->next;
        head->prev = NULL;
    }
    else if (p == tail)
    {
        usun = tail;
        tail = tail->prev;
        tail->next = NULL;
    }
    else
    {
        usun = p;
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    delete usun;
}

void delete_tail(node*& tail)
{
    node* usun = new node;
    usun = tail;
    tail = tail->prev;
    tail->next = NULL;
    delete usun;
}

void delete_head(node*& head)
{
    node* usun = new node;
    usun = head;
    head = head->next;
    head->prev = NULL;
    delete usun;
}

void insert_head(node*& head, node*& tail, int x)
{
    node* nowy = new node;
    nowy->val = x;
    nowy->next = NULL;
    nowy->prev = NULL;
    if (!head)
    {
        head = nowy;
        tail = nowy;
    }
    else
    {
        nowy->next = head;
        head = nowy;
        nowy->next->prev = nowy;
    }
}

void insert_tail(node*& head, node*& tail, int x)
{
    node* nowy = new node;
    nowy->val = x;
    nowy->next = NULL;
    nowy->prev = NULL;

    if (!head)
    {
        head = nowy;
        tail = nowy;
    }
    else
    {
        nowy->prev = tail;
        tail = nowy;
        nowy->prev->next = nowy;
    }
}

void insert_after(node* p, int x)
{
    node* nowy = new node;
    nowy->val = x;
    nowy->next = p->next;
    nowy->prev = p;
    if (p->next)
    {
        p->next->prev = nowy;
        p->next = nowy;
    }
}

void insert_before(node* p, int x)
{
    node* nowy = new node;
    nowy->val = x;
    nowy->next = p;
    nowy->prev = p->prev;
    if (p->prev)
    {
        p->prev->next = nowy;
        p->prev = nowy;
    }
}


void show(node* head)
{
    while (head)
    {
        cout << head->val << " ";
        head = head->next;
    }cout << endl;
}

int main()
{
    node* head = NULL;
    node* tail = NULL;

    int wybor = 0, liczba = 0, numer = 0;

    do
    {
        node* p = head;
        system("cls");
        cout << "Elementy listy: " << endl;
        show(head);
        cout << "Menu: " << endl << "1. Dodaj na poczatek listy" << endl << "2. Dodaj na koniec listy" << endl << "3. Dodaj po danym elemencie" << endl << "4. Dodaj przed danym elementem" <<endl << "5. Usun element na poczatku" << endl <<"6. Usun element na koncu" << endl << "7. Usun dowolny element" << endl;
        cout << "Wybor: ";
        cin >> wybor;
        switch (wybor)
        {
        case 1:
            cout << "Podaj liczbe: ";
            cin >> liczba;
            insert_head(head, tail, liczba);
            break;

        case 2:
            cout << "Podaj liczbe: ";
            cin >> liczba;
            insert_tail(head, tail, liczba);
            break;

        case 3:
            cout << "Podaj liczbe: ";
            cin >> liczba;
            cout << "Podaj numer elementu: ";
            cin >> numer;
            for (int i = 1; i < numer; i++)
                p = p->next;
            insert_after(p, liczba);
            break;

        case 4:
        {cout << "Podaj liczbe: ";
        cin >> liczba;
        cout << "Podaj numer elementu: ";
        cin >> numer;
        node* p = head;
        for (int i = 1; i < numer; i++)
            p = p->next;
        insert_before(p, liczba);
        break; }

        case 5:
            delete_head(head);
            break;

        case 6:
            delete_tail(tail);
            break;

        case 7:
            cout << "Podaj numer elementu: ";
            cin >> numer;
            node* p = head;
            for (int i = 1; i < numer; i++)
                p = p->next;
            del(p, head, tail);
            break;
        }
    } while (wybor != 10);

    return 0;
}