Как реализовать общий связанный список в c

Question

Я хочу создать общий связанный список в c. Ниже приведен способ, которым я его создал, но я не уверен, что это правильный способ сделать это, я выделяю новую память в куче для структуры uniqueOrderedList_t,а затем выделить новую память в куче для элемента, так как я хочу, чтобы он был универсальным, это правильный способ сделать это?и как насчет "следующего указателя", мне нужно также выделить память для него?

#the .h file contain:
typedef void* Element;
typedef struct uniqueOrderedList_t* UniqueOrderedList;
UniqueOrderedList uniqueOrderedListCreate(/*some parameters*/);

---

#the .c file:
struct uniqueOrderedList_t{
  Element element;
  struct uniqueOrderedList_t* next;  
};

uniqueOrderedList uniqueOrderedListCreate(/*some arguments*/){
   UniqueOrderedList newList = malloc(sizeof(*newList));
 if(!newList){
  return NULL;
 }
 newLust->element = malloc(sizeof(Element));
   if(!element){
     return NULL;
   }
 newList->next = NULL;

}

Answer 1

Первый шаг - правильно настроить все детали подключения узлов.У @chux есть хороший совет в комментариях - просто добавьте его сначала с типами int или float, чтобы убедиться в его правильности.

Большая проблема в том, что поставить вместо /*some parameters*/, вЧтобы сделать список общим.В частности, какой тип следует использовать для аргумента «значение» функции add_node.

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

Есть несколько способов обойти это.

1. Вы можете отслеживать размер элемента и использовать malloc и memcpy для создания узлов, достаточно больших для хранения данных.

   a.Объявите размер элемента при создании списка.list = makelist(sizeof(myType)).Это будет лучше всего работать с уникальным типом головы, который хранит размер.

   b.Заставьте пользователей передавать размер для каждого узла: list = add_node(list, &item, sizeof(item)).

   c.Стратегия 1b, но используйте макрос для передачи размера: #define add_node(l,item) (add_node_impl(l, &item, sizeof(item))

Недостатком этих стратегий является отсутствие безопасности типов.Компилятор не обнаружит, если вы передадите строки в ваш список с плавающей точкой.

Вы можете использовать макросы для генерации определенных функций для вашего списка типов

#define VALUE_T MyType #define LISTOF(type) type ## list LISTOF(VALUE_T) add_node(LISTOF(VALUE_T) l, VALUE_T v) { /* alloc(sizeof(VALUE_T)),copy from &v, link into l */ }

Эта стратегия более безопасна для типов, но она очень сложна, что затрудняет получение прав и затрудняет отладку.В итоге он работает как более явная версия шаблонов C ++, где вы должны убедиться, что есть копия кода, сгенерированного для каждого используемого вами другого типа.