Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

most efficient way to remove duplicates from list?

 
Johann Dobbins
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i have:



is there a more efficient method that maintains order?
 
Paul Clapham
Sheriff
Posts: 21107
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Johann Dobbins
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic