Java Arraylist contains vs. for loop

Question

It is known that if I would like to find whether an object is in an arraylist I can either use the contains() method:

if(arraylist.contains(obj)) { // do things }

or I could use a for loop (providing that I have overloaded the equals() method):

for(Object o : arraylist) { 

    if(obj.equals(o)) {

        // do things

    } 

}

As it is referred in other posts, contains() actually makes use internally of a for loop and the equals() method. Therefore, my question is: is it logical to expect contains() to take more time when the arraylist is larger?

I am asking this because in my code I use contains() in order to avoid "for loops" and therefore keep the run time low and constant, but I notice that the code runs significantly slower as the arraylist size becomes larger.

"I notice that the code runs significantly slower as the arraylist size becomes larger.", that makes sense, as the bigger the array is, then the more elements there is to search through. — vallentin
– vallentin, Commented Feb 17, 2014 at 14:00
@Vallentin That was what I was thinking too. But then, there is not a performance gain (or at least not a significant one) by using contains() instead of a manually-written for loop, right? — Kotsos
– Kotsos, Commented Feb 17, 2014 at 14:01
Definitely it would be slow with increase in the size of arraylist. Usage of contains() will be in single line and would be more readable and easier than your for loop — Nandkumar Tekale
– Nandkumar Tekale, Commented Feb 17, 2014 at 14:02
Perhaps a little since you'll have less overhead, but the contains() still needs to loop through the data set. — Gimby
– Gimby, Commented Feb 17, 2014 at 14:02
ok, it is clear now, thank you all for your answers. I was just wondering if there could possibly be any significant performance gain due to some inner-mechanic of contains() that I might was not aware of, but it seems that this is not the case! — Kotsos
– Kotsos, Commented Feb 17, 2014 at 14:09

blackpanther · Accepted Answer · 2014-02-17 14:06:56Z

6

Yes, contains() for a List takes time proportional to the size of the list. If you need to be able to check membership faster, consider using, for example, a HashSet, which can check membership in constant time.

edited Feb 17, 2014 at 14:06

blackpanther

11.5k12 gold badges53 silver badges79 bronze badges

answered Feb 17, 2014 at 14:02

Ernest Friedman-Hill

81.9k11 gold badges158 silver badges192 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

holap Over a year ago

or a sorted arraylist with binary search

Bex Over a year ago

Beat me with a minute. ;)

Puce Over a year ago

And of course it depends on the location of the object in question. But, yes, in the worst case you have to check all the elements.

Colin D · Accepted Answer · 2014-02-17 14:01:43Z

3

is it logical to expect contains() to take more time when the arraylist is larger?

yes. by your own words:

As it is referred in other posts, contains() actually makes use internally of a for loop and the equals() method.

More elements to search = more time taken.

If you need constant lookup you could try using a hashset (may or may not be applicable to your situation). Alternately, if your data is sorted you could use a binary search to go from O(n) to O(lg(N)).

answered Feb 17, 2014 at 14:01

Colin D

5,6611 gold badge27 silver badges38 bronze badges

Comments

Andreas Fester · Accepted Answer · 2014-02-17 14:01:09Z

1

Is it logical to expect contains() to take more time when the arraylist is larger?

Yes. The ArrayList Javadoc says:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).

Thus, the complexity of ArrayList.contains() is O(n), which makes sense since you need to check each element of the ArrayList. There is no other option, since an ArrayList is not sorted and there is no other access path to a specific element, given its value.

answered Feb 17, 2014 at 14:01

Andreas Fester

36.8k9 gold badges101 silver badges125 bronze badges

2 Comments

Kotsos Over a year ago

"The constant factor is low compared to that for the LinkedList implementation." Does that mean that if I was using a LinkedList implementation of the List interface instead of an ArrayList the contains() method would result in nearly constant time?

Andreas Fester Over a year ago

No, a factor does not really matter for complexity analysis. Also, it says that the factor for ArrayList is lower, so if ArrayList is O(n) I would expect LinkedList to be something like O(2*n), which would be worse than ArrayList.

Bex · Accepted Answer · 2016-10-18 09:00:46Z

1

As many already pointed out: YES, it makes sense and can't be avoided.

If you do want to optimize for the contains()-case, consider using a HashSet rather than an ArrayList, provided you don't need to fill the collection with copies. The HashSet is a lot faster to search.

edited Oct 18, 2016 at 9:00

answered Feb 17, 2014 at 14:04

Bex

2,9232 gold badges34 silver badges36 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 11:54:58Z

0

The contains() method will surely take time since it's inner implementation is also a for-loop just like what you gave as an example.

The more items you have in your ArrayList the longer time it takes to finish.

Here's a similar question Any big difference between using contains or loop through a list?

edited May 23, 2017 at 11:54

CommunityBot

11 silver badge

answered Feb 17, 2014 at 14:10

krato

1,2464 gold badges14 silver badges31 bronze badges

1 Comment

Kotsos Over a year ago

I saw that answer before but it was referring to the comparison of contains() with the foreach|iterator case and I thought that it might was a somehow different situation. As it seems, I was wrong.

Collectives™ on Stack Overflow

Java Arraylist contains vs. for loop

5 Answers 5

3 Comments

Comments

2 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

Comments

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related