CODEWITHSUNDEEP
calgorithmliststructprimitive-types
KarimS
KarimS

Reputation: 3892

How to make a generic linked list

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.

Upvotes: 3

Views: 4763

Answers (5)

Theo Stefou
Theo Stefou

Reputation: 645

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.

Upvotes: 0

Michał Ziobro
Michał Ziobro

Reputation: 11752

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)

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

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.

Upvotes: 1

zbs
zbs

Reputation: 681

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?

Upvotes: 2

Diego Allen
Diego Allen

Reputation: 4653

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.

Upvotes: 3

Related Questions