從單鏈表派生雙向鏈表：C++ 模板繼承的實踐與反思

雙向鏈表能否從單鏈表派生？嘗試過程揭示了 C++ 繼承與模板的深層機制，也暴露了「強行復用」的代價。

繼承策略與節點重定義

單鏈表節點 Node<Type> 僅含 data 和 link。派生雙向鏈表需雙向指針，有兩種路徑：

1. 重新定義節點類，但名稱必須仍為 Node（因基類代碼硬編碼），需複製整個單鏈表實現文件並替換——不再是繼承。
2. 定義包裝結構 newtype<Type>，內含 Type data 和 Node<newtype> *link，令 DblList : List<newtype<Type>>。注意連續 `>>` 需加空格。

採用方案二，並直接沿用 Node<Type> 作為雙向節點（利用其 link 域存儲前驅指針），需重載 `==` 運算符以配合 Find 等函數。

基類擴展：暴露指針操作接口

為實現 Prior()（向前移動），必須在單鏈表 List 中添加 protected 接口：

protected:
    void Put(Node<Type> *p) { current = p; }
    void PutPrior(Node<Type> *p) { prior = p; }

雖標註「盡量不用、危險」，但雙向鏈表不得不借用。

雙向鏈表核心實現

template <class Type> class DblList : public List< Node<Type> > {
public:
    Type *Get() { return pGet() ? &pGet()->data.data : NULL; }
    Type *Next() { pNext(); return Get(); }
    Type *Prior() {
        if (pGetPrior()) {
            Put(pGetPrior());
            PutPrior((Node<Node<Type>>*)pGet()->data.link);
            return Get();
        }
        return NULL;
    }
    void Insert(const Type &value) {
        Node<Type> newdata(value, (Node<Type>*)pGet());
        List<Node<Type>>::Insert(newdata);
        if (pGetNext()->link) pGetNext()->link->data.link = (Node<Type>*)pGetNext();
    }
    BOOL Remove() {
        if (List<Node<Type>>::Remove()) {
            pGet()->data.link = (Node<Type>*)pGetPrior();
            return TRUE;
        }
        return FALSE;
    }
};

僅實現 Insert、Remove、Prior，其他繼承自單鏈表不保證正確。指針類型轉換依賴編譯器實現，移植性存疑。

測試與結論

測試代碼驗證了正向遍歷、刪除後向前遍歷功能。但過程極其煩瑣，執行效率不佳，**不如重寫一個雙向鏈表來得乾淨、高效、可維護**。

同理，雙向循環鏈表可從雙向鏈表或循環鏈表派生。**結論：單鏈表是所有鏈式結構的根基，徹底掌握單鏈表，變體自然迎刃而解**——但這不代表要強行用繼承實現所有變體。為了學習而「鑽牛角尖」，過程本身加深了對 C++ 對象模型、函數調用、模板實例化的理解，這才是最大收穫。