C++ 單鏈表模板類實現與操作詳解

設計思路

採用帶頭節點的單鏈表結構，頭節點 `first` 的 `data` 域存儲鏈表長度，`last` 指向尾節點，實現 O(1) 尾插。所有操作基於模板 `Type`，支援任意可比較類型。

節點與類定義

template <class Type>
class ListNode {
    friend class List<Type>;
    Type data;
    ListNode *next;
    ListNode(Type d = Type(), ListNode *n = nullptr) 
        : data(d), next(n) {}
};

template <class Type>
class List {
    ListNode<Type> *first, *last;
public:
    List() { first = last = Buynode(); }
    ~List() { destroy(); }
    // 13 項核心操作...
protected:
    ListNode<Type>* Buynode(Type x = Type()) {
        return new ListNode<Type>(x);
    }
};

核心操作實現精華

尾插 O(1)

void push_back(const Type &x) {
    ListNode<Type> *s = Buynode(x);
    last->next = s;
    last = s;
    first->data++; // 長度++
}

頭插 O(1)

void push_front(const Type &x) {
    ListNode<Type> *s = Buynode(x);
    s->next = first->next;
    first->next = s;
    if (first == last) last = s; // 空表情況
    first->data++;
}

有序插入（按值）

void insert_val(const Type &x) {
    ListNode<Type> *s = Buynode(x);
    ListNode<Type> *p = first->next;
    if (!p || p->data > s->data) { push_front(s->data); return; }
    if (last->data < s->data) { push_back(s->data); return; }
    while (p->next && p->next->data < x) p = p->next;
    s->next = p->next;
    p->next = s;
    first->data++;
}

反轉（就地原地算法）

void reserv() {
    ListNode<Type> *p = first->next;
    if (!p) return;
    ListNode<Type> *curr = p->next;
    p->next = nullptr;
    last = p;
    while (curr) {
        ListNode<Type> *tmp = curr->next;
        curr->next = p;
        p = curr;
        curr = tmp;
    }
    first->next = p;
}

冒泡排序（數值交換法）

void sort() {
    for (ListNode<Type> *s = first->next; s->next; s = s->next)
        for (ListNode<Type> *p = s; p->next; p = p->next)
            if (s->data > p->next->data)
                swap(s->data, p->next->data);
}

測試主程式

同順序表，提供完整的菜單驅動測試框架，驗證所有 13 項操作。

關鍵點總結

改進方向

• 實現雙向鏈表，支援 O(1) 尾刪與反向遍歷
• 添加迭代器，兼容 STL 算法生態
• 引入智能指針 (`unique_ptr`) 自動管理記憶體
• 提供拷貝/移動語義，符合 Rule of Five