CODEWITHSUNDEEP
ccomparisonlinked-listvoid-pointers
wotann07
wotann07

Reputation: 410

Need implementation for generic list in C that avoids duplicates at insertion

I'm a newbie in C and I am trying to implement a linked list which nodes are defined as follows:

typedef struct _cListNode
{
    void *_data;                //generic pointer to any data type
    struct _cListNode *next;    //next node in the list
} cListNode;

I need the InsertElement(cList myList, void *dataToInsert) function not to grow the list when the element that is being inserted is already in (i.e. no duplicates). My current problem is that I can't find a way to compare dataToInsert (the parameter) with _data (inside my node).

I thought of traversing the list externally before calling the InsertElement function and taking care of the comparisons outside the implementation of the list where I do know what the type is but I was hoping for a better design/solution.

Upvotes: 3

Views: 323

Answers (2)

jmh
jmh

Reputation: 9336

Given two void pointers it is not possible to compare their data. This is because you do not know the size of the types of each of the pointers. If you want to compare their data, then you would need to store the pointers and the size of their data. Then you could use memcmp to compare the memory pointed at:

 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 the memcmp if the size is the same for both pointers, otherwise they are clearly different and you don't want to end up comparing invalid memory.

Your other option is to compare the pointers themselves and see if they are pointing at the same section of memory. It depends on what you mean by "duplicate".

Upvotes: 4

sgarizvi
sgarizvi

Reputation: 16796

You may want to do something like this. I'm supposing your linked list structure is as follows:

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 should create the struct cListNode as specified in @jmh's answer.

Upvotes: 2

Related Questions