Remove duplicates in a linked list before adding - C

Question

Hi,

My question is about removing duplicates from a linked list. But i want to do it before adding to linked list.

struct myStr{int number; mystr *next;}
void append(mystr **q,int item)
{
myStr *temp;
temp = *q;
myStr *newone;
if(*q==NULL)// There should be control of previous elements. Call of keysearch function.
     {   temp = (myStr *)malloc(sizeof(myStr));

          temp->number =size;
          temp->next=NULL;
          *q=temp;
     }
     else //And also here
     {  temp = *q;
         while(temp->next !=NULL)
         {  temp=temp->next;
         }
         newone = (myStr *)malloc(sizeof(myStr));
         newone->count = size;
         newone->next=NULL;
         temp->next=newone;

     }
}
int keysearch (myStr *p)
{
struct myStr *temp = p;
int found = 0;
int key= p->number;
while (temp->next != NULL) 
 {
 if(temp->number == key)
    {
   return 1;
//break;
        }
     temp = temp->next;   
     }
    return 0;
    }

My problem is in keySearch. I don't know what is wrong? Or is there another way for doing this.

Answer 1

This looks kind of questionable:

 if(temp->number == key)
    {
   found = 1;
    }
 temp = temp->next;   
 }
return found;
}

Why not just return 1 as soon as tmp->number == key ? There's no reason to continue in the loop (or at least the rest of the code you pasted shows no reason) once a match is found.

The other thing is, I think you want to be testing while (temp->next != NULL) , instead of comparing an integer to NULL, especially before assigning temp to temp->next.

You'll also want to use something more along the lines of:

int keysearch (myStr *p, int key)

And have the caller responsible for passing the value to search.

Answer 2

What do you mean by "its wrong"?

Beside that:

First. temp->number is an integer and you might want to check for the next pointer in your while statement.

Second. if you assign temp = p and key the value of p->number than youre check in the while loop will always be true for the first iteration.

Third. It might cause a crash if temp is not valid in your while statement.

Answer 3

In your code, you have 2 comments where you expect to be invoking keySearch. In fact, you only need it in 1 place - the second comment. This is because the first place is where you are creating a brand new list, so of course nothing will be in it that you need to worry about.

In the second case, you want to call this keySearch method. There are 3 types of keySearch methods I can think of that would be useful:

1. Invoke a method int keySearch(mystr *p, int value) that looks through p for value and, if found, returns true (non-zero number)
2. Invoke a method int keySearch(mystr *p) that looks through p for any duplicates and removes them. This would not be called on every append, though, and the implementation above suggests this is not what you are trying to do. It's a lot more work to do this, in any event.
3. Invoke a method int keySearch(mystr *p) that looks through p to see if the first value in q is duplicated, returning true if it is. It seems this is what your method is trying to do.

Based on the signature of the method, you are trying to do #2 or #3. But both of those are wrong-headed - they assume you've already added the duplicate to the list. What you should be doing instead is trying to prevent a duplicate from being added in the first place. The method as it is does not have enough information to do that, though. It needs the value of the element that has not yet been added.

I would suggest changing the method to the one in #1, and passing in the value you want to add. If it is found, return 1. In the append method, if this function evaluates to 1, don't append anything. Otherwise append the new element.

int keysearch(struct myStr *p, int value)
{
   if(p == NULL) return 0;
   // reusing p is fine - it's a local variable
   while(p != NULL)
   {
      if(p->number == value) return 1;  // return if value exists already
      p = p->next;                      // go to next element
   }
   return 0;
}

Now, when you are about to add an element, first run it by this method. If the method returns 1, leave your append method immediately - there is nothing to be done. If it returns 0, then malloc your new node and set it to the end of the list.

---

EDIT: An enterprising codesmith may want to optimize slightly so that on every append we don't do 2 loops through the whole list (one for keySearch, and then one to find the last element for actual appending). You can do this by modifying keySearch slightly...

// returns NULL if p is empty / value exists; otherwise returns the last element
struct myStr *keysearch(struct myStr *p, int value)
{
   // same logic, different return values; integration into append changes too!
}