Проектирование реализации связного списка в C

Question

В данный момент я работаю над созданием небольшой библиотеки для общих структур данных на C. Это в основном для целей обучения, но я планирую использовать эту библиотеку в других проектах, чтобы увидеть, насколько хорошо она работает и где проблемы,Пока что я доволен реализацией своего хеша и двоичного дерева, но не могу определиться с дизайном связанного списка.

Все реализованные структуры данных работают с указателями void и не несут ответственности засоздание или уничтожение данных, т.е. они ссылаются только на данные.Одна из целей разработки - сделать их как можно более общими для увеличения возможности повторного использования.

Что касается связанного списка, я нашел три подхода:

1. Выделенный заголовок списка : список содержит выделенный заголовок списка, который используется как абстрактный тип данных.

2. Только узлы : как в примере выше,за исключением того, что все функции работают на list_node.Используется в GLib .

3. В полезной нагрузке : добавьте структуру list_node к данным полезной нагрузки и рассчитайте смещение для полезной нагрузки с помощьюмакро.См. списки в ядре Linux

4. EDIT Создание типизированных списков с макросами : используйте макросы для создания специфичных для типаверсии структур и функций списка.

   Пример для 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

Я предпочитаю второй подход, т. Е. Только узлы.

Его преимущество в том, что он чрезвычайно прост, поскольку результаты большинства операций над списками (split, push, pop, sublist и т. Д.) Сами по себе являются списками.

Также обратите внимание, что вам не хватает важных операций со списками, в основном push() и pop(). Вы должны использовать тот факт, что списки допускают вставку в O (1).

Answer 2

Обратите внимание, что вам не обязательно использовать указатели void *. Вы можете использовать трюки вставки макросов для генерации типов / функций (путем добавления имени типа к типам и функциям) для общих типов безопасных структур данных.

пример: http://sglib.sourceforge.net/