// DoublyLinkedList.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node* next;
    Node* prev;
};
struct Dlist
{
    Node* head;
    Node* tail;
};

void Initialize(Dlist& d) 
{
    d.head = d.tail = NULL;
}
bool checkEmpty(Dlist d)
{
    if (d.head == NULL) {
        return true;
    }
    else {
        return false;
    }
}
Node* findIelement(Dlist d, int i)
{
    int count = 0;
    for (Node* p = d.head; p != NULL;p = p->next) {
        if (count == i)
            return p;
        count++;
    }
    return NULL;
}
Node* findDataX(Dlist d, int x) {
    for (Node* p = d.head; p != NULL;p = p->next) {
        if (p->data = x)
            return p;
    }
    return NULL;
}
Node* findLastelement(Dlist d)
{
    return d.tail;
}
Node* CreatNode(int n)
{
    Node* p = new Node;
    p->data = n;
    p->next = NULL;
    p->prev = NULL;
    return p;
}
void addHead(Dlist& d)
{
    int x;
    cout << "Enter x: ";
    cin >> x;
    Node* p = CreatNode(x);
    if (d.head == NULL)
    {
        d.head = d.tail = p;
    }
    else
    {
        p->next = d.head;
        d.head->prev = p;            
        d.head = p;
    }
}
void addTail(Dlist& d) {
    int x;
    cout << "Enter x: ";
    cin >> x;
    Node* p = CreatNode(x);
    if (d.head == NULL)
    {
        d.head = d.tail = p;
    }
    else
    {
        d.tail->next = p;
        p->prev = d.tail;
        d.tail = p;
    }
}
void addMiddle(Dlist& d)
{
    int x;
    cout << "Enter x: ";
    cin >> x;
    Node* p = CreatNode(x);
    if (d.head == NULL)
    {
        d.head = d.tail = p;
    }
    else {
        Node* cur = d.head;
        while (cur->next != NULL && cur->next->data < p->data) {
            cur = cur->next;
        }
        Node* temp = cur->next;
        p->next = cur->next;
        p->prev = cur;
        cur->next = p;  
        temp->prev = p;
    }
}
void removeHead(Dlist& d)
{
    if (d.head == NULL) {
        cout << "EMPTY" << endl;
        return;
    }
    else {
        d.head = d.head->next;
        d.head->prev = NULL;
    }
}
void removeTail(Dlist& d)
{
    if (d.head == NULL) {
        cout << "EMPTY" << endl;
        return;
    }
    else {
        d.tail = d.tail->prev;
        d.head->next = NULL;
    }
}
void removeIelement(Dlist& d, int i) {
    if (d.head == NULL) {
        cout << "EMPTY" << endl;
        return;
    }
    else {
        int count = 0;
        Node* cur = d.head;
        while (cur != NULL) {
            Node* temp = cur->next;
            if (count == i) {
                Node* temp2 = temp->next;
                cur->next = temp->next;
                temp2->prev = cur;
            }
            count++;           
            cur = cur->next;
        }
    }
}
void removeDataX(Dlist& d)
{
    int x;
    cout << "Enter x: ";
    cin >> x;
    Node* p = CreatNode(x);
    if (d.head == NULL) {
        cout << "EMPTY" << endl;
        return;
    }
    else {
        Node* cur = d.head;
        while (cur != NULL) {
            Node* temp = cur->next;
            if (cur->data == p->data) {
                Node* temp2 = temp->next;
                cur->next = temp->next;
                temp2->prev = cur;
            }
            cur = cur->next;
        }
    }
}

int main()
{
    std::cout << "Hello World!\n";
}