链表中void*数据类型使用问题：实现支持void*参数的键值对链表

1. value类型的确定 #

你目前的需求中key固定为int类型，所以模板类node的第一个参数S可以直接指定为int，第二个参数T（即value的类型）根据你的使用场景二选一即可：

• 如果你仅需要存储Add函数传入的value指针本身，不需要拷贝指针指向的实际数据，直接将T设置为void*即可，实例化后的节点类型为node<int, void*>。注意该场景下你需要自行管理所有传入的指针的生命周期，链表销毁时要同步释放对应内存避免泄漏。
• 如果你需要存储value指针指向的实际数据的拷贝，且使用场景中存储的数据类型是固定的（比如固定为自定义结构体、int、字符串等），可以将T设置为对应的实际类型，Add函数内将void*强转成对应类型的指针后解引用赋值给节点的value成员即可。

2. 链表实现选型 #

根据你的业务需求选择对应链表即可：

• 普通单向链表：实现成本最低，适合仅需要头尾插入、数据量小的场景，增删查操作的时间复杂度均为O(n)。
• 有序单向链表：如果后续需要支持按key查找、范围查询，可以要求节点按key的升序/降序排列，插入时找到对应位置插入，查询时可以提前终止遍历，效率高于普通无序链表。
• 有序双向链表：如果频繁需要删除中间节点，选择双向链表不需要遍历查找节点的前驱节点，增删效率更高。

注意：你当前声明的node类缺少指向其他节点的指针成员，需要对应补充：
单向链表补充后继指针node<S, T>* next;，双向链表额外补充前驱指针node<S, T>* prev;

示例实现参考 #

以下是采用普通单向链表、存储void*类型value的示例代码：

// 补充完整的node模板类
template<class S, class T>
class node {
public:
    S key;
    T value;
    node<S, T>* next;
};

// 链表结构体
struct KVList {
    node<int, void*>* head = nullptr;
    // 按需补充尾指针、节点计数等成员
};

StatusType Add(void *DS, int key, void* value)
{
    if (DS == nullptr) {
        return ERROR; // 替换为你定义的对应错误状态码
    }
    KVList* list = static_cast<KVList*>(DS);
    // 校验key是否已存在，按需选择覆盖旧值或返回重复错误
    node<int, void*>* cur = list->head;
    while (cur != nullptr) {
        if (cur->key == key) {
            cur->value = value;
            return SUCCESS; // 替换为你定义的对应成功状态码
        }
        cur = cur->next;
    }
    // 头插新节点
    node<int, void*>* new_node = new node<int, void*>();
    new_node->key = key;
    new_node->value = value;
    new_node->next = list->head;
    list->head = new_node;
    return SUCCESS;
}

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