CODEWITHSUNDEEP
javaarraylist
PeterHiggs
PeterHiggs

Reputation: 97

Efficient Way to Find Index of Object in ArrayList

I have an ArrayList which I fill with objects of type Integer in a serial fashion (i.e. one-by-one) from the end of the ArrayList (i.e. using the method add(object)). Every time I do this, the other objects in the ArrayList are of course left-shifted by one index.

In my code I want to find the index of a random object in the ArrayList. I want to avoid using the indexOf method because I have a very big ArrayList and the looping will take an enormous amount of time. Are there any workarounds? Some idea how to keep in some data structure maybe the indexes of the objects that are in the ArrayList?

EDIT: Apparently my question was not clear or I had a missunderstanding of the arraylist.add(object) method (which is also very possible!). What I want to do is to have something like a sliding-window with objects being inserted at one end of the arraylist and dropped from the other, and as an object is inserted to one end the others are shifted by one index. I could use arraylist.add(0, object) for inserting the objects from the left of the arraylist and right-shifting each time the previous objects by one index, but making a google search I found that this is very processing-intensive operation - O(N) if I remember right. Thus, I thought "ok, let's insert the objects from the right-end of the arraylist, no problem!", assuming that still each insertion will move the previous objects by one index (to the left this time).

Also when I use the term "index" I simply mean the position of the object in the ArrayList - maybe there is some more formall term "index" which means something different.

Upvotes: 2

Views: 3997

Answers (1)

Jason C
Jason C

Reputation: 40436

You have a couple of options. Here are the two basic options:

  1. You can maintain a Map<Object,Integer> that holds indexes, in parallel to the array. When you append an element to the array you can just add it to the map. When you remove an element from the beginning you will have to iterate through the entire map and subtract one from every index.

  2. If it's appropriate for your situation and the Map does not meet your performance requirements, you could add an index field to your objects and store the index directly when you add it to the array. When you remove an element from the beginning you will have to iterate through all objects in the list and subtract one from their index. Then you can obtain the index in constant time given an object.

These still have the performance hit of updating the indexes after a remove. Now, after you choose one of these options, you can avoid having to iterate through the map / list to update after removal if you make a simple improvement:

Instead of storing the index of each object, store a count of the total number of objects added so far. Then to get the actual index, simply subtract the count value of the first object from the value of the one you are looking for. E.g. when you add:

add a to end;
a.counter = counter++;
remove first object;

(The initial value of counter when starting the program doesn't really matter.) Then to find an object "x":

index = x.counter - first object.counter;

Whether you store counter as a new field or in a map is up to you. Hope that helps.

By the way; a linked list will have better performance when removing object from the front of the list, but worse when accessing an object by index. It may be more appropriate depending on your balance of add/remove vs. random access (if you only care about the index but never actually need to retrieve an object by index, random access performance doesn't matter). If you really need to optimize further you could consider using a fixed-capacity ring buffer instead (back inserts, front removes, and random access will all be O(1)).

Of course, option 3 is to reconsider your algorithm at a higher level; perhaps there is a way to accomplish the behavior you are seeking that does not require finding the objects in the list.

Upvotes: 4

Related Questions