#include <iostream>
using namespace std;
// 定义双向链表节点结构体
struct Node {
    int data;
    Node* prev; // 指向前一个节点的指针
    Node* next; // 指向下一个节点的指针

    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 定义双向链表类
class DoublyLinkedList {
private:
    Node* head; // 链表的头指针
    Node* tail; // 链表的尾指针

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    ~DoublyLinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 在头部插入节点
    void prepend(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    // 在尾部插入节点
    void append(int value) {
        Node* newNode = new Node(value);
        if (tail == nullptr) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    // 在指定节点之后插入新节点
    bool insertAfter(Node* prevNode, int value) {
        if (prevNode == nullptr) return false;
        Node* newNode = new Node(value);
        newNode->next = prevNode->next;
        newNode->prev = prevNode;
        if (prevNode->next != nullptr) {
            prevNode->next->prev = newNode;
        } else {
            tail = newNode; // 如果prevNode是尾部节点，更新tail指针
        }
        prevNode->next = newNode;
        return true;
    }

    // 删除指定节点
    bool remove(Node* node) {
        if (node == nullptr) return false;
        if (node->prev != nullptr) {
            node->prev->next = node->next;
        } else {
            head = node->next; // 如果node是头节点，更新head指针
        }
        if (node->next != nullptr) {
            node->next->prev = node->prev;
        } else {
            tail = node->prev; // 如果node是尾节点，更新tail指针
        }
        delete node;
        return true;
    }

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

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

int main() {
    DoublyLinkedList list;
    list.append(1);
    list.append(3);
    list.append(5);

    // 在头部插入节点
    list.prepend(0);

    // 在节点1之后插入节点2
    Node* node1 = list.find(1);
    if (node1 != nullptr) {
        list.insertAfter(node1, 2);
    }

    // 打印链表
    list.print(); // 应该显示 0 <-> 1 <-> 2 <-> 3 <-> 5 <-> null

    // 删除节点2
    Node* node2 = list.find(2);
    if (node2 != nullptr) {
        list.remove(node2);
    }

    // 再次打印链表
    list.print(); // 应该显示 0 <-> 1 <-> 3 <-> 5 <-> null

    return 0;
}