#include <iostream>

// 定义循环链表节点结构体
struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(this) {} // 构造函数，初始化时指向自身形成循环
};

// 定义循环链表类
class CircularLinkedList {
private:
    Node* head; // 链表的头指针

public:
    CircularLinkedList() {
        head = nullptr; // 初始化时头指针为nullptr
    }

    ~CircularLinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            traverseToLast(); // 移动到末尾
            head = head->next;
            delete temp;
        }
    }

    // 尾部添加节点
    void append(int value) {
        if (head == nullptr) {
            head = new Node(value);
        } else {
            Node* newNode = new Node(value);
            traverseToLast(); // 移动到末尾
            newNode->next = head; // 将新节点的next指向头节点
            head->prev = newNode; // 将头节点的prev指向新节点
        }
    }

    // 头部添加节点
    void prepend(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            newNode->next = newNode; // 形成循环
        } else {
            newNode->next = head; // 新节点指向头节点
            Node* last = traverseToLast(); // 移动到末尾
            last->next = newNode; // 末尾节点指向新节点
            head = newNode; // 更新头节点
        }
    }

    // 删除指定值的节点
    bool remove(int value) {
        if (head == nullptr) return false;

        Node* current = head;
        do {
            if (current->data == value) {
                if (current->next == head) { // 如果是末尾节点
                    traverseToLast();
                    head->prev->next = head;
                    head->prev = head->prev->prev;
                } else {
                    current->prev->next = current->next;
                    if (current == head) { // 如果是头节点
                        head = current->next;
                    }
                }
                delete current;
                return true;
            }
            current = current->next;
        } while (current != head);
        return false;
    }

    // 查找节点
    Node* find(int value) {
        Node* current = head;
        if (head != nullptr) {
            do {
                if (current->data == value) {
                    return current;
                }
                current = current->next;
            } while (current != head);
        }
        return nullptr;
    }

    // 打印链表
    void print() {
        Node* current = head;
        if (head != nullptr) {
            do {
                std::cout << current->data << " <-> ";
                current = current->next;
            } while (current != head);
            std::cout << "head" << std::endl;
        }
    }

private:
    // 辅助函数：移动到链表末尾
    Node* traverseToLast() {
        if (head != nullptr) {
            Node* current = head;
            while (current->next != head) {
                current = current->next;
            }
            return current;
        }
        return nullptr;
    }
};

int main() {
    CircularLinkedList list;
    list.append(1);
    list.append(2);
    list.prepend(0);

    list.print(); // 应该显示 0 <-> 1 <-> 2 <-> head

    list.remove(1);
    list.print(); // 应该显示 0 <-> 2 <-> head

    return 0;
}