#include <iostream>
using namespace std;

/* ساختار اصلی گره (Node) در لیست پیوندی */
struct Node {
    int data;    // ذخیره داده در هر گره
    Node* next;  // اشاره‌گر به گره بعدی
};

/* تابع اضافه کردن گره جدید به انتهای لیست */
void addnode(Node* &head) {
    cout << "Enter Node Data : ";
    int x;
    cin >> x;  // دریافت داده از کاربر
    
    // ایجاد گره جدید
    Node* newnode = new Node;
    newnode->data = x;
    newnode->next = NULL;
    
    // اگر لیست خالی باشد، گره جدید را به عنوان سرلیست قرار می‌دهیم
    if (head == NULL) {
        head = newnode;
    }
    // در غیر این صورت به انتهای لیست می‌رویم و گره جدید را اضافه می‌کنیم
    else {
        Node* current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newnode;
    }
}

/* تابع اضافه کردن گره به ابتدای لیست */
void addtohead(Node* &head) {
    cout << "Enter Node Data to First : ";
    int x;
    cin >> x;  // دریافت داده از کاربر
    
    // ایجاد گره جدید
    Node* newnode = new Node;
    newnode->data = x;
    newnode->next = head;  // گره جدید به سرلیست فعلی اشاره می‌کند
    head = newnode;        // سرلیست جدید، گره جدید است
}

/* تابع اضافه کردن گره قبل از آخرین گره لیست */
void addbeforlast(Node* &head) {
    cout << "Enter Node Data Before Last : ";
    int x;
    cin >> x;  // دریافت داده از کاربر
    
    Node* newnode = new Node;
    newnode->data = x;
    
    // اگر لیست خالی باشد یا فقط یک گره داشته باشد
    if (head == NULL || head->next == NULL) {
        cout << "nodes less than 2" << endl;
        return;
    }
    
    // پیمایش تا رسیدن به گره ماقبل آخر
    Node* current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    
    // قرار دادن گره جدید قبل از آخرین گره
    newnode->next = current->next;
    current->next = newnode;
}

/* تابع جستجوی مقدار در لیست */
bool searchValue(Node* head) {
    cout << "Enter Data to Search : ";
    int x;
    cin >> x;  // دریافت داده از کاربر
    
    Node* current = head;
    
    // پیمایش لیست تا پیدا شدن مقدار یا رسیدن به انتها
    while (current != NULL) {
        if (current->data == x) {
            return true;  // مقدار پیدا شد
        }
        current = current->next;
    }
    return false;  // مقدار یافت نشد
}

/* تابع حذف گره با مقدار مشخص */
void deletenode(Node* &head) {
    cout << "Enter Node Value to Delete : ";
    int x;
    cin >> x;  // دریافت داده از کاربر
    
    Node* current = head;
    Node* prev = NULL;
    
    // اگر لیست خالی باشد
    if (head == NULL) {
        return;
    }
    
    // اگر گره مورد نظر اولین گره باشد
    if (current != NULL && current->data == x) {
        head = current->next;
        delete current;
        return;
    }
    
    // پیمایش برای یافتن گره مورد نظر
    while (current != NULL && current->data != x) {
        prev = current;
        current = current->next;
    }
    
    // اگر گره پیدا نشد
    if (current == NULL) {
        return;
    }
    
    // حذف گره با اتصال گره قبلی به گره بعدی
    prev->next = current->next;
    delete current;
}

/* تابع نمایش تمام گره‌های لیست */
void printnode(Node* &head) {
    if (head == NULL) {
        cout << "List is Empty" << endl;
    }
    else {
        Node* current = head;
        while (current != NULL) {
            cout << current->data << endl;  // چاپ داده گره فعلی
            current = current->next;        // حرکت به گره بعدی
        }
    }
}

/* تابع اصلی برنامه */
int main(int argc, char** argv) {
    // ایجاد سه گره اولیه
    Node* node1 = new Node{10, NULL};
    Node* node2 = new Node{20, NULL};
    Node* node3 = new Node{30, NULL};
    
    // اتصال گره‌ها به هم
    Node* head = node1;
    node1->next = node2;
    node2->next = node3;
    
    // فراخوانی توابع مختلف
    addnode(head);       // اضافه کردن گره به انتها
    addnode(head);       // اضافه کردن گره دیگر به انتها
    addtohead(head);     // اضافه کردن گره به ابتدا
    addbeforlast(head);  // اضافه کردن گره قبل از آخر
    printnode(head);     // نمایش لیست
    
    cout << searchValue(head);  // جستجوی مقدار در لیست
    
    deletenode(head);    // حذف گره با مقدار مشخص
    printnode(head);     // نمایش لیست پس از حذف
    
    return 0;
}

#include <iostream>
using namespace std;

/* ساختار اصلی گره در لیست دوطرفه */
struct Node {
    int data;    // داده ذخیره شده در گره
    Node* prev;  // اشاره‌گر به گره قبلی
    Node* next;  // اشاره‌گر به گره بعدی
};

/* اشاره‌گرهای سر (اولین گره) و دم (آخرین گره) لیست */
Node* head = NULL; // همیشه به اولین گره اشاره می‌کند
Node* tail = NULL; // همیشه به آخرین گره اشاره می‌کند

