// 定义一个节点，此为 C++ 语法
struct Node
{
    int data = 0;
    Node* next = nullptr;
    Node* prev = nullptr;
};

// DoubleCircularLinkList.h
#pragma once
#include <iostream>
using namespace std;

struct Node 
{
    int data;
    Node* prev;
    Node* next;
    Node(int d) : data(d), prev(nullptr), next(nullptr) {}
};

class LoopDLinkList 
{
public:
    LoopDLinkList();
    ~LoopDLinkList();
    // 判断链表是否为空
    bool isEmpty();
    // 得到链表长度
    int length();
    // 数据添加到链表头部
    void prepend(int data);
    // 数据添加到链表尾部
    void append(int data);
    // 数据插入到链表任意位置, 第一个数据元素 pos=1
    bool insert(int pos, int data);
    // 搜索数值, 返回节点和位置, 没找到返回nullptr
    Node* find(int data, int& pos);
    // 删除节点
    bool remove(int pos);
    // 遍历链表
    void display();
private:
    Node* m_head;
    Node* m_tail;
    int m_length;
};

// DoubleCircularLinkList.cpp
#include "DoubleCircularLinkList.h"
#include <iostream>
using namespace std;

LoopDLinkList::LoopDLinkList() : m_head(new Node(0)), m_length(0)
{
    m_head->prev = m_head;
    m_head->next = m_head;
    m_tail = m_head;
}

LoopDLinkList::~LoopDLinkList()
{
    Node* current = m_head->next;
    while (current != m_head) 
    {
        Node* temp = current;
        current = current->next;
        cout << "释放链表节点: " << temp->data << endl;
        delete temp;
    }
    delete m_head;
}

bool LoopDLinkList::isEmpty()
{
    return m_head->next == m_head;
}

int LoopDLinkList::length()
{
    return m_length;
}

void LoopDLinkList::prepend(int data)
{
    Node* newNode = new Node(data);
    newNode->next = m_head->next; 
    newNode->prev = m_head; 
    m_head->next->prev = newNode; 
    if (isEmpty())
    {
        m_tail = newNode; 
    }
    m_head->next = newNode; 
    m_length++;
}

void LoopDLinkList::append(int data)
{
    Node* node = new Node(data);
    node->next = m_head->next;
    node->prev = m_head;
    node->next = m_tail->next;
    node->prev = m_tail;
    m_tail->next = node;
    m_head->prev = node;
    m_tail = node;
    m_length++;
}

bool LoopDLinkList::insert(int pos, int data)
{
    if (pos<1 || pos>length() + 1)
    {
        cout << "链表插入数据失败, 无效的位置" << endl;
        return false;
    }
    Node* pNode = new Node(data);
    if (pos == 1)
    {
        prepend(data);
        return true;
    }
    else
    {
        Node* p = m_head;
        int j = 0;
        while (j < pos - 1)
        {
            p = p->next;
            j++;
        }
        Node* pNode = new Node(data);
        pNode->next = p->next;
        pNode->prev = p;
        p->next->prev = pNode;
        if (p->next == m_head)
        {
            m_tail = pNode;
        }
        p->next = pNode;
        m_length++;
    }
    return true;
}

Node* LoopDLinkList::find(int data, int& pos)
{
    pos = 0;
    Node* p = m_head;
    do
    {
        p = p->next;
        pos++;
    }while (p != m_head && p->data != data);
    return p;
}

bool LoopDLinkList::remove(int pos)
{
    if (pos<1 || pos>length())
    {
        cout << "删除链表节点失败, 位置无效" << endl;
        return false;
    }
    if (pos == 1)
    {
        Node* p = m_head;
        m_head = m_head->next;
        m_head->prev = p->prev;
        m_tail->next = m_head;
        delete p;
    }
    else
    {
        Node* p = m_head;
        int j = 0; 
        while (j < pos - 1)
        {
            p = p->next;
            j++;
        }
        Node* delNode = p->next;
        p->next = delNode->next;
        p->next->prev = p; 
        if (p->next == m_head)
        {
            m_tail = p;
        }
        delete delNode;
    }
    m_length--;

    return true;
}

void LoopDLinkList::display()
{
    if (m_head->next == m_head)
    {
        cout << "空链表" << endl;
        return;
    }
    cout << "从头到尾遍历: " << endl;
    for (Node* item = m_head->next; item != m_head; item = item->next)
    {
        cout << item->data << " ";
    }
    cout << endl;

    cout << "从尾到头遍历: " << endl;
    for (Node* item = m_tail; item != m_head; item = item->prev)
    {
        cout << item->data << " ";
    }
    cout << endl;
}

int main() 
{
    LoopDLinkList lst;
    cout << "是否为空链表: " << lst.isEmpty() << endl;
    lst.prepend(18);
    lst.prepend(19);
    lst.insert(1, 12);
    lst.append(8);
    lst.insert(2, 7);
    lst.insert(2, 6);
    lst.insert(1, 5);
    lst.insert(2, 4);
    lst.append(3);
    lst.prepend(9);
    lst.display();
    cout << "当前链表的长度为: " << lst.length() << endl;
    cout << "========== 测试搜索和删除=========" << endl;
    LoopDLinkList lst1;
    lst1.insert(1, 10);
    lst1.insert(2, 20);
    lst1.insert(3, 30);
    lst1.insert(4, 40);
    lst1.insert(5, 50);
    lst1.display();
    int pos;
    Node* node = lst1.find(10, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(30, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(50, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();
    cout << "当前链表的长度为: " << lst1.length() << endl;
    return 0;
}

是否为空链表: 1
从头到尾遍历:
9 5 4 12 6 7 19 18 8 3
从尾到头遍历:
3 8 18 19 7 6 12 4 5 9
当前链表的长度为: 10
========== 测试搜索和删除=========
从头到尾遍历:
10 20 30 40 50
从尾到头遍历:
50 40 30 20 10
搜索到的节点位置: 1, 值为: 10
从头到尾遍历:
20 30 40 50
从尾到头遍历:
50 40 30 20
搜索到的节点位置: 2, 值为: 30
从头到尾遍历:
20 40 50
从尾到头遍历:
50 40 20
搜索到的节点位置: 3, 值为: 50
从头到尾遍历:
20 40
从尾到头遍历:
40 20
当前链表的长度为: 2
释放链表节点: 20
释放链表节点: 40
释放链表节点: 9
释放链表节点: 5
释放链表节点: 4
释放链表节点: 12
释放链表节点: 6
释放链表节点: 7
释放链表节点: 19
释放链表节点: 18
释放链表节点: 8
释放链表节点: 3