在C中设计链表实现

Question

目前我正在为C中的公共数据结构创建一个小型库.这主要用于学习目的,但我计划在其他项目中使用此库来查看它的工作原理以及问题所在.到目前为止,我对我的哈希和二叉树实现感到满意,但我无法决定链表的设计.

到目前为止实现的所有数据结构都使用void指针,并且不负责创建或销毁数据,即它们仅引用数据.一个设计目标是使它们尽可能通用,以提高可重用性.

关于链表,到目前为止我找到了三种方法:

1. 专用列表头:列表具有专用列表头,用作抽象数据类型.

2. 仅限节点:与上面的示例类似,只是所有功能都在a上运行list_node.用于GLib.

3. 在有效负载中:list_node向有效负载数据添加结构,并使用宏计算有效负载的偏移量.请参阅linux内核中的列表

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;
}

现在回答这个问题:哪种方法最通用？还有其他方法吗？

Answer 1

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

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

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