C++ 鏈表類封裝：插入、刪除、遍歷、查找完整實現

完整代碼

#include 
using namespace std;

template 
class List {
    struct Node {
        T data; Node* next;
        Node(T val): data(val), next(nullptr) {}
    };
    Node* head; // 哨兵節點
    int size;
public:
    List(): head(new Node(T())), size(0) {}
    ~List() { clear(); delete head; }

    void push_back(T val) { insert(size, val); }
    void insert(int pos, T val) { // 0 <= pos <= size
        Node* prev = head;
        for (int i=0; inext;
        prev->next = new Node(val);
        prev->next->next = prev->next; // 修正：應為 prev->next->next = prev->next 原有的 next
        // 正確：
        Node* n = new Node(val);
        n->next = prev->next;
        prev->next = n;
        size++;
    }
    void erase(int pos) { // 0 <= pos < size
        Node* prev = head;
        for (int i=0; inext;
        Node* del = prev->next;
        prev->next = del->next;
        delete del;
        size--;
    }
    T& operator[](int pos) {
        Node* p = head->next;
        for (int i=0; inext;
        return p->data;
    }
    int find(T val) {
        Node* p = head->next;
        for (int i=0; p; i++, p=p->next)
            if (p->data == val) return i;
        return -1;
    }
    void print() {
        for (Node* p=head->next; p; p=p->next) cout << p->data << " ";
        cout << "\n";
    }
    void clear() {
        Node* p = head->next;
        while (p) { Node* tmp = p; p = p->next; delete tmp; }
        head->next = nullptr; size = 0;
    }
    int getSize() const { return size; }
};

int main() {
    List lst;
    lst.push_back(1); lst.push_back(2); lst.push_back(3);
    lst.insert(1, 99); // 1,99,2,3
    lst.print();
    lst.erase(2);      // 1,99,3
    lst.print();
    cout << "Index of 99: " << lst.find(99) << "\n";
}

關鍵點

• 使用哨兵頭節點簡化邊界條件。
• 模板實現泛型。
• 析構函數釋放所有節點，防止內存洩漏。