C语言中链表实现的设计

Question

目前我正在开发一个用于C语言常见数据结构的小型库。这主要是为了学习目的，但我计划在其他项目中使用此库，以查看其功能和问题所在。到目前为止，我对我的哈希和二叉树实现感到满意，但我无法决定链表的设计。

到目前为止，所有已实现的数据结构都使用void指针，并不负责创建或销毁数据，即它们只引用数据。一个设计目标是尽可能地保持它们的通用性，以增加重复使用性。

关于链表，我已经找到了三种方法：

1. 专用列表头：该列表具有专用列表头，用作抽象数据类型。

2. 仅节点：与上面的示例类似，但所有函数都在 list_node 上操作。在 GLib 中使用。

3. 在有效负载中：将 list_node 结构添加到有效负载数据中，并使用宏计算偏移量以获取有效负载。参见 lists in the linux kernel

4. 编辑 使用宏生成带类型的列表：使用宏创建特定类型版本的列表结构和函数。

   1 和 2 的示例：

/* list.h */
typedef struct list_t list;

typedef int (*comparator)(const void* a, const void* b);

list* list_new          (comparator c);
void  list_delete       (list* l);
void  list_insert_after (list* l, uint32_t index, void* data);
void  list_remove       (list* l, void* data);
uint32_t list_size      (list* l);
/* other functions operating on lists */

/* list.c */
#include "list.h"

typedef struct list_node_t {
  struct list_node_t* next;
  struct list_node_t* prev;
  void* data;
} list_node;

struct list_t {
  list_node* begin;
  list_node* end;
  uint32_t   size;
  comparator cmp;
}

现在来谈谈问题：哪种方法最为通用？还有其他方法吗？

- Dario Hamidi

---

最好使用 size_t 来表示 index、size 等，而不是 uint32_t。 - Paul R

你可能也想看看sys/queue.h的实现。 - mripard

@Dario - 或许这两个函数应该接受一个比较器参数，而不是将其作为列表的固有部分。 - Chris Lutz

另外，不要使用宏来创建特定类型的函数。这听起来像是在C中模仿模板的一种非常笨拙的方式。我更喜欢第三种选择，但如果你愿意始终将列表成员放在前面并编写所有函数作为void *或宏，则不需要使用offsetof。(宏允许您创建一个new函数，它可以进行堆分配，但通用于实际列表类型。) - Chris Lutz

@Dario - 我已经阅读了OOC（我正在基于它的项目上工作），根据你的描述，它似乎有点过重了。我更倾向于“链表类型通用”而不是“所有容器通用”（尽管如果你能做到，我会为你鼓掌）。#define list_new(name, next, prev) do { name = malloc(sizeof *name); ((node *)name)->next = next; ((node *)name)->prev == prev; } while(0) - Chris Lutz

Answer 1

我更喜欢第二种方法，即仅使用节点。

它的优点在于非常简单，因为大多数列表操作（拆分、推入、弹出、子列表等）的结果本身就是列表。

此外，请注意您缺少重要的列表操作，主要是push()和pop()。您应该利用列表允许O(1)插入的事实。

- Philip

---

谢谢你的建议！示例中提供的接口绝不完整，它只是为了说明问题。 - Dario Hamidi

我实际上更喜欢1和2的混合使用——当节点足够时使用2，但在可以存储在列表头中的额外信息（例如end、size等）可以导致显著加速的情况下使用1。 - Chris Lutz

Answer 2

请注意，您不一定需要使用void *指针。您可以使用宏粘贴技巧来生成类型/函数（通过将类型名称附加到类型和函数上），以用于通用类型安全数据结构。

例如：http://sglib.sourceforge.net/

- Roman A. Taycher

---

当然是一个有趣的方法，你知道有哪些项目使用sglib吗？ - Dario Hamidi