#include <iostream>

struct Node         //Инициализация списка
{
    int data;       //Присвоение введенного значения элементу
    Node *Next;     //Указатель на следующий элемент
    Node *Prev;     //Указатель на предыдущий элемнт
};

class List
{
    Node *Head, *Tail;  //Указатель на адреса начала и конца списка

public:
    List(): Head(NULL), Tail(NULL) {}; //Адреса пусты

    ~List();                    //Деструктор
    void writeList();           //Вывод списка на экран
    void addElem (int data);    //Добавление элементов по возрастанию
    void isEmpty();             //Проверка на пустоту
    void findMin();             //Поиск минимального элемента
    void delNeed(int elem);             //Удаление заданного
    void addAfterNeed(int elem, int e);        //Добавление после каждого заданного
    void delAfterNeed(int elem);        //Удаление после каждого заданного
    void listSize();
    int n;                      //Размер списка
};

List::~List()                   //Деструктор
{
    while (Head) {
        Tail = Head -> Next;
        delete Head;
        Head = Tail;
    }
    n = 0;
}

void List::isEmpty()            //Проверка на пустоту
{
    if (Head == NULL) {
        std::cout << "Лист пуст" << std::endl;
    }
    else
        std::cout << "Лист не пуст" << std::endl;
}

void List::listSize()          //Размер списка
{
    std::cout << "Размер списка = " << n << std::endl;
}

void List::addElem (int data)      //Добавление по возрастанию
{
    Node *p = new Node;
    Node *temp = new Node;
    temp -> Next = NULL;
    temp -> data = data;
    p = Head;
    if (Head != NULL) {
        if (temp -> data <= Head -> data) { //Если добавляемый элемент <= голове
            temp -> Next = Head;
            Head = temp;
            n++;
            return;
        }

        if (temp -> data >= Tail -> data) //Если добавляемый элемент >= хвосту
        {
            p = Head;
            int b = 1;
            while (b < n) {
                p = p -> Next;
                b++;
            }
            temp -> Next = p -> Next;
            temp -> Prev = p;
            p -> Next = temp;
            Tail  = temp;
        }

        if ((temp -> data >= p -> data) and (temp -> data < Tail -> data)) //Если добавляемый элемент >= элементу в списке и < хвоста
        {
            int c = 1;
            p = Head;
            while ((temp -> data >= p -> data) and (p -> Next != NULL))
            {
                c++;
                p = p -> Next;
            }
            int count = 1;
            p = Head;
            while (count < c - 1)
            {
                count++;
                p = p -> Next;
            }
            temp -> Next = p -> Next;
            p -> Next = temp;
        }
        n++;
    }
    else                        //Если список пустой
    {
        temp -> Prev = NULL;
        Head = Tail = temp;
        n++;
    }
}

void List::delNeed(int elem)       //Удаление заданного
{
    Node *p = new Node;
    p = Head;
    if (n == 0)
    {
        std::cout << "Лист пуст" << std::endl;
    } else if (n == 1)
    {
        if (Head -> data == elem)
        {
            delete Head;
            Head = NULL;
            Tail = Head;
            n = 0;
        }
    } else
    {
        while ((Head -> Next != NULL) && (Head -> data == elem))
        {
            p = Head -> Next;
            delete Head;
            Head = p;
            Head -> Prev = NULL;
            n--;
        }
        p = Head;
        while (p -> Next != NULL)
        {
            if (p -> data == elem)
            {
                p -> Next -> Prev = p -> Prev;
                p -> Prev -> Next = p -> Next;
                Node *next = p -> Next;
                delete p;
                p = next;
                n--;
            } else
                p = p -> Next;
        }
        if (n == 1)
            delNeed(elem);
        else if (Tail -> data == elem)
        {
            p = Tail -> Prev;
            delete Tail;
            n--;
            Tail = p;
        }
    }
}

