• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Searching in ArrayList

 
pramod talekar
Ranch Hand
Posts: 347
Eclipse IDE Java Opera
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

If my list contains over 1 lac elements then how to effectively search a particular element ?
If the element I'm looking happens to be at the last index then it will take lot of time to search.
Also how contains() work here?
Thanks.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you're just occasionally searching for one item, it won't take long. You can probably do millions of equality tests per second.

However, finding an item in an unsorted list is an O(N) operation, so if you're doing it a lot, it could become a performance issue. In that case, you would want to sort the List with Collections.sort(), and then use Collections.binarySearch() to find it in O(log N) on an ArrayList.

Another alternative, if you won't have duplicate elements, is to use a SortedHashSet.

As for how contains() works, you can read the docs as well as I can. That's all that's specified. Anything else is left up to the implementation. You can look at the source code to see for yourself if you want. It's in src.zip in your JDK download. However, the most likely implementation for a List is to iterate over the List, comparing each element until we find a match or reach the end of the List.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic