Better way to find index of item from ArrayList<CustomObject>

Question

First of all, please correct me If I am wrong. I want to find index of Item (i.e String value) from ArrayList<CustomType> without using For Loop.

POJO:

id;
name;

Code:

ArrayList<POJO> list = new ArrayList<POJO>;

//Lots of data added to these list...

Now I want to find the id of particular name from the arraylist without using below kind of for loop.

String id = null;
// TODO Auto-generated method stub
for (int i = 0; i < list.size(); i++) {
    if("ABCD".equalsIgnoreCase(list.get(i).getName())) {
        id = list.get(i).getId();
        break;
    }
}

Ideally I don't want to implement the For loop because in some cases i have 500+ data inside the List and to find index using a For loop is not a good way to do this.

Maybe you should use Map<String, POJO> with the String being the name instead? — ShyJ
– ShyJ, Commented Nov 12, 2012 at 9:47
500 elements is not a lot, chances are this loop has no real effect on the performance of your code (even 'though it is inefficient). — Joachim Sauer
– Joachim Sauer, Commented Nov 12, 2012 at 9:49
@JoachimSauer, But I have to think of future also. May be it increase up to thousands or more than that. So that is the concern. BYW thanks for your kind response. — Scorpion
– Scorpion, Commented Nov 12, 2012 at 9:55

Maveňツ · Accepted Answer · 2016-11-09 08:03:16Z

12

You can use list.indexOf(), but in order to make it work, you need to override equals and hasCode of your POJO.

By default, two objects will be considered equal if they have the same reference. You can overwrite equals to work for your case:

public boolean equals(Object o) {
  if (!(o instanceof POJO)) {
    return false;
  }
  POJO other = (POJO) o;
  return name.equalsIgnoreCase(other.getName());
}

Overridding equals would suggest you override hashCode. For example:

public int hashCode() {
  return name.hashCode();
}

edited Nov 9, 2016 at 8:03

Maveňツ

8,28812 gold badges56 silver badges96 bronze badges

answered Nov 12, 2012 at 9:48

Dan D.

32.4k6 gold badges66 silver badges81 bronze badges

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

4 Comments

Joachim Sauer Over a year ago

This does not address the inefficiency mentioned in the question, it's "just" another way to do what the code in the question does. Also: depending on the size/use of the POJO, instantiating one just to search for a equally-named on is a bad idea. Also: most of the time having an equals() implementation on a POJO that doesn't consider the id is a bad idea.

Martin Over a year ago

Is there an option using a java.util.Comparator instead?

Dan D. Over a year ago

@Martin You can use the Comparator for sorting and then doing a binary search.

Martin Over a year ago

@Dan Interesting idea. But I would still need to overloads equals () — which does not help if you need to search for different predicates. To bad I can't use Java 8 which seem to have this function.

Subhrajyoti Majumder · Accepted Answer · 2012-11-12 09:48:39Z

4

Finding element in this way where complexity would be give you BIG-O (n). I think if you Map that would gives you better result.

HashMap would be better choice. - Where Complexity would be O(1).

answered Nov 12, 2012 at 9:48

Subhrajyoti Majumder

41.3k13 gold badges84 silver badges103 bronze badges

3 Comments

Scorpion Over a year ago

Ok. Yes I can use HashMap<String, String> for this. Thanks for your suggestion @Quoi.

Yogesh Prajapati Over a year ago

If i have a List only than it take again BIG-O (n) to convert List to Map.

Amit Over a year ago

@yogeshprajapati - the conversion is BIG-O(n) but whenever you query, it's O(1). if you need to frequently query, it's better to convert to map.

Community · Accepted Answer · 2017-05-23 12:00:08Z

3

Thank you all for your kind and quick response. But a Special thanks to Joachim Sauer. You are absolutely right that 500 elements is not a lot, chances are this loop has no real effect on the performance of your code (even 'though it is inefficient). Even I try it up to 5000 elements and still there is no negative impact on the performance.

Thank you all once again and thank you for your comment Joachim Sauer.

edited May 23, 2017 at 12:00

CommunityBot

11 silver badge

answered Nov 13, 2012 at 13:40

Scorpion

6,91116 gold badges82 silver badges126 bronze badges

Comments

Klas Lindbäck · Accepted Answer · 2012-11-12 09:48:37Z

2

If you need to search on a string value you should use a HashMap instead of ArrayList.

answered Nov 12, 2012 at 9:48

Klas Lindbäck

33.4k5 gold badges61 silver badges85 bronze badges

Comments

amit · Accepted Answer · 2012-11-12 09:58:22Z

2

You can use the List.indexOf() - but you must make sure you also override POJO.equals() - (and as part of the convention - also hashCode().

Note that nevertheless - the result will be O(n) - an alternative could be to use an sorted array (POJO[]) and use Arrays.binarySearch() or a Set/Map.

If you use an array and binarySearch() - you must make sure that POJO also implements Comparable<POJO>

Note that for a static data (your list doesn't change often/at all) - though arrays and binarySearch() is "worse" then HashSet in terms of big-O notations, in practice - it is often much faster, especially for relatively short lists.
In terms of big-O notation, a hash based solution offers a O(1) average case accessing.

edited Nov 12, 2012 at 9:58

answered Nov 12, 2012 at 9:49

amit

179k27 gold badges245 silver badges348 bronze badges

3 Comments

Joachim Sauer Over a year ago

binarySearch also requires the List to be sorted.

amit Over a year ago

@JoachimSauer Yeap, of course - I thought it was implicitly obvious, I'll add an explicit indication.

Martin Over a year ago

Is there an option using a java.util.Comparator or similar instead? So one could search for different predicates.

Fabien Leborgne · Accepted Answer · 2020-08-20 17:46:19Z

To answer to this question, I launched a benchmark with JMH.

Without surprise classic loop is the efficient way to do that.

I used a DATA_ARRAY containing 17576 elements and the searched element is at the index 7733.

Using classic Loop - 0,030 ± 0,001 ms/op:

int i = 0;
for (String str : DATA_ARRAYLIST) {
    if (str.equals("lll")) break;
    i++;
}

Using indexOf and override the equals method: 0,030 ± 0,002 ms/op

MY_DATA_ARRAYLIST.indexOf("lll");

Using data range: 0,082 ± 0,003 ms/op

OptionalInt integer = IntStream.range(0, DATA_ARRAYLIST.size())
            .filter(i -> DATA_ARRAYLIST.get(i).equals("lll"))
            .findFirst();

Using indexOf after having found with a stream: 0,074 ± 0,008 ms/op

String result = DATA_ARRAYLIST.stream().filter(e -> e.equals("lll")).findFirst().get();
DATA_ARRAYLIST.indexOf(result);

Using indexOf after having found with a parallelStream: 0,087 ± 0,023 ms/op

String result = DATA_ARRAYLIST.parallelStream().filter(e -> e.equals("lll")).findFirst().get();
DATA_ARRAYLIST.indexOf(result);

However if the searched element is in the last index:

Classic Loop : 0,066 ± 0,002 ms/op
Parallel Stream : 0,121 ± 0,023 ms/op
Stream : 0,161 ± 0,024 ms/op

And then if you have 456 976 elements:

Classic Loop : 2,172 ± 0,297 ms/op
Parallel Stream : 3,145 ± 0,380 ms/op
Stream : 6,081 ± 0,097 ms/op

As you can see it's really hard to beat the Loop!

Collectives™ on Stack Overflow

Better way to find index of item from ArrayList<CustomObject>

6 Answers 6

4 Comments

3 Comments

Comments

Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

4 Comments

3 Comments

Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related