Searching data in a array(list)

Question

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.

Jon Skeet · Accepted Answer · 2010-01-03 21:01:02Z

5

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.

answered Jan 3, 2010 at 21:01

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

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

1 Comment

Timo Willemsen Over a year ago

Thanks. Yes I will have to lookup almost every attribute in the hashmap. And I have not written all the code yet. So I don't mind changing it a lot, I just want to learn. Thanks alot!

Jerome · Accepted Answer · 2010-01-03 21:00:19Z

1

You want to use a Map

answered Jan 3, 2010 at 21:00

Jerome

8,4572 gold badges35 silver badges41 bronze badges

Comments

alphazero · Accepted Answer · 2010-01-03 21:00:57Z

1

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.

answered Jan 3, 2010 at 21:00

alphazero

27.3k3 gold badges32 silver badges27 bronze badges

Collectives™ on Stack Overflow

Searching data in a array(list)

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related