C++ 單鏈表模板深度解析：從節點設計到多項式運算符重載

單鏈表是數據結構皇冠上的明珠。本文構建一個簡潔、實用、擴展性強的單鏈表模板，並展示其在多項式運算中的強大表達力。

節點類：極簡設計

template <class Type> class Node {
public:
    Type data;
    Node<Type> *link;
    Node() : data(Type()), link(NULL) {}
    Node(const Type &item) : data(item), link(NULL) {}
    Node(const Type &item, Node<Type> *p) : data(item), link(p) {}
};

關鍵修正：缺省構造函數用 Type() 而非 NULL，支援任意類型（含結構體）。成員全開放，因鏈表類未對外暴露節點指針，封裝性由外層把控。

單鏈表類：游標式接口

採用 first（頭節點）、current（當前）、prior（前驅）、last（尾節點）四指針，提供豐富操作：

• 基本操作：MakeEmpty、IsEmpty、Length、Get/Put、Next、First/End、Locate、Find
• 插入刪除：Insert（當前後）、InsertBefore（當前前）、Remove（刪當前）、RemoveAfter（刪下一）
• 輸出運算符重載：遍歷輸出
• 受保護擴展接口：LastInsert（O(1) 尾插，供隊列用）、Initialize、節點指針級操作（pGet、pNext、Insert(Node*) 等），供派生類高效擴展

屏蔽了返回節點指針的公有接口，簡化使用；擴展接口置於 protected，兼顧封裝與性能。

賦值運算符與拷貝構造：讓容器可複製

operator = (const List<Type> &l) {
    MakeEmpty();
    for (Node<Type> *p = l.first->link; p; p = p->link) LastInsert(p->data);
}
List(const List<Type> &l) {
    first = current = last = new Node<Type>(); prior = NULL;
    for (Node<Type> *p = l.first->link; p; p = p->link) LastInsert(p->data);
}

解決了原書「游標類」設計導致的賦值困境，支援 a = b + c * d 等鏈式表達式。

多項式運算：運算符重載實戰

基於單鏈表實現多項式 Polynomial，項結構 Term{coef, exp}。重載 +、*：

friend Polynomial operator+(Polynomial &A, Polynomial &B) {
    Polynomial tA = A, tB = B; PolyAdd(tA, tB); return tA;
}
friend Polynomial operator*(Polynomial &A, Polynomial &B) {
    Polynomial tA, tB;
    for (Node<Term> *pA = A.pGetFirst()->link; pA; pA = pA->link)
        for (Node<Term> *pB = B.pGetFirst()->link; pB; pB = pB->link) {
            tB.LastInsert(Term(pA->data.coef * pB->data.coef,
                               pA->data.exp + pB->data.exp));
        }
    PolyAdd(tA, tB); tB.Initialize(); // 重置 tB 供下輪
    return tA;
}

減法可先實現取反再用加法；除法參照手工豎式/多字節除法實現。核心依賴 PolyAdd（原位加法），體現「基礎操作決定上層表達力」。

對比原書：接口設計哲學

原書分離 List、ListNode、ListIterator 三類，雖符合 STL 風格，但初學者負擔重、代碼晦澀（如 pa->coef = pa->coef + pb->coef; p = pb; pb = Biter.Next(); delete p; 混淆節點與數據域）。本設計單類封裝、游標內聚，更適合教學與中小項目。擴展時派生新類、封裝業務邏輯，符合工程實踐。