資料結構基礎 (8) - 單向鏈表完整實作 (C++ Template)

為什麼需要鏈表？

結論：頻繁增刪、少量查詢 → 鏈表；頻繁查詢、少量增刪 → 陣列/向量。

節點定義

template <typename Type>
class Node {
    friend class MyList<Type>;
    template <typename T> friend ostream& operator<<(ostream&, const MyList<T>&);
private:
    Node(const Type& val) : data(val), next(nullptr) {}
    Type data;
    Node* next;
};

鏈表類別骨架

template <typename Type>
class MyList {
    template <typename T> friend ostream& operator<<(ostream&, const MyList<T>&);
public:
    MyList(); ~MyList();
    void insertFront(const Type&);
    void insert(const Type&, int index); // 1-based
    void remove(const Type&);
    bool isEmpty() const;
    void invert();           // 反轉
    void concatenate(const MyList<Type>&); // 串接另一串表
private:
    Node<Type>* first; // 指向哨兵節點
};

核心操作實作

建構/解構

MyList() { first = new Node<Type>(Type()); first->next = nullptr; }
~MyList() {
    Node<Type>* cur = first;
    while (cur) { Node<Type>* nxt = cur->next; delete cur; cur = nxt; }
}

頭插

void insertFront(const Type& val) {
    Node<Type>* n = new Node<Type>(val);
    n->next = first->next;
    first->next = n;
}

指定位置插入 (1-based)

void insert(const Type& val, int idx) {
    Node<Type>* prev = first;
    int cnt = 1;
    while (cnt < idx && prev->next) { prev = prev->next; ++cnt; }
    Node<Type>* n = new Node<Type>(val);
    n->next = prev->next;
    prev->next = n;
}

刪除所有值為 val 的節點

void remove(const Type& val) {
    if (isEmpty()) return;
    Node<Type>* prev = first;
    for (Node<Type>* cur = first->next; cur; ) {
        if (cur->data == val) {
            prev->next = cur->next;
            delete cur;
            cur = prev->next; // 繼續檢查下一個
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
}

判空

bool isEmpty() const { return first->next == nullptr; }

進階操作

鏈表反轉 (三指標法)

void invert() {
    if (isEmpty()) return;
    Node<Type>* cur = first->next;
    Node<Type>* prev = nullptr;
    while (cur) {
        Node<Type>* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    first->next = prev; // 新頭
}

串接另一鏈表 (深拷貝避免雙重釋放)

void concatenate(const MyList<Type>& other) {
    if (isEmpty()) { first = other.first; return; } // 注意：這裡為簡化直接指向，實務應深拷貝
    if (other.isEmpty()) return;
    Node<Type>* tail = first;
    while (tail->next) tail = tail->next;
    for (Node<Type>* src = other.first->next; src; src = src->next) {
        tail->next = new Node<Type>(src->data);
        tail = tail->next;
    }
}

輸出運算子重載

template <typename Type>
ostream& operator<<(ostream& os, const MyList<Type>& list) {
    for (Node<Type>* p = list.first->next; p; p = p->next) {
        os << p->data;
        if (p->next) os << " -> ";
    }
    return os;
}

測試主程式

int main() {
    MyList<int> a, b;
    for (int i=1;i<=5;++i) a.insert(i,i);
    a.remove(5);
    for (int i=6;i<=10;++i) b.insert(i,i-5);
    b.insertFront(5); b.insert(88,7);
    cout << "Before concat:\na: " << a << "\nb: " << b << "\n";
    a.concatenate(b);
    cout << "After concat:\na: " << a << "\nb: " << b << "\n";

    MyList<char> c;
    for (char ch='9'; ch>='0'; --ch) c.insertFront(ch);
    cout << "\nBefore invert: " << c;
    c.invert();
    cout << "\nAfter invert:  " << c;
    c.remove('5');
    cout << "\nAfter remove 5:" << c << "\n";
    return 0;
}

輸出範例

Before concat:
a: 1 -> 2 -> 3 -> 4
b: 5 -> 6 -> 88 -> 7 -> 8 -> 9 -> 10
After concat:
a: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 88 -> 7 -> 8 -> 9 -> 10
b: 5 -> 6 -> 88 -> 7 -> 8 -> 9 -> 10

Before invert: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
After invert:  0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
After remove 5: 0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9

關鍵筆記

• 哨兵節點簡化邊界條件 (頭插、空表皆同邏輯)。
• 刪除時 prev 不動、cur 前進，避免漏檢相鄰重複值。
• 反轉必須「先存 next、再改指標、再移動指標」。
• 串接必須深拷貝，否則析構時同一記憶體被 delete 兩次 → Crash。