开源C语言库Melon双向链表使用

　　本篇主要介绍开源C语言库Melon的双向链表使用，对开源C库感兴趣的读者可以访问：
　　github。comWaterMelonMelon。链表简介
　　先简单介绍一下什么是双向链表。可以参考下图：
　　简单来说，链表是将一个一个的结点，通过指针连接起来。而双向链表则是每一个结点不仅记录了指向下一结点的指针，也记录了指向前一结点的指针。
　　Melon中的双向链表属于上图中带有尾部结点的双向链表。
　　双向链表的优势：结点的插入和删除操作的时间复杂度为O（1），所以应对频繁插入和删除的场景，是非常适合的。双向链表使用
　　我们先定义一个自定义结构体类型：typedefstructtests｛intval；｝testt；
　　后续的介绍中，我们要做的就是使用Melon的链表组件对这个结构进行改造，将其构建成一个双向链表。
　　在Melon中，双向链表有两种实现。两种实现进行对比也各有其特点，因此读者在了解各自特点后，可根据自己需要进行选择使用。第一种实现
　　我们直接上代码，然后再进行说明：includestdio。hincludestdlib。hincludemlndefs。htypedefstructtests｛intval；structtestsprev；structtestsnext；｝testt；MLNCHAINFUNCDECLARE（test，testt，staticinlinevoid，）；MLNCHAINFUNCDEFINE（test，testt，staticinlinevoid，prev，next）；intmain（void）｛inti；testtheadNULL，tailNULL，t；for（i0；i10；i）｛t（testt）malloc（sizeof（testt））；if（tNULL）｛fprintf（stderr，mallocfailed。）；return1；｝tvali；tprevtnextNULL；testchainadd（head，tail，t）；｝for（thead；t！NULL；ttnext）｛printf（d，tval）；｝return0；｝
　　这段代码中，main函数中的内容很简单，利用一个for循环，malloc10个testt结构，然后将其val填充数值。随后利用testchainadd函数将这些结点连成一个链表。然后利用for循环遍历结点并打印val的值。
　　下面问题就来了，testchainadd哪里来的？
　　我们看到main前有两个MLNCHAINFUNCxxx的宏，这两个宏是在Melon的mlndefs。h头文件中定义的，用来对链表的插入和删除函数进行定义和声明的。MLNCHAINFUNCDECLARE第一个参数：函数名前缀第二个参数：自定义结构体类型第三个参数：函数返回值及函数类型第四个参数：函数参数限制属性（本例没有使用）MLNCHAINFUNCDEFINE第一个参数：函数名前缀第二个参数：自定义结构体类型第三个参数：函数返回值及函数类型第四个参数：自定义结构中用于访问前一结点的指针成员名字第五个参数：自定义结构中用于访问下一结点的指针成员名字
　　这两个宏会定义和声明两个函数，分别名为：testchainadd和testchaindel，这两个函数的原型类似如下形式：void（chainop）（typehead，typetail，typenode）；
　　第一个参数为双向链表首指针的指针，第二个参数为双向链表尾指针的指针，第三个参数为要被操作的结点指针。特点
　　这种实现方案的好处是：插入和删除函数可以被定义成inline或者增加一些其他属性。并且在遍历链表时，只需要访问自定义结点的prev和next指针即可。
　　缺点是：使用者需要知道自定义结构中自己加入的prev和next成员名字，以及如果定义了很多双向链表，则需要配套定义很多插入和删除函数，会增加可执行程序的体积。第二种实现
　　这种实现可能比较常见了。我们直接看代码：includemlnlist。hincludemlndefs。hincludestdlib。htypedefstruct｛intval；mlnlisttnode；｝testt；intmain（void）｛inti；testtt；mlnlisttsentinelmlnlistnull（）；for（i0；i3；i）｛t（testt）calloc（1，sizeof（t））；if（tNULL）return1；mlnlistadd（sentinel，tnode）；tvali；｝for（tmlncontainerof（mlnlisthead（sentinel），testt，node）；t！NULL；tmlncontainerof（mlnlistnext（tnode），testt，node））｛printf（d，tval）；｝return0；｝
　　主函数的行为与第一种实现的代码是完全一样的。差别在于如下几方面：引入了mlnlist。h头文件testt中不再是添加prev和next成员，而是加入一个固定类型的成员，即mlnlistt类型的node成员。双向链表的首尾指针改为了一个名叫sentinel的mlnlistt类型变量。链表插入函数不再是自定义前缀函数，而是一个固定名称的函数名为mlnlistadd。访问链表首结点使用mlnlisthead宏想获取链表结点所在的宿主结构（即本例的testt）指针，需要使用mlndefs。h中的mlncontainerof宏。特点
　　这种实现的优劣分别是：
　　优势：使用者不需要关心链表的具体实现细节，只需要在自定义类型中引入mlnlistt类型成员即可。并且函数的插入和删除操作都是固定名称的，分别为：mlnlistadd和mlnlistremove。
　　劣势：对链表结点所属的宿主结点（testt）的访问需要借助mlncontainerof宏，这看上去并不如第一种实现中那么直观。且链表操作函数都是非inline的，因此频繁调用的开销会高于第一种实现。
　　事实上，感兴趣的读者可能会发现，第二种双向链表（mlnlist。c），是使用第一种双向链表来实现的。结语
　　感谢阅读，感兴趣的读者可以访问Melon库查看更多细节，Melon是一个无依赖且开箱即用的开源C语言库，并且有配套的中英文文档。
　　Github传送门：
　　github。comWaterMelonMelon