Need an implementation for a generic list in C to avoid duplication when inserting
I'm new to C and I am trying to implement a linked list whose nodes are defined like this:
typedef struct _cListNode
{
void *_data; //generic pointer to any data type
struct _cListNode *next; //next node in the list
} cListNode;
I need a function InsertElement (cList myList, void * dataToInsert) to not increment the list when there is already an inserted element (i.e. no duplicates). My current problem is that I cannot find a way to compare dataToInsert (parameter) with _data (inside my node).
I thought about traversing the list externally before calling the InsertElement function and taking care of the comparison outside of the list implementation where I know what the type is, but I was hoping for a better design / solution.
source to share
Given two void pointers, it is impossible to compare their data. This is because you don't know the size of each of the pointers. If you want to compare your data, you will need to keep the pointers and the size of their data. Then you can use memcmp to compare the memory pointed to:
typedef struct _cListNode
{
void *_data; //generic pointer to any data type
size_t size;
struct _cListNode *next; //next node in the list
} cListNode;
int memcmp ( const void * ptr1, const void * ptr2, size_t num );
So:
memcmp(node_data_ptr, new_data_ptr, size_of_item_pointed_at);
You should only do memcmp if the size is the same for both pointers, otherwise they are clearly different from each other and you don't want to end up comparing invalid memory.
Another option is to compare the pointers themselves and see if they point to the same section of memory. It depends on what you mean by "duplication".
source to share
You might want to do something like this. I assume the structure of the linked list looks like this:
typedef struct _cList
{
cListNode* head;
cListNode* tail;
size_t size;
} cList;
int contains(cList* list, void* data, size_t dataSize)
{
cListNode* temp = list->head;
while(temp)
{
if(!memcmp(data, temp->_data, dataSize))
return 1;
temp = temp->next;
}
return 0;
}
void InsertElement(cList* myList, void *dataToInsert, size_t dataSize)
{
if(!contains(myList,dataToInsert, dataSize))
{
//Insert Data
}
else
{
//Data Is already present.
}
}
You have to create struct cListNode
as stated in @ jmh's answer.
source to share