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

    Node(int val) : data(val), next(nullptr) {} // 构造函数
};

// 定义单向链表类
class LinkedList {
private:
    Node* head; // 链表的头指针

public:
    LinkedList() : head(nullptr) {} // 构造函数

    // 析构函数，释放链表内存
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }

    // 在链表末尾添加新节点
    void append(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }

    // 在链表头部添加新节点
    void prepend(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

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

    // 删除指定值的节点
    bool remove(int value) {
        Node* current = head;
        Node* previous = nullptr;

        while (current != nullptr) {
            if (current->data == value) {
                if (previous == nullptr) {
                    head = current->next;
                } else {
                    previous->next = current->next;
                }
                delete current;
                return true;
            }
            previous = current;
            current = current->next;
        }
        return false;
    }

    // 更新节点的值
    bool update(int oldValue, int newValue) {
        Node* node = find(oldValue);
        if (node != nullptr) {
            node->data = newValue;
            return true;
        }
        return false;
    }

    // 打印链表
    void print() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "null" << endl;
    }
    
    // 在指定节点之后插入新节点
    bool insertAfter(Node* prevNode, int value) {
        if (prevNode == nullptr) {
            std::cout << "The given previous node cannot be NULL" << std::endl;
            return false;
        }

        Node* newNode = new Node(value);
        newNode->next = prevNode->next;
        prevNode->next = newNode;

        return true;
    }
};

int main() {
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.prepend(0);
    list.print(); // 打印链表

    list.remove(2);
    list.print(); // 打印删除节点后的链表

    list.update(0, -1);
    list.print(); // 打印更新节点后的链表
    
	// 找到节点3，然后在这个节点之后插入节点4
    Node* nodeToInsertAfter = list.find(3);
    if (nodeToInsertAfter != nullptr) {
        list.insertAfter(nodeToInsertAfter, 4);
    }

    list.print(); // 打印链表
    return 0;
}