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

发布时间：2020-12-16 06:00:21 所属栏目：百科来源：网络整理

导读：我通常知道在C中设计一个通用的链表数据结构的两种方式.我想知道哪一种更好.在提出问题之前,我将尽快介绍两种方法：一种方法是围绕如下结构构建函数： struct list_element { struct list_element *prev; struct list_element *next; void *data;}; 显然,数

我通常知道在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/.列表元素结构中没有指向有效内容的void指针.相反,列表元素结构体包含在有效负载结构中：

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()就足够了. (罗迪回答)

解决方法

第一种方法可能看起来不那么干涉,但在许多情况下它不是(除非你添加额外的数据结构).

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

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

另一种选择是具有将人的存储器地址映射到列表节点的存储器地址的散列图.然后找到列表中的节点要快得多(但是比入侵方式还要慢).然而,由于这将需要更多的记忆,我建议不要这样做.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!