#include <iostream>
#include <random>
using namespace std;

struct UZ //структура элемента списка
{
    int num;//число
    UZ *next;//указатель на следующий элемент
};

struct List//структура листа
{
    UZ *Head = new UZ;//голова
    int n;//размерность
    List(int n) :n(n)//создание листа
    {
        cout << "Ввод элементов: ";
        int x;
        cin >> x;
        Head->num = x;//ввод значения первого элемента
        Head->next = NULL;
        UZ *Next = Head;
        for (int i = 1; i < n; i++)//в цикле создаём новые элементы, определяем их значения, указываем ссылки друг на друга
        {
            UZ *New = new UZ;
            cin >> x;
            New->next = NULL;
            New->num = x;

            //Next->num = x;
            Next->next = New;
            Next = New;
        }
    }
    void print()//Вывод списка с первого элемента, проверяя существование следующего через наличие ссылки
    {
        cout << "Список: ";
        UZ *p;
        bool b = true;
        p = Head;
        do
        {
            if (p == NULL)//если ссылки на след. нет, остановка
                b = false;
            else { cout << p->num << " "; p = p->next; }//если есть - вывод и переход к следующему
        } while (b);
    }
    void pfirst()
    {
        cout << "Новый элемент в начале: ";
        UZ *First = new UZ;
        cin >> First->num;//создание и ввод нового элемента
        if (n != 0) {//если список не пустой, то ставим его перед головой
            First->next = Head;
            Head = First;
        }
        else
        {
            Head->num = First->num;//если список пуст, то новый элемент теперь голова
            Head->next = NULL;
        }
        n++;
    }
    void plast()
    {
        cout << "Новый элемент в конце: ";
        UZ *Last = new UZ;
        cin >> Last->num;//создание элемента
        Last->next = NULL;
        if (Head->num == NULL)//если список пустой - новый элемент становится головой
            Head = Last;
        else
        {
            UZ *search = Head;
            while (search->next != NULL)//если не пуст, то по ссылкам добираемся до последнего элемента
                search = search->next;
            search->next = Last;//ставим новый элемент в конец
            n++;
        }
    }
    void mdel()
    {
        cout << "Удаление элемента: ";
        int val;
        cin >> val;//определение какого элемента удаляем

        UZ *count = Head;
        int j = 0;
        for (int i = 0; i < n - 1; i++)//считаем сколько элементов надо удалить
        {
            if (count->num == val)
                j++;
            count = count->next;
        }
        if (count->num == val)
            j++;
        for (int i = 0; i < j; i++) {
            int m = 0;
            UZ *search;
            if (Head->num == val)//удаляемый элемент в начале
            {
                Head = Head->next;
            }
            else
            {
                search = Head;
                while ((search->num != val) && m < n - 1)//поиск следующего для удаления
                {
                    search = search->next;
                    m++;
                }
                UZ *dlt = Head;
                for (int i = 0; i < m - 1; i++)//удаление элемента
                {
                    dlt = dlt->next;
                }
                dlt->next = search->next;
                search = dlt;
            }
            n--;
        }
    }
    void delall()
    {
        UZ *hlp = Head;
        for (int i = 1; i < n - 1; i++)//обход всего списка, удаляя всё по ходу
        {
            UZ *hlp1 = hlp->next;
            hlp->next = NULL;
            hlp->num = NULL;
            hlp = hlp1;
        }
        hlp->next = NULL;
        hlp->num = NULL;
        n = 0;
    }
};

int main()
{
    cout << "Введите размер списка:\n";
    int n;
    cin >> n;
    List *list = new List(n);
    cout << "[1]Вывод\n[2]Новый элемент в начале\n[3]Новый элемент в конце\n[4]Удаление элемента\n[5]Удаление списка\n[6]Закончить\n";
    int sw;
    bool ch = true;
    while (ch)
    {
        cout << "Выберите действие:\n";
        cin >> sw;
        switch (sw)
        {
        case 1:
        {list->print(); break; }
        case 2:
        {list->pfirst(); break; }
        case 3:
        {list->plast(); break; }
        case 4:
        {list->mdel(); break; }
        case 5:
        {list->delall(); break; }
        case 6:
        {ch = false; break; }
        default:
            break;
        }
    }
}