0

Hello,

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

3
Contributors
5
Replies
6
Views
9 Years
Discussion Span
Last Post by Salem
0

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

0

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.

0

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

0

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 topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.