aspose file tools*
The moose likes Beginning Java and the fly likes most efficient way to remove duplicates from list? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "most efficient way to remove duplicates from list?" Watch "most efficient way to remove duplicates from list?" New topic
Author

most efficient way to remove duplicates from list?

Johann Dobbins
Ranch Hand

Joined: Oct 16, 2008
Posts: 62
i have:



is there a more efficient method that maintains order?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18907
    
    8

What is this "order" you want maintained? Is it insertion order, or do these objects have a natural ordering? (And if the latter, why is it a List<Object>?)
Johann Dobbins
Ranch Hand

Joined: Oct 16, 2008
Posts: 62
i would like the objects to remain in the same order as in the list. i guess that would be insertion order?
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
You could copy the elements of the list into a java.util.LinkedHashSet. That's an O(n) operation compared to the O(n^2) complexity of your current method.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Johann Dobbins
Ranch Hand

Joined: Oct 16, 2008
Posts: 62
Garrett Rowe wrote:You could copy the elements of the list into a java.util.LinkedHashSet. That's an O(n) operation compared to the O(n^2) complexity of your current method.


where can i find the O complexity of java methods? I actually need to end up with a list (to fit method signature in interface definition), so I would have to convert the linkedHashset back to a list, but this would still be O(n) (right?)


Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
where can i find the O complexity of java methods?

Sometimes it is specified in the documentation, but many times you just have to reason about it on your own.

I actually need to end up with a list (to fit method signature in interface definition), so I would have to convert the linkedHashset back to a list, but this would still be O(n) (right?)


Yes that's still O(n) (O(2n) == O(n)). Further you could do it in a one-liner

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: most efficient way to remove duplicates from list?