关于c:开源C语言库双向链表

本篇次要介绍开源 C 语言库 Melon 的双向链表应用，对开源 C 库感兴趣的读者能够拜访：Github repo。

链表简介

先简略介绍一下什么是双向链表。能够参考下图：

简略来说，链表是将一个一个的结点，通过指针连接起来。而双向链表则是每一个结点不仅记录了指向下一结点的指针，也记录了指向前一结点的指针。

Melon 中的双向链表属于上图中带有尾部结点的双向链表。

双向链表的 劣势：结点的插入和删除操作的工夫复杂度为 O(1)，所以应答频繁插入和删除的场景，是非常适合的。

双向链表应用

咱们先定义一个自定义构造体类型：

typedef struct test_s {int val;} test_t;

后续的介绍中，咱们要做的就是应用 Melon 的链表组件对这个构造进行革新，将其构建成一个双向链表。

在 Melon 中，双向链表有两种实现。两种实现进行比照也各有其特点，因而读者在理解各自特点后，可依据本人须要进行抉择应用。

第一种实现

咱们间接上代码，而后再进行阐明：

#include <stdio.h>
#include <stdlib.h>
#include "mln_defs.h"

typedef struct test_s {
    int val;
    struct test_s *prev;
    struct test_s *next;
} test_t;

MLN_CHAIN_FUNC_DECLARE(test, test_t, static inline void,);
MLN_CHAIN_FUNC_DEFINE(test, test_t, static inline void, prev, next);

int main(void)
{
  int i;
  test_t *head = NULL, *tail = NULL, *t;

  for (i = 0; i < 10; ++i) {t = (test_t *)malloc(sizeof(test_t));
    if (t == NULL) {fprintf(stderr, "malloc failed.\n");
        return -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);
  }
  return 0;
}

这段代码中，main函数中的内容很简略，利用一个 for 循环，malloc10 个 test_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"
#include <stdlib.h>

typedef struct {
    int        val;
    mln_list_t node;
} test_t;

int main(void)
{
    int i;
    test_t *t;
    mln_list_t sentinel = mln_list_null();

    for (i = 0; i < 3; ++i) {t = (test_t *)calloc(1, sizeof(*t));
        if (t == NULL)
            return -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);
    }
    return 0;
}

主函数的行为与第一种实现的代码是齐全一样的。差异在于如下几方面：

1. 引入了 mln_list.h 头文件
2. test_t 中不再是增加 prev 和next成员，而是退出一个固定类型的成员，即 mln_list_t 类型的 node 成员。
3. 双向链表的首尾指针改为了一个名叫 sentinel 的mln_list_t类型变量。
4. 链表插入函数不再是自定义前缀函数，而是一个固定名称的函数名为mln_list_add.
5. 拜访链表首结点应用 mln_list_head 宏
6. 想获取链表结点所在的宿主构造（即本例的 test_t）指针，须要应用 mln_defs.h 中的 mln_container_of 宏。

特点

这种实现的优劣别离是：

劣势：使用者不须要关怀链表的具体实现细节，只须要在自定义类型中引入 mln_list_t 类型成员即可。并且函数的插入和删除操作都是固定名称的，别离为：mln_list_add和mln_list_remove。

劣势：对链表结点所属的宿主结点（test_t）的拜访须要借助 mln_container_of 宏，这看上去并不如第一种实现中那么直观。且链表操作函数都是非 inline 的，因而频繁调用的开销会高于第一种实现。

事实上，感兴趣的读者可能会发现，第二种双向链表（mln_list.c），是应用第一种双向链表来实现的。

结语

感激浏览，感兴趣的读者能够拜访 Melon 库查看更多细节，Melon 是一个无依赖且开箱即用的开源 C 语言库，并且有配套的中英文文档。

Github 传送门