#include <iostream>
#include <conio.h>
#include <Windows.h>

using namespace std;

struct List
{
	int Value;
	List* pNext;
};

List* head;

void Initial();
bool isEmpty();
List* Search(int);
List* SearchPrev(int);
void AddAfter(int);
void AddBefore(int);
void DeleteBefore(int);
void DeleteAfter(int);
void DeleteAll();
void Output();

int main()
{
	int q;

	do
	{
		SetConsoleOutputCP(1251);
		SetConsoleCP(1251);

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

		cin >> q;

		if (q == 1)
		{
			Initial();
		}
		else if (q == 2)
		{
			if (isEmpty() == 0)
				cout << "Список не пустой" << endl;
			else cout << "Список пустой" << endl;
		}
		else if (q == 3)
		{
			int num;
			cout << "Введите искомое значение:" << endl;
			cin >> num;
			cout << Search(num) << endl;
		}
		else if (q == 4)
		{
			int num;
			cout << "Введите искомое значение:" << endl;
			cin >> num;
			AddAfter(num);
		}
		else if (q == 5)
		{
			int num;
			cout << "Введите искомое значение:" << endl;
			cin >> num;
			AddBefore(num);
		}
		else if (q == 6)
		{
			int num;
			cout << "Введите искомое значение:" << endl;
			cin >> num;
			DeleteAfter(num);
		}
		else if (q == 7)
		{
			int num;
			cout << "Введите искомое значение:" << endl;
			cin >> num;
			DeleteBefore(num);
		}
		else if (q == 8)
			DeleteAll();
		else if (q == 9)
			Output();
	} while (q != 0);
}

void Initial()
{
	head = new List;
	head->Value = 0;//head выполняет роль счётчик элементов

	List* tmp = head;
	tmp->pNext = nullptr;

	int elem;

	cout << "Введите элементы списка:" << endl;
	cin >> elem;
	while (elem != 0)
	{
		tmp->pNext = new List;
		tmp = tmp->pNext;
		tmp->Value = elem;
		head->Value++;
		tmp->pNext = nullptr;
		cin >> elem;
	}
}

bool isEmpty()
{
	return head == nullptr;
}

List* Search(int num)//функция выводит адрес элемента с заданным значением
{
	List* tmp = head->pNext;

	while (tmp != nullptr && tmp->Value != num)
	{
		tmp = tmp->pNext;
	}

	if (tmp == nullptr)
		cout << "Такого элемента нет в списке" << endl;

	return tmp;
}

List* SearchPrev(int num)//функция выводит адрес элемента находящего перед элементом с заданным значением
{
	List* tmp = head;

	while (tmp->pNext != nullptr)
	{
		if (tmp->pNext->Value == num)
			return tmp;
		tmp = tmp->pNext;
	}

	cout << "Такого элемента нет в списке" << endl;

	return nullptr;
}

void AddAfter(int num)
{
	List* prev = SearchPrev(num), * tmp = prev, * tmp2 = new List;

	if (tmp != nullptr)
	{
		cout << "Введите значение для нового элемента:" << endl;
		cin >> tmp2->Value;
		tmp2->pNext = tmp->pNext;
		tmp->pNext = tmp2;
		head->Value++;
	}
}

void AddBefore(int num)
{
	List* elem = Search(num), * tmp = elem;

	if (tmp != nullptr && tmp->pNext == nullptr)//когда нужно добавить в конец списка
	{
		tmp->pNext = new List;
		tmp->pNext->pNext = nullptr;
		cout << "Введите значение для нового элемента:" << endl;
		cin >> tmp->pNext->Value;
		head->Value++;
	}
	else if (tmp != nullptr)
	{
		List* tmp2 = new List;

		cout << "Введите значение для нового элемента:" << endl;
		cin >> tmp2->Value;
		tmp2->pNext = tmp->pNext;
		tmp->pNext = tmp2;
		head->Value++;
	}
}

void DeleteBefore(int num)
{
	List* elem = Search(num), * tmp = elem->pNext;

	if (elem != nullptr && tmp == nullptr)
		cout << "Нельзя удалить элемент следующий за последним" << endl;
	else if (elem != nullptr && tmp->pNext == nullptr)//для последнего элемента
	{
		delete tmp;
		elem->pNext = nullptr;
		head->Value--;
	}
	else if (elem != nullptr && tmp != nullptr)
	{
		elem->pNext = elem->pNext->pNext;
		delete tmp;
		head->Value--;
	}
}

void DeleteAfter(int num)
{
	List* elem = SearchPrev(num), * tmp;

	if (elem == head)
		cout << "Нельзя удалить элемент перед первым элементом" << endl;
	else if (elem != nullptr)
	{
		List* tmp2 = head;//tmp2 элемент перед предыдущим
		while (tmp2->pNext != elem)
		{
			tmp2 = tmp2->pNext;
		}
		tmp = elem;
		tmp2->pNext = elem->pNext;
		delete tmp;
		head->Value--;
	}
}

void DeleteAll()
{
	List* tmp;
	while (head->pNext != nullptr)
	{
		tmp = head->pNext;
		head->pNext = tmp->pNext;
		delete tmp;
		head->Value--;
	}
}

void Output()
{
	List* tmp = head;
	cout << "Вывод списка:" << endl;
	for (tmp; tmp != nullptr; tmp = tmp->pNext)
		cout << tmp->Value << '\t';
	cout << endl;
}