This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Java in General and the fly likes Searching in ArrayList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Searching in ArrayList" Watch "Searching in ArrayList" New topic
Author

Searching in ArrayList

pramod talekar
Ranch Hand

Joined: Apr 26, 2010
Posts: 316

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.


Thanks,
Pramod
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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.
 
Consider Paul's rocket mass heater.
 
subject: Searching in ArrayList
 
Similar Threads
how to define criteria for search
Unable to create child elements.... XMl Parsing...
Unable to create child elements.... XMl Parsing...
How do I search after a number in a vector element ?
Search using XPath