C++抽象链表基类如何让单链表仅继承next指针、双链表继承双指针

核心解决思路 #

通过模板特化控制节点成员生成，或者隐藏派生节点类的内部转换逻辑，既满足两类链表的指针需求，又保证原有基类接口完全兼容，无需修改现有返回Node类型的函数。

方案1：模板特化节点类（推荐，无额外开销） #

该方案通过编译期分支生成不同的节点结构，单链表节点不会包含多余的prev指针，所有原有接口完全复用。

#include <type_traits>
template <typename T, bool is_double_linked = false>
class LL{
protected:
    enum {MAX = 512};
    // 节点模板声明
    template<bool enable_prev>
    struct NodeImpl;
    // 单链表节点特化：仅包含next指针
    template<>
    struct NodeImpl<false> {
    protected:
        NodeImpl* next;
    public:
        const T& data;
        NodeImpl() {}
        // 原有节点方法保持不变
    };
    // 双链表节点特化：同时包含next、prev指针
    template<>
    struct NodeImpl<true> {
    protected:
        NodeImpl* next;
        NodeImpl* prev;
    public:
        const T& data;
        NodeImpl() {}
        // 原有节点方法保持不变
    };
    // 统一节点类型别名，对外暴露的Node类型和原有定义完全一致
    using Node = NodeImpl<is_double_linked>;

    // 原有基类所有返回Node*的函数不需要做任何修改
    // ... 原有LL类的其余实现
};

派生单链表类 #

template<typename T>
class SingleLL : public LL<T, false> {
    // 直接复用基类所有逻辑，节点仅含next指针，无额外内存开销
    // 补充单链表特有的操作即可
};

派生双链表类 #

template<typename T>
class DoubleLL : public LL<T, true> {
    // 基类Node自动包含prev指针，所有原有接口直接可用
    // 双链表特有的操作可以直接访问Node的prev成员
};

方案2：派生节点内部转换（兼容C++03及更早标准） #

如果编译环境不支持C++11以上特性，可以采用该方案，不需要修改基类定义，仅在双链表内部做类型转换即可。

基类保持你修改后的原有定义即可 #

template <typename T>
class LL{
protected:
    enum {MAX = 512};
    class Node{
    protected: 
        Node* next;
    public:
        const T& data;
        Node() {}
        // 原有节点方法保持不变
    };
    // 原有返回Node*的所有函数完全不变
    // ... 原有LL类的其余实现
};

单链表派生类直接复用基类即可 #

template<typename T>
class SingleLL : public LL<T> {
    // 不需要额外修改，直接使用基类逻辑
};

双链表派生类内部处理节点转换 #

template<typename T>
class DoubleLL : public LL<T> {
protected:
    // 内部派生节点新增prev指针，不需要对外暴露
    class BiNode : public LL<T>::Node {
    protected:
        BiNode* prev;
    };
    // 内部工具函数：基类Node指针转BiNode指针，双链表所有节点都是BiNode实例，静态转换安全
    BiNode* to_binode(typename LL<T>::Node* node) {
        return static_cast<BiNode*>(node);
    }
public:
    // 对外接口和基类完全一致，返回基类Node*，外部使用无感知
    // 双链表内部操作需要访问prev时，调用to_binode转换即可
};

两种方案优势对比 #

• 方案1无任何运行时开销，节点结构完全按需生成，接口和原有逻辑100%兼容，优先推荐使用
• 方案2不需要修改原有基类代码，适合基类已经封装为库无法修改的场景，仅双链表内部有可忽略的静态转换开销

内容的提问来源于stack exchange，提问作者g0x0