实现链表的两种方法：哪种更好？

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 成员。

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

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

Answer 1

我认为这是一个非常主观的问题，因为没有给出比较两者的标准。

对于简单的列表，我倾向于使用两者的组合。

struct list_node {
    struct list_node *  prev;
    struct list_node *  next;
};

struct some_struct {
    struct list_node  node;
    ...
};

尽管这看起来与第二个几乎相同，但请注意链表节点是“some_struct”的第一个元素。这意味着当您前进到下一个节点或倒回到列表中的上一个节点时，指针位于结构的开头。否则我将被迫执行一些指针数学运算才能到达“some_struct”的开头。按照目前的情况，我可以简单地进行投射。

然而，这种方法确实有其局限性。例如，如果我想要一个具有多个链表的结构，则列出的每个方法都存在缺陷，因为它需要指针算术才能到达至少一个结构的开头。为了解决这个问题，一些实现（例如 BSD VFS 代码中的实现）使用宏来创建链接列表元素。在这些中，链表始终指向结构的开头，但宏包含根据需要自动应用结构内节点偏移量的代码（用于前进到下一个，或倒回上一个）。

希望这有帮助。

编辑：修正了一些术语。

Answer 2

这是课程的马。

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

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

对于第二种方法，我将重新排序结构，使列表元素位于开头 - 这确实为不同的有效负载大小提供了一定的灵活性。

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

Answer 3

第一种方法可能看起来侵入性较小，但在许多情况下并非如此（除非您添加其他数据结构）。

想象一下，您有一个一千人的列表，并且您想从列表中删除其中一个人。如果此人不知道其在列表中的位置，则您必须先扫描整个列表才能找到此人的确切位置。

您可以通过添加从 person 到其相应列表结构的指针来解决此问题，但这会破坏解决方案的非侵入性（这个词存在吗？）。

另一种替代方案是使用哈希映射将人员的内存地址映射到列表节点的内存地址。那么在列表中查找节点要快得多（但仍然比侵入式方式慢）。但是，由于这会占用更多内存，因此我建议不要这样做。

因此，最简单、最简单的解决方案就是第二种。

Answer 4

第一个更好，因为您可以拥有根本没有数据的列表节点。

使用第二个选项时，无论实际使用情况如何，您始终使用空格（例如，名称的 20 个字符）。

Answer 5

第二种方法是侵入式列表。您必须修改要存储在列表中的结构。由于间接性较少，因此使用此方法可以获得一些性能。如果您需要更灵活的解决方案而不是最后一点性能，则应该使用第一种方法。

Answer 6

第二种方法是“侵入式”的；它需要对列表中的类型进行修改。列表（或多个列表）上的类型必须知道它在列表中。您必须能够修改结构才能将其放入列表中。

第一种方法不具有侵入性。它不需要修改结构。您可以将任何类型放入列表中。您甚至可以在单个列表中包含异构类型，尽管这会充满问题。但是，即使您无法修改基本类型，您也可以将其放在列表的第一种类型中。与此相反，它需要更多的空间。

因此，如果您可以完全控制要放入列表中的数据类型（并且可以修改它以支持您需要的列表），则第二种类型比第一种类型具有一些优势。在 Linux 内核的上下文中，前提条件已满足并且有意义。否则，第一种类型更灵活，但开销稍大。

Answer 7

我认为这更多是一个概念/分析问题。您正在使用的实体是否具有列表，或者您是否有实例列表？

换句话说，如果您在数据中管理的内容具有独立的存在，则第一个是有意义的，因为无论数据点如何，都将被独立操作。如果数据始终且必然是列表的一部分，那么第二种方法可能更清晰。

与大多数设计决策一样，最重要的标准应该是更清晰、最明显。