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

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
– John Bollinger, Commented Dec 12, 2018 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
– chux, Commented Dec 12, 2018 at 18:45
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
– chux, Commented Dec 12, 2018 at 18:55
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
– chux, Commented Dec 12, 2018 at 19:12

AShelly · Accepted Answer · 2018-12-12 21:05:44Z

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: 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!!!
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.

Collectives™ on Stack Overflow

How to implement generic linked list in c

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related