Searching data in a array(list)

Question

Hello everyone,

I have a ArrayList containing Attributes

class Attribute{
  private int id;
  public string getID(){
    return this.id;
  }

  private string value;
  public string getValue(){
    return this.value;
  }

  //... more properties here...
}

Well I filled the ArrayList with like hundreds of those attributes. And I want to find the Attribute with a defined ID. I want to do something like this:

ArrayList<Attribute> arr = new ArrayList<Attribute>();
fillList(arr); //Method that puts a lot of these Attributes in the list
arr.find(234); //Find the attribute with the ID 234;

Is looping over the ArrayList the only solution.

Answer 1

You want to use a Map

Answer 2

If you wish to access elements of a collection using element attributes, and this attribute is guaranteed to be unique per element, then you really should use a Map. Try a Map with the Attribute.id as the key.

Answer 3

Well something's going to have to loop over the array list, yes. There are various ways of doing this, different libraries etc.

If you fill the array in an ordered way (e.g. so that low IDs always come before high IDs) then you can perform a binary search in O(log N) time. Otherwise, it'll be O(N).

If you're going to search by IDs a lot, however, why not create a Map<Integer, Attribute> to start with - e.g. a HashMap, or a LinkedHashMap if you want to preserve ordering?

If you're only going to search for a single ID (or a few), however, this almost certainly won't be worth it - there's a cost involved in hashing, after all; filling the map will be more expensive than filling the list, and the difference is likely to be greater than the time saved looking up a few IDs.

Have you already established that this is a performance bottleneck? If so, this is an easy place to improve by using a map (or just a sorted list with a binary search). If not, I wouldn't disturb your code if it more naturally uses a list than a map - but you should certainly check whether it's a bottleneck or not.