// ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <conio>
#include <algorithm>
using namespace std;

struct Node
{
 int data; // содержание
 Node* next; // код на некст
 Node* prev; // код на превиус
};

struct List
{
 Node* head;
 Node* tail;
};
int m[100000];
int N = 0;
auto p = 0;

void Create(List* list)
{
 Node *newNode = new Node();
 newNode->prev = nullptr;
 newNode->next = nullptr;
 list->head = nullptr;
 list->tail = nullptr;
}

void add(List* list, int data)
{
 Node *newNode = new Node(); //Выделение памяти под новый элемент структуры
 newNode->next = nullptr;  //Указываем, что изначально по следующему адресу пусто
 newNode->data = data;
 N++;
 m[p] = newNode->data;
 p++;
 if (list->head != nullptr)
 {
  newNode->prev = list->tail; //Указываем адрес на предыдущий элемент в соотв. поле
  list->tail->next = newNode; //Указываем адрес следующего за хвостом элемента
  list->tail = newNode; //Меняем адрес хвоста
 }
 else //Если список пустой
 {
  newNode->prev = nullptr; //Предыдущий элемент указывает в пустоту
  list->head = newNode; list->tail = newNode; //Голова=Хвост=тот элемент, что сейчас добавили
 }
};

void add_beginning(List* list, int data)
{ 
 cin >> data;
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = list->head ;
 list->head = newNode;
};
void add_ending(List* list, int data)
{ 
 cin >> data;
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->prev = list->tail;
 list->tail->next = newNode;
 list->tail = newNode;
};
Node* search(List* list, int element)
{
 Node* newNode= list->head;
 while (newNode != nullptr)
 {
  if (newNode->data == element)
   return newNode;
  newNode = newNode->next;
 }
 return nullptr;
}
Node* remove (List* list, int element)
{ 
 cin >> element;
 Node* newNode = list->head;
 while (newNode->data != element)
 {
  newNode = newNode->next;
 }
 newNode->next->prev = newNode->prev;
 newNode->prev->next = newNode->next;
 delete newNode;
 return nullptr;
}
void show(List* list)
{
 Node *newNode = list->tail;
 newNode = list->head;
 while (newNode != nullptr)
 {
  cout << newNode>data <<' ';
  newNode = newNode->next;
 }
 cout << endl xss=removed>head;
 sort(m, m + N);
 for (int i = 0; i < N>data = m[i];
  newNode = newNode->next;
 }
};
void MenuInfo()
{
 cout << "\n\t Выберите пункт:\n"
  << "1. Создать список. \n"
  << "2. Добавление элемента в список. \n"
  << "3. Удаление элемента из списка. \n"
  << "4. Вставка элемента в начало. \n"
  << "5. Вставка элемента в конец. \n"
  << "6. Вставка элемента. \n"
  << "7. Сортировка списка. \n"
  << "8. Линейный поиск по списку. \n";

}
void Menu(List* list)
{
 int o, vvod;
 int h = 0;
 do
 {
  MenuInfo();
  cin >> h;
  switch (h)
  {
  case 1:
  {
   Create(list);
   cout << "Список создан! \n";
   break;
  }
  case 2:
   {
   cout << "Сколько элементов добавить? \n";
   cin >> o;
   cout << "Введите элементы \n";
   for ( int i = 0; i < o>> vvod;
    add(list, vvod);
   }
   cout << "Элементы успешно добавлены \n";
   show(list);
   break;
   }
  case 3:
   {
   cout << "Какой элемент удалить? \n";
   remove(list, vvod);
   cout << "Элемент успешно удален \n";
   show(list);
   break;
   }
  case 4:
   {
   cout << "Введите элемент \n";
   add_beginning(list, vvod);
   cout << "Элемент успешно добавлен \n";
   show(list);
   break;
   }
  case 5:
   {
   cout << "Введите элемент \n";
   add_ending(list, vvod);
   cout << "Элемент успешно добавлен \n";
   show(list);
   break;
   }
  case 6:
   {
   cout << "Введите элемент \n";
   add(list, vvod);
   cout << "Элемент успешно добавлен \n";
   show(list);
   break;
   }
  case 7:
   {
   Sort(list, m);
   cout << "Список успешно посорчен \n";
   show(list);
   break;
   }
  case 8:
   {
   cout << "Введите элемент \n";
   cout << "Элемент успешно найден \n";
   search(list, vvod);
   break;
   }

  }

 } while (h != 0);
}
int main()
{ 
 setlocale(0, "");
 int data;
 List *list = new List;
 Node *node = new Node;
 Menu(list);
 Create(list);
 system&#40;"pause"&#41;;
 return 0;
}