Thread: removing duplicates from a linked list

  1. #1
    Registered User brianptodd's Avatar
    Join Date
    Oct 2002
    Posts
    66

    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.
     *
     */
    
    void linklist::remove_dups()
    {
    	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
    "In theory, there is no difference between theory and practice. But, in practice, there is."
    - Jan L.A. van de Snepscheut

  2. #2
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244
    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!
    Nothing more to tell about me...
    Happy day =)

  3. #3
    Registered User brianptodd's Avatar
    Join Date
    Oct 2002
    Posts
    66

    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
    "In theory, there is no difference between theory and practice. But, in practice, there is."
    - Jan L.A. van de Snepscheut

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM