#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <fstream>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

// تعريف هيكل العقدة
struct node
{
    int item;
    node *next;
};

// متغير لتتبع عدد العقد في القائمة المرتبطة
int counter = 0;

// إعلان عقدة الرأس
node *head;

// إدراج عقدة من الجهة الأمامية للقائمة
void insert_from_front(int item)
{
    // إنشاء عقدة جديدة
    node *newnode = new node;
    newnode->item = item;
    newnode->next = NULL;

    // إذا كانت القائمة فارغة، قم بتعيين العقدة الجديدة كرأس
    if (head == NULL)
    {
        head = newnode;
    }
    else
    {
        // إذا لم تكن القائمة فارغة، ضع العقدة الجديدة في الجهة الأمامية وقم بتحديث الرأس
        newnode->next = head;
        head = newnode;
    }
    counter++;
}

// إدراج عقدة من الجهة الخلفية للقائمة
void insert_from_back(int item)
{
    // إنشاء عقدة جديدة
    node *newnode = new node;
    newnode->item = item;
    newnode->next = NULL;

    // إذا كانت القائمة فارغة، قم بتعيين العقدة الجديدة كرأس
    if (head == NULL)
    {
        head = newnode;
    }
    else
    {
        // إذا لم تكن القائمة فارغة، ابحث عن العقدة الأخيرة وضع العقدة الجديدة بعد العقدة الأخيرة
        node *t = head;

        while (t->next != NULL)
        {
            t = t->next;
        }
        t->next = newnode;
        newnode->next = NULL;
    }
    counter++;
}

// إدراج عقدة في موقع محدد
void insertpos(int pos, int element)
{
    // إذا كان الموقع هو الجهة الأمامية، قم بإدراج من الجهة الأمامية
    if (pos == 1)
    {
        insert_from_front(element);
    }
    // إذا كان الموقع غير الجهة الأمامية، ابحث عن الموقع وقم بإدراج العقدة في هذا الموقع
    else if (pos > 1)
    {
        node *newnode = new node;
        newnode->item = element;
        node *f = head;
        node *p = f;
        int i = 1;
        while (i < pos)
        {
            p = f;
            f = f->next;
            i++;
        }
        p->next = newnode;
        newnode->next = f;
        counter++;
    }
}

// حذف العقدة من الجهة الأمامية
void delete_front()
{
    // إذا كانت القائمة فارغة، قم بطباعة رسالة خطأ
    if (head == NULL)
    {
        cout << "linked list under flow\n";
    }
    // إذا كانت هناك عقدة واحدة فقط، قم بحذفها وقم بتحديث الرأس
    else if (counter == 1)
    {
        delete head;
        head = NULL;
        counter--;
    }
    // إذا كانت هناك أكثر من عقدة، قم بحذف العقدة الجديدة من الجهة الأمامية وقم بتحديث الرأس
    else
    {
        node *temp = head;
        head = head->next;
        delete temp;
        counter--;
    }
}

// حذف العقدة من الجهة الخلفية
void delete_back()
{
    // إذا كانت القائمة فارغة، قم بطباعة رسالة خطأ
    if (head == NULL)
    {
        cout << "linked list under flow\n";
    }
    // إذا كانت هناك عقدة واحدة فقط، قم بحذفها وقم بتحديث الرأس
    else if (counter == 1)
    {
        delete head;
        head = NULL;
        counter--;
    }
    // إذا كانت هناك أكثر من عقدة، قم بالبحث عن العقدة قبل العقدة الأخيرة وحذف العقدة الأخيرة وقم بتحديث الرأس
    else
    {
        node *f = head;
        node *p = f->next;
        while (p->next != NULL)
        {
            f = p;
            p = p->next;
        }
        f->next = NULL;
        delete p;
        counter--;
    }
}

// حذف العقدة من موقع محدد
void deletpos(int pos)
{
    // إذا كان الموقع هو الجهة الأمامية، قم بحذف من الجهة الأمامية
    if (pos == 1)
    {
        delete_front();
    }
    // إذا كان الموقع غير الجهة الأمامية، ابحث عن الموقع وقم بحذف العقدة في هذا الموقع
    else if (pos > 1 && pos <= counter)
    {
        node *f = head;
        node *p = f;
        int i = 1;
        while (i < pos)
        {
            p = f;
            f = f->next;
            i++;
        }
        p->next = f->next;
        delete f;
        counter--;
    }
}

// عرض محتوى القائمة المرتبطة
void display()
{
    node *cur = head;
    while (cur != NULL)
    {
        cout << cur->item << " ";
        cur = cur->next;
    }
    cout << "\n";
}

// دالة main تحتوي على القائمة الرئيسية للتفاعل مع المستخدم
int main()
{
    while (true)
    {
        // عرض الخيارات الممكنة للمستخدم
        cout << "Choose operation:\n"
             << "1. Append\n"
             << "2. Prepend\n"
             << "3. Insert After\n"
             << "4. Delete from Front\n"
             << "5. Delete from End\n"
             << "6. Delete After\n"
             << "7. Display\n"
             << "8. Exit\n";

        int choice, value, key;
        cin >> choice;

        // تنفيذ العملية المختارة
        switch (choice)
        {
        case 1:
            cout << "Enter value to append: ";
            cin >> value;
            insert_from_back(value);
            break;

        case 2:
            cout << "Enter value to prepend: ";
            cin >> value;
            insert_from_back(value);
            break;

        case 3:
            cout << "Enter key after which to insert: ";
            cin >> key;
            cout << "Enter value to insert: ";
            cin >> value;
            insertpos(key, value);
            break;

        case 4:
            delete_front();
            break;

        case 5:
            delete_back();
            break;

        case 6:
            cout << "Enter key after which to delete: ";
            cin >> key;
            deletpos(key);
            break;

        case 7:
            display();
            break;

        case 8:
            return 0;

        default:
            cout << "Invalid choice\n";
        }
    }
}