Hello,

Can anyone provide me the optimized and with low complexity program to remove the repeated elements in an single linked list program?

Is the single linked list already sorted, so identical elements are adjacent?

If its an sorted array that makes it easy.
But my question is incase of Unsorted array.
I know one method is liner search method. Where each indivual element is check once with all elements. But the complexity is O(n*n)

regards
Prakash

O-notation always covers the worst-case scenario. I don't think you can get an algorithm better than O(n*n) without sorting.

However, it is always possible to reduce the number of comparisons done. Things that work along the lines of a hash-table would probably work best.

AFAIK.

O-notation always covers the worst-case scenario. I don't think you can get an algorithm better than O(n*n) without sorting.

However, it is always possible to reduce the number of comparisons done. Things that work along the lines of a hash-table would probably work best.

AFAIK.

Ya that is what the solution i am looking for. Reduced number of comparisons and as you said can be done with code that goes along with Hash Table.
Actually I am looking for the Pseudo code atleast.

However thanks for the reply.

cheers

Basically, you use the hash to answer the "doesElementExist" test. If it doesn't, copy it to the unique list.

Or you could just insert the whole list into a balanced binary tree, then flatten it into a list when you're done. The inserts will be O(log2(n)) on average, either finding the item already present or finding where to insert it.

This article has been dead for over six months. Start a new discussion instead.