void List::addAfterNeed(int elem, int e)       //Добавление после каждого заданного
{
    Node *p = new Node;
    p = Head;
    if (n == 0)
    {
        std::cout << "Лист пуст" << std::endl;
    }
    else
    {
        while (p -> Next !=NULL)
        {
            if (p -> data == elem)
            {
                Node *temp = new Node;
                temp -> data = e;
                temp -> Next = p -> Next;
                temp -> Prev = p;
                p -> Next = temp;
                temp -> Next -> Prev = temp;
                n++;
                p = p-> Next;
           }
           if (p -> Next != NULL)
           {
               p = p -> Next;
           }
        }

        if (p -> data == elem)
        {
            Node *temp = new Node;
            temp -> Next = NULL;
            temp -> data = e;
            temp -> Next = p -> Next;
            temp -> Prev = p;
            p -> Next = temp;
            n++;
        }
    }
}

void List::delAfterNeed(int elem)       //Удаление после каждого заданного
{
    Node *p = new Node;
    p = Head;
    if (n == 0)
    {
        std::cout << "Лист пуст" << std::endl;
    }
    else
    {
        while (p -> Next !=NULL)
        {
            if (p -> data == elem)
            {
                Node *h;
                h = p -> Next;
                p -> Next = h -> Next;
                delete h;
                n--;
            }
            if (p -> Next != NULL)
            {
                p = p -> Next;
            }
        }

        if (p == Tail -> Prev)
        {
            Node *h;
            h = Tail;
            p = h -> Prev;
            p -> Next = NULL;
            Tail = p;
            delete h;
            n--;
        }
    }
}

void List::findMin()
{
    if (n != 0)
    {
        int min = 1000000;
        Node *p = new Node;
        p = Head;
        while (p -> Next != NULL)
        {
            if (p -> data < min)
            {
                min = p -> data;
            }
            p = p -> Next;
        }
        std::cout << "Минимальный элемент = " << min << std::endl;
    }
    else
    {
        std::cout << "Лист пуст" << std::endl;
    }
}

void List::writeList()
{
    Node *temp;
    temp = Head;
    while (temp != NULL)
    {
        std::cout << temp -> data << " ";
        temp = temp -> Next;
    }
    if (n == 0)
    {
        std::cout << "Лист пуст";
    }
    std::cout << "\n";
}

int main ()
{
    int data;
    int elem;
    int e;
    int x = 1;
    List listElem;

    std::cout << "1. Добавление элемента по возрастанию" << std::endl;
    std::cout << "2. Вывод списка" << std::endl;
    std::cout << "3. Добавление элемента после каждого заданного" << std::endl;
    std::cout << "4. Удаление после каждого заданного" << std::endl;
    std::cout << "5. Удаление заданного" << std::endl;
    std::cout << "6. Поиск минимального элемента" << std::endl;
    std::cout << "7. Удаление списка" << std::endl;
    std::cout << "8. Размер списка" << std::endl;
    std::cout << "9. Проверка на пустоту" << std::endl;
    std::cout << "0. Выход из программы" << std::endl;

    while (x != 0)
    {
        std::cin >> x;
        switch (x)
        {
            case 1:
                std::cout << "a = ";
                std::cin >> data;
                listElem.addElem(data);
                break;
            case 2:
                listElem.writeList();
                break;
            case 3:
                std::cout << "Введите число, после которого нужно вставить n ";
                std::cin >> elem;
                std::cout << "Введите n ";
                std::cin >> e;
                listElem.addAfterNeed(elem, e);
                break;
            case 4:
                std::cout << "Введите число, после которого нужно удалить ";
                std::cin >> elem;
                listElem.delAfterNeed(elem);
                break;
            case 5:
                std::cout << "Введите число, которое нужно удалить ";
                std::cin >> elem;
                listElem.delNeed(elem);
                break;
            case 6:
                listElem.findMin();
                break;
            case 7:
                listElem.~List();
                break;
            case 8:
                listElem.listSize();
                break;
            case 9:
                listElem.isEmpty();
                break;
            case 0:
                ;
        }
    }
    return 0;
}