Deleting the Repetetive elements in an array

[prakash.kudreka]

Hello,

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

[Salem]

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

[prakash.kudreka]

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

[Duoas]

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.

[prakash.kudreka]

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

[Salem]

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.