#include<iostream>
using namespace std;

// 節(jié)點類型聲明
struct Node
{
    int date;
    Node* last;  // 前驅(qū)節(jié)點
    Node* next;  // 后繼節(jié)點
};

class DList
{
private:
    // 成員變量
    Node* phead;

public:
    // 構(gòu)造函數(shù)
    DList() : phead(nullptr) {}

    // 析構(gòu)函數(shù)
    ~DList()
    {
        while (phead != NULL)
        {
            PopFront();
        }
    }

    // 創(chuàng)建節(jié)點
    Node* CreateNode(int x)
    {
        Node* node = new Node;
        node->date = x;
        node->last = NULL;
        node->next = NULL;
        return node;
    }

    // 打印鏈表
    void PrintList()
    {
        Node* cur = phead;
        while (cur)
        {
            cout << cur->date << "<-->";  // 雙向箭頭表示雙鏈表
            cur = cur->next;
        }
        cout << "NULL" << endl;
    }

    // 頭插法
    void PushFront(int x)
    {
        Node* newnode = CreateNode(x);
        if (phead == NULL)
        {
            phead = newnode;
        }
        else
        {
            newnode->next = phead;
            phead->last = newnode;
            phead = newnode;
        }
    }

    // 尾插法
    void PushBack(int x)
    {
        Node* newnode = CreateNode(x);
        if (phead == NULL)
        {
            phead = newnode;
        }
        else
        {
            Node* tail = phead;
            while (tail->next != NULL)
            {
                tail = tail->next;
            }
            tail->next = newnode;
            newnode->last = tail;
        }
    }

    // 頭刪法
    void PopFront()
    {
        if (phead == NULL)
        {
            cout << "鏈表為空，無法進行刪除操作！" << endl;
        }
        else
        {
            Node* del = phead;
            phead = del->next;
            if (phead != NULL)
            {
                phead->last = NULL;
            }
            delete del;
            del = NULL;
        }
    }

    // 尾刪法
    void PopBack()
    {
        if (phead == NULL)
        {
            cout << "鏈表為空，無法進行刪除操作！" << endl;
        }
        else
        {
            if (phead->next == NULL)  // 只有一個節(jié)點
            {
                delete phead;
                phead = NULL;
            }
            else
            {
                Node* tail = phead;
                while (tail->next != NULL)
                {
                    tail = tail->next;
                }
                tail->last->next = NULL;
                delete tail;
                tail = NULL;
            }
        }
    }
     //指定元素后插入
    void InsertAfter(int v, int x)
    {
        Node* node = phead;
        while (node != NULL && node->date != v)
        {
            node = node->next;
        }

        if (node == NULL)
        {
            cout << "未找到值為 " << v << " 的節(jié)點，無法插入!" << endl;
            return;
        }

        Node* newnode = CreateNode(x);
        newnode->last = node;
        newnode->next = node->next;

        if (node->next != NULL)
        {
            node->next->last = newnode;
        }

        node->next = newnode;
    }

    // 根據(jù)值刪除節(jié)點
    void PopValue(int value)
    {
        if (phead == NULL)
        {
            cout << "鏈表為空，無法進行刪除操作！" << endl;
            return;
        }
        Node* cur = phead;
        while (cur != NULL)
        {
            if (cur->date == value)
            {
                // 刪除節(jié)點
                if (cur->last != NULL)
                {
                    cur->last->next = cur->next;
                }
                else
                {
                    // 刪除的是頭節(jié)點
                    phead = cur->next;
                }

                if (cur->next != NULL)
                {
                    cur->next->last = cur->last;
                }
                delete cur;
                cur = NULL;
                cout << "刪除節(jié)點 " << value << " 成功！" << endl;
                return;
            }
            cur = cur->next;
        }
        cout << "未找到值為 " << value << " 的節(jié)點！" << endl;
    }
};

int main()
{
    DList ls1;
    ls1.PushBack(1);
    ls1.PushBack(2);
    ls1.PushBack(3);
    ls1.PushBack(4);
    ls1.PushBack(5);
    ls1.PrintList();

    ls1.PopFront();
    ls1.PopBack();
    ls1.PushFront(9);
    ls1.PrintList();

    ls1.InsertAfter(9,7);
    ls1.PrintList();

    ls1.PopValue(4);
    ls1.PrintList();
    return 0;
}