-2

I have a problem that's been bothering me for some time. I have a software where I generate a certain number of objects in a physical world, storing them in an ArrayList. However, this implementation generates lags when removing objects from the ArrayList.

A static array implementation does not lead to lags, but is less practical as I cannot use "add" and "remove".

I'm assuming the lags with ArrayLists are due to memory freeing and re-allocation. As my ArrayList has a fixed maximal size, is it possible to preallocate it a certain memory, to avoid these issues? Or is there another solution for this?

Thanks a lot in advance for any help!

ProgressiveMonkey
  • 315
  • 1
  • 4
  • 11
  • When adding an element to a List, you just put a reference to the object to the List. I don't think it can cause any trouble. Maybe the problem is with constructing your objects? – iozee Jun 22 '12 at 07:52
  • 1
    What do you mean by "a static array implementation"? – Jon Skeet Jun 22 '12 at 07:53
  • can you show the code that you are using when you found this? I believe that an ArrayList uses a backing array with prealocated size – John Kane Jun 22 '12 at 07:53
  • @JohnKane Yes it is. [Sample](http://www.docjar.com/html/api/java/util/ArrayList.java.html) from Open JDK, line 111. – Mikita Belahlazau Jun 22 '12 at 07:56

2 Answers2

2

I normally would not just repost someone elses answer, but this seems to fit very well.

Community
  • 1
  • 1
John Kane
  • 4,383
  • 1
  • 24
  • 42
2

The problem here is that an ArrayList is internally implemented, as the name states, with an array. This means that elements of the collection can't be freely inserted or removed without shifting the elements after the index you are working it.

So if your collection has a lot of elements and you, for example, remove the 5th, then all the elements from 6th to the end of the list must be shifted to the left by one position. This can be expensive indeed and leads to a O(n) complexity.

To avoid these issues, you should choose an appropriate collection according to the most common operations you are going to use on it. A LinkedList can be good if you need to iterate, remove (actually the removal requires to find the element anyway so it's good just if you are already enumerating them) or insert elements but whenever you want to access a specific index you are going into troubles.

You could also look for a HashSet or a TreeSet, they could be suitable to your solution.

In these circumstances knowing how most common data structures work and which are good/bad for is always useful to make appropriate choices.

Jack
  • 131,802
  • 30
  • 241
  • 343