本文主要介绍开源C语言库Melon的双向链表的使用。对开源C库感兴趣的读者可以访问：Githubrepo。链表简介首先简单介绍一下什么是双向链表。可以参考下图：简单来说，链表就是通过指针将节点一个接一个地连接起来。在双向链表中，每个节点不仅记录了指向下一个节点的指针，还记录了指向前一个节点的指针。Melon中的双向链表属于上图中尾节点的双向链表。双向链表的优点：节点插入和删除的时间复杂度为O(1)，因此非常适合频繁插入和删除的场景。要使用双向链表，我们首先定义一个自定义结构类型：typedefstructtest_s{intval;}test_t;在后面的介绍中，我们要做的就是利用Melon的链表组件对这个结构进行改造，构建成双向链表。在Melon中，有两种双向链表的实现。对比这两种实现方式也各有特点，读者可以在了解各自的特点后，根据自己的需要选择使用。对于第一种实现，我们直接上传代码，然后进行解释：#include#include#include"mln_defs.h"结构test_s*prev;structtest_s*next;}test_t;MLN_CHAIN_FUNC_DECLARE(test,test_t,staticinlinevoid,);MLN_CHAIN_FUNC_DEFINE(test,test_t,staticinlinevoid,prev,next);intmain(void){inti;test_t*head=NULL,*tail=NULL,*t;对于(i=0;i<10;++i){t=(test_t*)malloc(sizeof(test_t));if(t==NULL){fprintf(stderr,"malloc失败。\n");返回-1；}t->val=i;t->prev=t->next=NULL;test_chain_add(&head,&tail,t);}for(t=head;t!=NULL;t=t->next){printf("%d\n",t->val);}return0;}这段代码中，main函数中的内容很简单，使用了一个for循环，malloc10test_t结构，然后给它的val填充一个值。然后使用test_chain_add函数将这些节点连接成一个链表。然后使用for循环遍历节点，打印出val的值。问题来了，test_chain_add从哪里来？我们看到main之前有两个MLN_CHAIN_FUNC_xxx宏。这两个宏定义在Melon的mln_defs.h头文件中，用于定义和声明链表的插入和删除函数。MLN_CHAIN_FUNC_DECLARE第一个参数：函数名前缀第二个参数：自定义结构类型第三个参数：函数返回值和函数类型第四个参数：函数参数限制属性（本例未使用）MLN_CHAIN_FUNC_DEFINE第一个参数：函数名前缀第二个参数：自定义结构类型第三个参数：函数返回值和函数类型第四个参数：用于访问自定义结构中上一个节点的指针成员名第五个参数：用于访问自定义结构中下一个节点的指针成员名。这两个宏将定义和声明两个名为：test_chain_add和test_chain_del的函数。这两个函数的原型类似于下面的形式：void(*chain_op)(type**head,type**tail,type*node);第一个参数是双向链表头指针的指针，第二个参数是双向链表尾指针的指针，第三个参数是要操作的结点指针。这种实现的好处是可以将插入和删除函数定义为inline或者可以添加一些其他的属性。而在遍历链表时，只需要访问自定义节点的prev和next指针即可。缺点是用户需要知道自定义结构中添加的prev和next成员的名称，如果定义了很多双向链表，需要定义很多插入删除函数，会增加可执行程序的体积.第二种实现可能更常见。我们直接看代码：#include"mln_list.h"#include"mln_defs.h"#includetypedefstruct{intval;mln_list_t节点；}test_t；intmain(void){inti;test_t*t;mln_list_tsentinel=mln_list_null();对于(i=0;i<3;++i){t=(test_t*)calloc(1,sizeof(*t));如果(t==NULL)返回-1;mln_list_add(&sentinel,&t->node);t->val=i;}for(t=mln_container_of(mln_list_head(&sentinel),test_t,node);\t!=NULL;\t=mln_container_of(mln_list_next(&t->node),test_t,node)){printf("%d\n",t->val);}return0;}main函数的行为与第一个实现的代码完全一样。区别在于以下几个方面：引入mln_list.h头文件test_t不再增加prev和next成员，而是增加了一个固定类型的成员，即mln_list_t类型的节点成员。双向链表的头尾指针改为一个名为sentinel的mln_list_t类型变量。链表插入函数不再是自定义的前缀函数，而是一个固定名称的函数，名字叫mln_list_add。要访问链表的第一个节点，使用mln_list_head宏获取链表节点所在宿主结构的指针（即本例中的test_t），需要使用mln_defs.h中的mln_container_of宏。特点这种实现的优缺点是：优点：用户无需关心链表的具体实现细节，只需要在自定义类型中引入mln_list_t类型成员即可。并且函数的插入和删除操作都是固定的名字，分别是：mln_list_add和mln_list_remove。缺点：访问链表节点所属的宿主节点（test_t）需要借助mln_container_of宏，看起来不像第一种实现那么直观。而且链表操作函数都是非内联的，所以频繁调用的开销会比第一次实现高。其实有兴趣的读者可能会发现，第二种双向链表（mln_list.c）是使用第一种双向链表实现的。结论感谢您的阅读。感兴趣的读者可以访问Melon库了解更多详情。Melon是一个开源的C语言库，无依赖，开箱即用，有配套的中英文文档。Github门户
