# Thread: removing duplicates from a linked list

1. ## removing duplicates from a linked list

I am trying to write a function that removes duplicates from a linked list.

Here is the code I have:

Code:
```/*
* Function remove_dups()
*
* This function removes all duplicates from the list. Any node that is
* removed is also freed.
*
*/

{
node * current_ptr;
node * prev_ptr;
node * temp_ptr;

current_ptr = _first_element;
temp_ptr = _first_element->next;

while (current_ptr != _last_element)
{
if (occurrences(current_ptr->data) == 1 && current_ptr->next != NULL)
{
current_ptr = current_ptr->next;
}

while (temp_ptr->data != current_ptr->data && temp_ptr->next != NULL)
{
temp_ptr = temp_ptr->next;

if (temp_ptr == NULL)
{
current_ptr = current_ptr->next;
break;
}

}

if (current_ptr == _last_element)
break;

if (temp_ptr->data == current_ptr->data)
{
prev_ptr = _first_element;

while (prev_ptr->next!= temp_ptr)
{
prev_ptr = prev_ptr->next;
}
prev_ptr->next = temp_ptr->next;
_remove(temp_ptr);
temp_ptr = _first_element;
}

}

}```
If my input is 1,2,3,1,2,3 this function will remove the 1 and the 2, but will leave the duplicate 3. So my output will be 1,2,3,3.

Any ideas why this is happening?

Brian

2. To tell the truth, I didnīt understand your algorithm very well, I would have done different. Anyway, I noticed the condition of your main loop: while (current_ptr != _last_element). But if _last_element really points to the last element, you will never compare him to other elements, but I may have understood really bad your algorithm!
I would do like this:
Code:
```void linklist::remove_dups()
{
node* current = _first_element;
node* next_nd;
node* previous;

while( current != NULL ){

next_nd = current->next;
previous = current;

while( next_nd != NULL ){
if( next_nd->data == current->data){
previous->next = next_nd->next;
delete next_nd;
next_nd = previous->next;
}
else{
previous = next_nd;
next_nd = next_nd->next;
}
}
current = current->next;
}```
I have made a quick example, just to show that really works :P
Hope that helped!

3. ## thanks

That helped a lot. I need to use a member function to perform the actual removing, but your algorithm helped me get mine straight.

Thanks.

Brian

Popular pages Recent additions