1

is it possible to determine the ArrayList-index of an element inside the ArrayList based on one of its attributes?

In my particular case I have an Object "worker" with the attributes "name" and "worker_id". The worker_id is an ID I get from the database.

Since the first worker-object inside the ArrayList doesn't necessarily start with 0 (and may have gaps), it's not the same ID as the index each element has inside this ArrayList.

Now I want to determine this particular index of a worker-object inside the ArrayList based on its attribute "worker_id". However: since the list can be very long, I'd like to not have to iterate over the worker-ArrayList everytime.

Using a HashMap might be a solution, but I'd like to use an ArrayList if possible, because I normally won't need a key (except in this case).

Any suggestions are welcome!

Thank you in advance, Igor.

Improve this question
3
  • Isn't the worker_id the key? Commented Sep 15, 2010 at 7:50
  • is the list sorted by worker_id? Commented Sep 15, 2010 at 8:45
  • The list is sorted by worker_id; however: worker_id is not the key, since worker_id can be 5, 7, 12, 15 etc. It's the id of the worker_table - and that id is on auto_increment, therefore starts off at 1 and may contain gaps. Commented Sep 15, 2010 at 10:45

7 Answers 7

Reset to default
4

Since the first worker-object inside the ArrayList doesn't necessarily start with 0 (and may have gaps), it's not the same ID as the index each element has inside this ArrayList.

It sounds to me that the list is at least sorted? In that case, you could use a binary search, which is slightly faster than a linear scan of the list.

Another option is to define two workers to be equal if they have the same worker_id. Then you could simply do int index = workerList.indexOf(new Worker(idToSearchFor));

Using a HashMap might be a solution, but I'd like to use an ArrayList if possible, because I normally won't need a key (except in this case).

Well, to be honest, when I use a map it is seldom because I couldn't do it with a list, but rather because the interface of a map is nicer to work with, and results in cleaner code. So, even though you may think that a HashMap is an overkill, it may be worth it, solely because it's slightly more logical and the code ends up being a bit easier to read.

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

1 Comment

Actually all of the solutions posted here are interesting. I try to overwrite equal and use indexOf with some sort of "dummy" worker-object, that only contains a valid worker_id. Thanks for all other suggestions though :).
1

You may consider using a LinkedHashMap. This offers the best of both worlds: it can behave as a list due to its predictable iteration order and it offers fast (O(1)) key based lookup at the same time.

The price is, as can be expected, a slight performance penalty (compared to ArrayList).

Improve this answer

1 Comment

I'll look into this. However: I am using Google Web Toolkit and therefore it might not be implemented in there - I'll have to check. I'd prefer to keep the ArrayList though. Thank you very much for your answer though :).
0

You need to check every object for it's id. There is no direct way i guess. Iterate through all the objects and check for the id.

Improve this answer

Comments

0

Something like:

List<Worker> workers = // ...
for (int i = 0; i < workers.size(); i++) {
    if (/* ... */) {
        return i;
    }
}
Improve this answer

1 Comment

That's something I came across too, but thought there must be a smarter solution than just iterating hundrets of times through the list.
0

int find(List <A> list, Object sth) { Iterator it = list.iterator(); int index = 0; while(it.hasNext()); A current = it.next(); if (el.getSth().equals(element)) { return index; } index++; } return -1; }

Improve this answer

Comments

0

Create the List as big as the largest worker_id value. while inserting the object, insert it at worker_id number. like

list.add(obj.worker_id,obj);
while retrieving
list.get(obj.worker_id);

yes, its not space effecient solution, the space efficient solution is to use the Hashmap (or its variant) as everyone else have already mentioned.

Improve this answer

Comments

0

I think you have two choices:

  1. Build an index. A hash is a decent mechanism for accessing an index, but there are others. A simple sparse array might work in this context, for example.
  2. Search for the matching element. A linear scan is O(n) but a binary search is O(log n) so will be better if your list is sorted (assuming any non-trivial length).
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.