/* تابع اضافه کردن گره به ابتدای لیست */
void addToFirst(int x) {
    // 1. ایجاد گره جدید
    Node* newNode = new Node;
    newNode->data = x;
    newNode->prev = NULL; // چون اولین گره است، قبلی ندارد
    newNode->next = head; // بعدی آن گره فعلی اول است

    // 2. اگر لیست خالی نبود، گره اول قبلی را به جدید اشاره می‌کنیم
    if (head != NULL) {
        head->prev = newNode;
    } 
    // 3. اگر لیست خالی بود، دم هم همان گره جدید است
    else {
        tail = newNode;
    }
    
    // 4. سرلیست را به گره جدید تنظیم می‌کنیم
    head = newNode;
}

/* تابع اضافه کردن گره به انتهای لیست */
void addToEnd(int x) {
    // 1. ایجاد گره جدید
    Node* newNode = new Node;
    newNode->data = x;
    newNode->next = NULL; // چون آخرین گره است، بعدی ندارد
    newNode->prev = tail; // قبلی آن گره فعلی آخر است

    // 2. اگر لیست خالی نبود، گره آخر بعدی را به جدید اشاره می‌کنیم
    if (tail != NULL) {
        tail->next = newNode;
    } 
    // 3. اگر لیست خالی بود، سر هم همان گره جدید است
    else {
        head = newNode;
    }

    // 4. دم لیست را به گره جدید تنظیم می‌کنیم
    tail = newNode;
}

/* تابع اضافه کردن گره بعد از یک مقدار خاص */
void addAfter(int value, int x) {
    // 1. پیدا کردن گره مورد نظر
    Node* current = head;
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    
    // اگر مقدار پیدا نشد، برگرد
    if (current == NULL) return;

    // 2. ایجاد گره جدید
    Node* newNode = new Node;
    newNode->data = x;
    newNode->next = current->next; // بعدی جدید، بعدی گره فعلی است
    newNode->prev = current;       // قبلی جدید، خود گره فعلی است

    // 3. اگر گره فعلی آخر نبود، گره بعدی آن را به جدید اشاره می‌کنیم
    if (current->next != NULL) {
        current->next->prev = newNode;
    } 
    // اگر آخر بود، دم را به جدید تنظیم می‌کنیم
    else {
        tail = newNode;
    }

    // 4. بعدی گره فعلی را به جدید اشاره می‌کنیم
    current->next = newNode;
}

/* تابع اضافه کردن گره قبل از یک مقدار خاص */
void addBefore(int value, int x) {
    // 1. پیدا کردن گره مورد نظر
    Node* current = head;
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    
    // اگر مقدار پیدا نشد، برگرد
    if (current == NULL) return;

    // 2. ایجاد گره جدید
    Node* newNode = new Node;
    newNode->data = x;
    newNode->next = current;       // بعدی جدید، خود گره فعلی است
    newNode->prev = current->prev; // قبلی جدید، قبلی گره فعلی است

    // 3. اگر گره فعلی اول نبود، گره قبلی آن را به جدید اشاره می‌کنیم
    if (current->prev != NULL) {
        current->prev->next = newNode;
    } 
    // اگر اول بود، سر را به جدید تنظیم می‌کنیم
    else {
        head = newNode;
    }

    // 4. قبلی گره فعلی را به جدید اشاره می‌کنیم
    current->prev = newNode;
}

/* تابع چاپ لیست از ابتدا به انتها */
void printForward() {
    cout << "لیست از ابتدا: ";
    Node* current = head;
    while (current != NULL) {
        cout << current->data << " <-> ";
        current = current->next;
    }
    cout << "NULL" << endl;
}

/* تابع چاپ لیست از انتها به ابتدا */
void printBackward() {
    cout << "لیست از انتها: ";
    Node* current = tail;
    while (current != NULL) {
        cout << current->data << " <-> ";
        current = current->prev;
    }
    cout << "NULL" << endl;
}

void hazf(int x)
{
	Node* current=head;
	while (current!=NULL && current->data!=x) // اگر لیست خالی نباشد
		current = current->next; // پیمایش تا آخرین گره
	if (current == NULL) // اگر لیست خالی باشد بازگشت به برنامه اصلی
		return;
	//اگر در اولین گره مقدار را پیدا کرده 
	if (current->prev == NULL)	head = current->next;
	// اگر در آخرین گره مقدار را پیدا کرد
	if (current->next == NULL)  tail = current->prev;
	// اگر در گره های وسط مقدار را پیدا کرد
	if (current->prev != NULL && current->prev != NULL)
	{
		current->prev->next = current->next;
		current->next->prev = current->prev;
	}
	delete current;
}

/* تابع اصلی */
int main() {
    addToEnd(10);    // اضافه کردن 10 به انتها
    addToEnd(20);    // اضافه کردن 20 به انتها
    addToEnd(30);    // اضافه کردن 30 به انتها
    addToFirst(5);   // اضافه کردن 5 به ابتدا
    addAfter(20, 25); // اضافه کردن 25 بعد از 20
    addBefore(10, 8); // اضافه کردن 8 قبل از 10
    
    printForward();  // چاپ از اول به آخر
    printBackward(); // چاپ از آخر به اول
    
    hazf(20);
    printForward();
    return 0;
}