Односвязный и двусвязный список

#include <conio.h>
#include <iostream>
#include <string>
#include <Windows.h>
 
using namespace std;
struct List_O//первый список
{
    int Data;
    List_O* next;
};
 
void Print_O(List_O* begin)
{
    if (begin != NULL)
    {
        cout << begin->Data << "\t";
        Print_O(begin->next);
    }
    else cout << "\n";
}
 
void Insert_O(List_O* begin, unsigned n, int val)
{
    unsigned i = 1;
    List_O*tmp = NULL;
    List_O* first = NULL ;
    
    while (i < (n - 1) && begin->next)
    {
        begin = begin->next;
        i++;
    }
    tmp = (List_O*)malloc(sizeof(List_O));
    tmp->Data = val;
    
    if (begin->next)
    {
        tmp->next = begin->next;
        //иначе на NULL
    }
    else tmp->next = NULL;
    begin->next = tmp;
}
void Search_O(List_O* begin, int val)//поиск элемента 
{
    bool f = false;
    int i = 1;
    while (begin)
    {
        if (begin->Data == val)
        {
            f = true;
            cout << "Элемент найден,его позиция: " << i << endl;
            break;
        }
        else begin = begin->next;
        i++;
    }
    if (f == false) cout << "Элемент не найден" << endl;
}
 
void Delete_O(List_O* head, int data)//удаление элемента
{
    List_O* temp = head;
    List_O* el = NULL;
    if (head && head->Data == data)
    {
        el = head;
        head = head->next;
        delete el;
        return;
    }
    while (temp->next)
    {
        if (temp->next->Data == data)
        {
            el = temp->next;
            temp->next = el->next;
            delete el;
            break;
        }
        temp = temp->next;
 
    }
}
void Init_O(int n, List_O** begin)//инициализация
{
    
    int a;
 
    if (n > 0)
    {
        (*begin) = new List_O();
        cout << "Введите значение: ";
        cin >> a;
        
        (*begin)->Data = a;
 
        (*begin)->next = NULL;
        Init_O(n - 1, &((*begin)->next));
    }
}
//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//
struct node//двусвязный список
{
    int value;
    struct node* next;
    struct node* prev;
};
struct node* head;
struct node* tail;
 
void init()
{
    head = NULL;
    tail = NULL;
}
 
void insertFirst(int element)
{
    struct node* newItem;
    newItem = new node;
    if (head == NULL)
    {
        head = newItem;
        newItem->prev = NULL;
        newItem->value = element;
        newItem->next = NULL;
        tail = newItem;
    }
    else
    {
        newItem->next = head;
        newItem->value = element;
        newItem->prev = NULL;
        head->prev = newItem;
        head = newItem;
    }
}
void insertLast(int element)
{
    struct node* newItem;
    newItem = new node;
    newItem->value = element;
    if (head == NULL)
    {
        head = newItem;
        newItem->prev = NULL;
        newItem->next = NULL;
        tail = newItem;
    }
    else
    {
        newItem->prev = tail;
        tail->next = newItem;
        newItem->next = NULL;
        tail = newItem;
    }
}
void insertAfter(int old, int element)
{
    struct node* newItem;
    newItem = new node;
    struct node* temp;
    temp = head;
    if (head == NULL)
    {
        cout << "could not insert" << endl;
        return;
    }
    if (head == tail)
    {
        if (head->value != old)
        {
            cout << "could not insert" << endl;
            return;
        }
        newItem->value = element;
        head->next = newItem;
        newItem->next = NULL;
        head->prev = NULL;
        newItem->prev = head;
        tail = newItem;
        return;
    }
    if (tail->value == element)
    {
        newItem->next = NULL;
        newItem->prev = tail;
        tail->next = newItem;
        tail = newItem;
        return;
    }
    while (temp->value != old)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            cout << "Could not insert" << endl;
            cout << "element not found" << endl;
            return;
        }
    }
 
    newItem->next = temp->next;
    newItem->prev = temp;
    newItem->value = element;
    temp->next->prev = newItem;
    temp->next = newItem;
}
void deleteItem(int element)
{
    struct node* temp;
    temp = head;
    if (head == tail)
    {
        if (head->value != element)
        {
            cout << "could not delete" << endl;
            return;
        }
        head = NULL;
        tail = NULL;
        delete temp;
        return;
    }
    if (head->value == element)
    {
        head = head->next;
        head->prev = NULL;
        delete temp;
        return;
    }
    else if (tail->value == element)
    {
        temp = tail;
        tail = tail->prev;
        tail->next = NULL;
        delete temp;
        return;
    }
    while (temp->value != element)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            cout << "element not found" << endl;
            return;
        }
    }
    temp->next->prev = temp->prev;
    temp->prev->next = temp->next;
    delete temp;
}
struct node* searchItem(int element)
{
    struct node* temp;
    temp = head;
    while (temp != NULL)
    {
        if (temp->value == element)
        {
            return temp;
            break;
        }
        temp = temp->next;
    }
    return NULL;
}
void printList()
{
    struct node* temp;
    temp = head;
    while (temp != NULL)
    {
        printf("%d->", temp->value);
        temp = temp->next;
    }
    puts("");
}
 
 
//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//
 
