2

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.

Improve this question
13
  • 3
    Use a Map<Integer, Integer> to store indices. Commented Feb 23, 2014 at 21:20
  • If you are adding them in some particular order, could you maybe use the size of the list to determine the index of a given item? Commented Feb 23, 2014 at 21:22
  • Also, what do you mean by "Every time I do this, the other objects in the ArrayList are of course left-shifted by one index". If you are adding to the end, the indices stay the same. Commented Feb 23, 2014 at 21:23
  • 2
    But since the indexes are changing by 1 every time I put an object in my ArrayList Huh? Adding to the end doesn't change anything else Commented Feb 23, 2014 at 21:26
  • 1
    @PeterHiggs The indexes will only be changing if you are inserting in the middle or beginning of the array. Do you have to do this? Could you append instead? Or, do you add all objects prior to having to find any? If you must insert objects but you do all insertions first, you can build the map after all objects are inserted. Commented Feb 23, 2014 at 21:27

1 Answer 1

Reset to default
4

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.

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

5 Comments

The counter idea seems really good, I was thinking also something like that (calculating the position shifts). I will try to implement it, thank you!
Worked perfectly! A million thanks! Too bad I have reputation smaller than 15 and I can't upvote, but if I could I would give you +100000000000!!!
Finally, >15 reputation, thus +1 for you!
I don't get the algorithm, what does 'first object' refer to?
@JShattu The first object in the list.

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.