How to implement generic linked list in c

Question

I want to create a generic linked list in c, Below is the way I created it, but I am not sure if that is the correct way to do it, I allocate a new memory in the heap for the struct uniqueOrderedList_t, and then allocate a new memory in the heap as well for the element as I want it to be generic, is that the right way to do it? and what about the "next pointer", do I need to allocate memory for it as well?

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

}

Possible duplicate of [How to implement a linked list in C?](https://stackoverflow.com/questions/982388/how-to-implement-a-linked-list-in-c) — Increasingly Idiotic, Dec 12 '18 at 18:10
You might try looking at: https://pseudomuto.com/2013/05/implementing-a-generic-linked-list-in-c/ — Increasingly Idiotic, Dec 12 '18 at 18:12
Start by *not* concealing pointer nature behind your `typedef`'d type aliases. In fact, it might be instructional to avoid using `typedef` at all. Next, ask yourself how, if your list is generic, it can possibly know how much memory an element requires. Consider also whether you intend to *copy* data into your list, or simply store pointers to objects that exist outside it. There is more, but that should get you aimed in a productive direction. — John Bollinger, Dec 12 '18 at 18:23
`newLust->element = malloc(sizeof(Element));` is not correct. Allocation not needed here. Too many application details ares unclear for recommended alternatives. — chux - Reinstate Monica, Dec 12 '18 at 18:45
@chux why? the element is a void*, so we dont know what the type it will get, so we have to allocate memory here, right? — D.A, Dec 12 '18 at 18:51
No. You have a linked list of pointers - we know its type - `void *`. Without going into things, it would be better for you to successfully make a linked list of `int` and then port that to "generic" types. — chux - Reinstate Monica, Dec 12 '18 at 18:55
@chux that is where I dont get it, If we dont know the type, then how the memory will allocate the correct one related to the type? chat is 1 byte, int is 4 byte and so on, — D.A, Dec 12 '18 at 19:06
But we do know the type with `typedef void* Element;` The element type is `void *`. There are 2 coding goals you are attempting. Making a linked list. Making the LL generic. I recommend again, code a LL for a specific type, then approach the "generic" attribute. Good luck. — chux - Reinstate Monica, Dec 12 '18 at 19:12

score 0 · Answer 1 · answered Dec 12 '18 at 21:05

The first step is to get all the fiddly details of connecting nodes right. @chux has good advice in the comments - just implement it with int or float types first to make sure it is correct.

The bigger issue is what to put in place of /*some parameters*/, in order to make the list generic. Specifically, what type should you use for the "value" argument of the add_node function.

The only type that you can freely convert back and forth from any other type is void*. You could just store copies of the pointers directly in the nodes - but that means you need to ensure that the variables they point to never go out of scope. You could never add the address of a stack local variable to the list.

There are several ways around this.

You can keep track of the item size and use malloc and memcpy to create nodes big enough to hold the data.

a. Declare the item size when the list is created. list = makelist(sizeof(myType)). This would work best with a unique head type that stores the size.

b. Force the users to pass the size for each node: list = add_node(list, &item, sizeof(item)) .

c. Strategy 1b, but use a macro to pass the size: #define add_node(l,item) (add_node_impl(l, &item, sizeof(item))

These strategies have the disadvantage that there is no type safety. The compiler won't detect if you pass strings to your list of floats.

You can use macros to generate specific functions for your listable type

#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 */ }

This strategy is more typesafe, but is macro-heavy, which makes it hard to get right, and hard to debug. It ends up working like a more explicit version of C++ templates, where you have to ensure there is a copy of the code generated for every different type you use.

But when I check this link: https://www.geeksforgeeks.org/generic-linked-list-in-c-2/ , I see that they allocate a memory in the heap for the "element" as well, (in there case it is node), and here where I get confused!!! — D.A, Dec 13 '18 at 10:47
Yes, you need to allocate space for both the pointers (the node: in your case `uniqueOrderedList` ) _and_ the item being stored (the value :`*Element`). The linked example is using the strategey I describe as 1b. — AShelly, Dec 13 '18 at 16:24

How to implement generic linked list in c

1 Answers1