如何在c中实现通用链表

Question

我想在c中创建一个泛型链表，下面是我创建它的方法，但我不确定这是否是正确的方法，我在堆中为结构uniqueOrderedList_t分配一个新内存，然后在堆中也为元素分配一个内存，因为我希望它是泛型的，这是正确的方式吗？那么"下一个指针"呢，我也需要为它分配内存吗？

#the .h file contain:
typedef void* Element;
typedef struct uniqueOrderedList_t* UniqueOrderedList;
UniqueOrderedList uniqueOrderedListCreate(/*some parameters*/);

---

#the .c file:
struct uniqueOrderedList_t{
Element element;
struct uniqueOrderedList_t* next;  
};
uniqueOrderedList uniqueOrderedListCreate(/*some arguments*/){
UniqueOrderedList newList = malloc(sizeof(*newList));
if(!newList){
return NULL;
}
newLust->element = malloc(sizeof(Element));
if(!element){
return NULL;
}
newList->next = NULL;
}

Answer 1

第一步是正确处理连接节点的所有繁琐细节@chux在评论中有很好的建议——只需先用int或float类型实现它，以确保它是正确的。

更大的问题是用什么来代替/*some parameters*/，以便使列表具有通用性。具体来说，add_node函数的"value"参数应该使用什么类型。

唯一可以从任何其他类型自由来回转换的类型是void*。您可以直接将指针的副本存储在节点中，但这意味着您需要确保它们所指向的变量永远不会超出范围。您永远无法将堆栈本地变量的地址添加到列表中。

有几种方法可以解决这个问题。

1. 您可以跟踪项目大小，并使用malloc和memcpy创建足够大的节点来容纳数据。

   a。在创建列表时声明项目大小。list = makelist(sizeof(myType))。这将与存储尺寸的独特头部类型配合使用效果最佳。

   b。强制用户传递每个节点的大小：list = add_node(list, &item, sizeof(item))。

   c。策略1b，但使用宏传递大小：#define add_node(l,item) (add_node_impl(l, &item, sizeof(item))

这些策略的缺点是没有类型安全性。编译器不会检测到是否将字符串传递到浮点数列表中。

2. 您可以使用宏为您的列表类型生成特定的函数

   #define VALUE_T MyType #define LISTOF(type) type ## list LISTOF(VALUE_T) add_node(LISTOF(VALUE_T) l, VALUE_T v) { /* alloc(sizeof(VALUE_T)),copy from &v, link into l */ }

此策略更为类型安全，但宏量很大，这使得它很难正确，也很难调试。它最终的工作方式就像C++模板的一个更明确的版本，在那里你必须确保有一个为你使用的每种不同类型生成的代码副本。