struct key
{
    int x;
    key* next;
};
 
 
//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//-//
void menu()
{
    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 << "10.Удалить элемент из списка.(двунапр.список)" << endl;
    cout << "Если хотите выйти нажмите у" << endl;
}
 
 
 
    int main()
    {
 
 
        init();
        List_O* begin = NULL; int n = 0;
        int pos, val, udal, sear, num;
        char exit;
        setlocale(LC_ALL, "rus");
        cout << "Введите размер n (n>1): ";
        cin >> n;
        Init_O(n, &begin);
        cout << "=================================================================" << endl;
 
 
 
        do {
            menu();//case 1-4= однонаправленный список
            int choice;
            cin >> choice;
            switch (choice) {
            case 1:
            {
                cout << "Исходный список: ";
                Print_O(begin);
            }break;
            case 2:
            {
                if (begin != NULL)
                {
                    cout << "Введите позицию (pos>0), после которой хотите вставить новый элемент: ";
                    cin >> pos;
                    cout << "Введите вставляемое число: ";
                    cin >> val;
                    Insert_O(begin, pos, val);
                    cout << "Исходный список: ";
                    Print_O(begin);
 
                }
            }break;
            case 3:
            {
                if (begin != NULL)
                {
                    cout << "Введите удаляемый элемент: ";
                    cin >> udal;
                    Delete_O(begin, udal);
                    cout << "Исходный список: ";
                    Print_O(begin);
 
                }
            }break;
            case 4:
            {
                cout << "Введите искомое число: ";
                cin >> sear;
                Search_O(begin, sear);
            }break;
            case 5:
            {
                int element;
                cout << "Введите число";
                cin >> element;
                insertFirst(element);
                printList();
            }break;
            case 6:
            {
                int element;
                cout << "Введите число";
                cin >> element;
                insertLast(element);
                printList();
            }break;
            case 7:
            {
                int old, newitem;
                cout << "Введите после какого числа вы хотите ввести новое";
                cin >> old;
                cout << "Новое число";
                cin >> newitem;
                insertAfter(old, newitem);
                printList();
            }break;
            case 8:
            {
                int item;
                cout << "Введите число, которое хотите найти";
                cin >> item;
                struct node* ans = searchItem(item);
                if (ans != NULL) cout << "Найдено " << ans->value << endl;
                else cout << "Не найдено" << endl;
            }break;
            case 9:
            {
                printList();
            }break;
            case 10:
            {
                int element;
                cout << "Введите число для удаления" << endl;
                cin >> element;
                deleteItem(element);
                printList();
            }break;
            case 11:
            {
            
            }break;
            }
            cout << "Хотите выйти?" << endl;
            cin >> exit;
        } while (exit != 'y');
 
        system("pause");
 
        return 0;
 
    }