c - 链表的两种实现方式 : which is better?

Question

我通常知道两种用 C 语言设计通用链表数据结构的方法。我想知道哪种方法更好。在提问之前，我将简要介绍这两种方法:

一种方法是围绕如下结构构建函数:

struct list_element {
    struct list_element *prev;
    struct list_element *next;
    void *data;
};

显然，数据指针指向负载。列表元素结构在有效负载之外。这是例如glib 如何设计其双链表工具:http://library.gnome.org/devel/glib/2.26/glib-Doubly-Linked-Lists.html

另一种方法是它在 Linux 内核中的实现方式:http://isis.poly.edu/kulesh/stuff/src/klist/ .列表元素结构中没有指向有效负载的空指针。相反，列表元素结构包含在有效负载结构中:

struct list_element {
    struct list_element *prev;
    struct list_element *next;
};

struct person {
    char name[20];
    unsigned int age;
    struct list_element list_entry;
};

在给出指向 list_entry 的指针的情况下，使用一个特殊的宏来获取指向有效载荷结构的指针，其名称包含有效载荷结构和有效载荷结构的类型(list_entry() 宏)。

最后，问题来了:这两种构造链表的方法，后者的优势是什么？有几次我听到人们说第二种比第一种更“通用”，但为什么呢？我什至会争辩说第一种方法更通用，因为有效负载结构是列表实现不可知的，而第二种方法不是这种情况。
第二种方法的另一个缺点是，如果您想将有效载荷放在多个列表中，则应该为有效载荷结构中的每个列表分配一个 struct list_element 成员。

编辑: 总结到目前为止，我看到了两个对我很重要的答案:

• 第一种方法:从列表中删除有效载荷涉及遍历整个列表，直到找到指向有效载荷的列表元素。您不需要使用第二种方法执行此操作。 (帕特里克的回答)
• 使用第一种方法，您必须为每个元素执行两个 malloc():一个用于有效负载，一个用于列表元素结构。对于第二种方法，一个 malloc() 就足够了。 (罗迪的回答)

Answer 1

这是用来类的马。

第一种方法效率较低，因为它通常需要为每个列表元素使用两个 malloc() 和 free()，以及一个额外的指针间接访问它们- 当然还有指针的存储空间。

但是，它允许不同的列表元素具有不同大小的有效载荷，这对于第二种方法来说可能更尴尬。

对于第二种方法，我会重新排序结构，以便列表元素位于开头 - 这样可以为不同的有效负载大小提供一些灵 active 。

struct person {
    struct list_element list_entry;
    unsigned int age;
    char name[20];  // now could be variable length.
};