I want to write a method to remove consecutive items with duplicate data values from a singly linked list. The method should return the number of items removed. The method should clean up memory as required, and should assume that memory was allocated using new.

For example, passing in the list
->a->b->c->c->a->b->b->b->a->null
should result in
->a->b->c->a->b->a->null
and return 3

The list item definition and function declaration are given below

struct litem {
     char data;
     litem* next;
};

int remove_consecutive_duplicates( litem*& list );

I have a simple logic to check the next element recursively & removing the element if its duplicate.
But, i would like to know how many efficient ways to do this ? All ideas welcome from C++ gurus..

Recommended Answers

All 3 Replies

I don't know about efficiency, but you can save a lot of code by using the list::unique method.
The number of items deleted is the item count difference between the previous and current list. example

Edit:
However you have to use the std::list. Can't be used for your custom list object.

WolfPack: Thanks for u'r reply.
list::unique will remove all duplicate elements in the list. But, i need to remove only consecutive duplicate elements. any more ideas other than recursive logic ?

No it doesn't remove all the duplicate elements in the list if the list is not sorted.
Look at the output of the example. There are two 10s in the resulting list.

The initial list is c1 = -10 10 10 20 20 -10
After removing successive duplicate elements, c2 = -10 10 20 -10

As for a non-recursive algorithm, this is linear. Correct any mistakes.

delete_count = 0;

Current = List_Top_Element ;
while( Current != Null ){
    if( Current->Next == Null ){
        break;
    }
    If( Current == Current->Next ){
        Delete Current->Next ;
        delete_count = delete_count + 1;
    }
    else{
        Current = Current->Next ;
    }
}
return delete_count;
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.