How to make a generic linked list

Question

I'm trying to create a generic linked list in the C programming language and I succeeded but I have a little problem:

linked_list.h

 struct Element {
     void * data;
     struct Element * nEl;
 };
 typedef struct Element Element;

 struct List {
     size_t el_size;
     Element * start_el;
 };
 typedef struct List List;

linked_list.c

 List * create_list(size_t el_size);
 void delete_list(List * ls);
 void append(List * ls, void * data);
 void s_append(List * ls, void * data);


 void append(List * ls, void * data) {

     Element * last_el = ls - > start_el;

     if (last_el == NULL)
         ls - > start_el = last_el = malloc(sizeof(Element));
     else {
         while (last_el - > nEl != NULL)
             last_el = last_el - > nEl;

         last_el - > nEl = malloc(sizeof(Element));
         last_el = last_el - > nEl;
     }

     void * cdata = malloc(ls - > el_size);
     memcpy(cdata, data, ls - > el_size);

     last_el - > data = cdata;
     last_el - > nEl = NULL;
 }

This works well with all type like int, char, float, double etc. but it is not working with char * because its copying the first 4 bytes (implementation dependant) of the string, but not the whole string.

score 3 · Accepted Answer · answered Jun 23 '14 at 14:54

3

The problem is that the size of every element in your list is fixed (el_size). Not all strings will have the same size, assuming 1 byte per char "hola" will take up 4 bytes while "hi" while take up 2 bytes.

answered Jun 23 '14 at 14:54

Diego Allen

4,623
5
30
33

Yes, but then each element must take a el_size type, wich is not necessary for all other type – KarimS Jun 23 '14 at 14:59
@karim That's right. If you want a truly generic Linked List, you'll need to do some changes. I think your current implementation can work for linked lists limited to one type for every node and fixed size types. – Diego Allen Jun 23 '14 at 15:03

score 2 · Answer 2 · edited May 23 '17 at 11:45

2

You should use a more generic approach. Instead of just allocating memory you should use a function pointer to a constructor of the object that you want to hold.

Inside that function you should correctly allocate the space needed for your type. And don't forget to correctly clean up after using the same principle.

Those 2 functions should be members of your struct.

This may help you: How do function pointers in C work?

edited May 23 '17 at 11:45

Community

1
1

answered Jun 23 '14 at 14:52

zbs

671
4
16

Yeah i understand you're idea but i must create a constructor for each type – KarimS Jun 23 '14 at 14:58
Unfortunately, that is the way for generic structures in `C`. – zbs Jun 23 '14 at 14:58
1

Or i can add a generic constructor for simple type and i add own constructor for complex type like string – KarimS Jun 23 '14 at 15:01
Yeah of course, this idea is for types that contain `pointers`. Because those are the types that you need to investigate further to discover their size. – zbs Jun 23 '14 at 15:02

score 1 · Answer 3 · answered Jun 23 '14 at 15:32

Your list should never allocate and copy data. It's not its job. It only should store data (as a pointer). Copying data is the list creator's responsibility.

Thus, instead of

 void * cdata = malloc(ls - > el_size);
 memcpy(cdata, data, ls - > el_size);
 last_el -> data = cdata;

you would have just

 last_el -> data = data;

And no freeing data either.

Now if you want a list that owns its data, you can make that too, as a wrapper to your basic non-owning list. The idea is that you do that only when needed. Not every list needs to own its content.

A list that owns its contents needs to have a way to copy and dispose the data, ant that should be provided as a pair of function pointers that copy and free data. This is not an undue burden, as every data type should have such functions defined for it anyway.

but if you do it like you say a simple code like **for(int i = 0; i < 10; ++i) append(ls, &i);** this will not work, fetching data from the list will give you only one result because all the **data** contain the address of i wich will have the value 9 — KarimS, Jun 23 '14 at 16:21

score 0 · Answer 4 · answered Aug 03 '16 at 07:25

I approve memcpy is the bad idea in linked list. I have used it in the queue (using underneath linked list) and linked list works only as long as i don't start to free (node->data). When i do this in sequention of calls like front(), pop_front () in order to not lose my free ()ed data i start to use memcpy but that was a horrible do. I suppose that when you pas structure it deallocates only 1st field. And when you memcpy such structure ( (operating on generics void *) you only can copy pointer as this points to only one field of structure, so you lose your fields in such structures all but not first.

So to resume: Abandon memcpy in INSERT operations and also while REMOVING abandon free (node->data)

score 0 · Answer 5 · answered Mar 15 '19 at 10:48

The void pointer is what I use myself but assuming you want to do this because you do not want to rewrite the whole implementation of the list multiple times for the different data types you will be using it for, you could implement it once for example using

typedef int* DataPtr;

Then, every time you want to use the list for a different data type, you can just copy the source and header file under different names and replace int* with the data type you wish to use. I am not a huge fan of this and I would not recommend doing it, but it's worth mentioning in my opinion.

How to make a generic linked list

5 Answers5