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

Question

我通常知道在C中设计通用链表数据结构的两种方法.我想知道哪个更好.在提出问题之前,我将简要介绍这两种方法:

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

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

显然,数据指针指向有效负载.list元素struct在有效负载之外.这就是glib如何设计其双链表设施:http://library.gnome.org/devel/glib/2.26/glib-Doubly-Linked-Lists.html

另一种方法是在Linux内核中完成它的方式:http://isis.poly.edu/kulesh/stuff/src/klist/.list元素结构中没有指向有效负载的void指针.相反,list元素struct包含在payload结构中:

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():一个用于有效负载,另一个用于list元素struct.使用第二种方法,一个malloc()就足够了.(罗迪的回答)

Answer 1

这是课程的马匹.

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

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

对于第二种方法,我会重新排序结构,因此列表元素在开始时 - 这样就可以为不同的有效负载大小提供一些灵活性.

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

Answer 2

第一种方法可能看起来不那么具有侵入性,但在许多情况下并非如此(除非您添加其他数据结构).

想象一下,你有一个千人的列表,你想从列表中删除其中一个.如果此人不知道列表中的位置,则必须先扫描整个列表以获取该人员的确切位置.

你可以通过添加一个从人到其相应列表结构的指针来解决这个问题,但是这会破坏解决方案的非侵入性(这个词是否存在？).

另一种替代方案是具有将人的存储器地址映射到列表节点的存储器地址的散列映射.然后在列表中找到节点要快得多(但仍比入侵方式慢).但是,由于这将占用更多的内存,我建议不要这样做.

因此,最简单和最简单的解决方案是第二个.