#include <iostream>
#include <stdexcept>  // 用於異常處理
using namespace std;

// 定義鏈表節點結構體
template <typename T>
struct ListNode {
    T data;               // 數據域
    ListNode<T>* next;    // 指針域，指向下一個節點

    // 節點構造函數
    ListNode(T val) : data(val), next(nullptr) {}
};

// 單鏈表類封裝
template <typename T>
class SinglyLinkedList {
private:
    ListNode<T>* head;    // 頭節點指針（哨兵節點，不存儲數據）
    int size;             // 鏈表元素個數

public:
    // 構造函數：初始化空鏈表
    SinglyLinkedList() {
        head = new ListNode<T>(T());  // 頭節點（哨兵），數據域默認值
        size = 0;
    }

    // 析構函數：銷燬鏈表
    ~SinglyLinkedList() {
        clear();          // 清空所有節點
        delete head;      // 釋放頭節點
        head = nullptr;
    }

    // 1. 清空鏈表
    void clear() {
        ListNode<T>* curr = head->next;  // 從第一個有效節點開始
        while (curr != nullptr) {
            ListNode<T>* temp = curr;
            curr = curr->next;
            delete temp;  // 釋放當前節點
        }
        head->next = nullptr;
        size = 0;
    }

    // 2. 在鏈表尾部添加元素
    void push_back(T val) {
        ListNode<T>* newNode = new ListNode<T>(val);
        ListNode<T>* curr = head;
        // 找到最後一個節點
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = newNode;
        size++;
    }

    // 3. 在鏈表頭部添加元素
    void push_front(T val) {
        ListNode<T>* newNode = new ListNode<T>(val);
        newNode->next = head->next;  // 新節點指向原第一個節點
        head->next = newNode;        // 頭節點指向新節點
        size++;
    }

    // 4. 刪除指定值的第一個節點
    bool remove(T val) {
        ListNode<T>* prev = head;
        ListNode<T>* curr = head->next;
        while (curr != nullptr) {
            if (curr->data == val) {
                prev->next = curr->next;  // 跳過待刪除節點
                delete curr;              // 釋放內存
                size--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false;  // 未找到該值
    }

    // 5. 根據索引刪除節點（索引從0開始）
    bool removeAt(int index) {
        if (index < 0 || index >= size) {
            throw out_of_range("Index out of bounds");
        }
        ListNode<T>* prev = head;
        ListNode<T>* curr = head->next;
        for (int i = 0; i < index; i++) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = curr->next;
        delete curr;
        size--;
        return true;
    }

    // 6. 查找元素是否存在
    bool find(T val) const {
        ListNode<T>* curr = head->next;
        while (curr != nullptr) {
            if (curr->data == val) {
                return true;
            }
            curr = curr->next;
        }
        return false;
    }

    // 7. 獲取指定索引的元素（索引從0開始）
    T get(int index) const {
        if (index < 0 || index >= size) {
            throw out_of_range("Index out of bounds");
        }
        ListNode<T>* curr = head->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
        return curr->data;
    }

    // 8. 修改指定索引的元素
    bool set(int index, T val) {
        if (index < 0 || index >= size) {
            return false;
        }
        ListNode<T>* curr = head->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
        curr->data = val;
        return true;
    }

    // 9. 獲取鏈表長度
    int getSize() const {
        return size;
    }

    // 10. 判斷鏈表是否為空
    bool isEmpty() const {
        return size == 0;
    }

    // 11. 遍歷打印鏈表
    void print() const {
        ListNode<T>* curr = head->next;
        if (curr == nullptr) {
            cout << "Linked list is empty" << endl;
            return;
        }
        cout << "Linked list: ";
        while (curr != nullptr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "nullptr" << endl;
    }
};

// 測試代碼
int main() {
    // 創建int類型的鏈表
    SinglyLinkedList<int> list;

    // 測試添加元素
    list.push_back(10);
    list.push_back(20);
    list.push_front(5);
    list.print();  // 輸出：5 -> 10 -> 20 -> nullptr

    // 測試查找
    cout << "Find 10: " << boolalpha << list.find(10) << endl;  // true
    cout << "Find 30: " << boolalpha << list.find(30) << endl;  // false

    // 測試獲取元素
    cout << "Index 1: " << list.get(1) << endl;  // 10

    // 測試修改元素
    list.set(1, 15);
    list.print();  // 5 -> 15 -> 20 -> nullptr

    // 測試刪除元素
    list.remove(15);
    list.print();  // 5 -> 20 -> nullptr

    list.removeAt(1);
    list.print();  // 5 -> nullptr

    // 測試清空
    list.clear();
    list.print();  // Linked list is empty

    // 測試邊界情況
    try {
        list.get(0);  // 拋出異常
    } catch (const out_of_range& e) {
        cout << "Exception: " << e.what() << endl;
    }

    return 0;
}