Java collection optimized for add (insert) operations only

Question

I am looking for Java collection. My only two expectations are:

1. Fast O(1) insertion / add operations.

2. The ability to iterate over this collections.

I don't care about the elements order.

• LinkedList is not the optimal candidate because of many small allocations (for every new node).
• ArrayList is not the optimal candidate because of internal array resizing when there is no more space left.

Can you propose other Java collection optimized for such operations?

In other words, I am looking for the hybrid between LinkedList and ArrayList. Something like LinkedList where the additional memory allocations are preallocated for the N next elements - not for every new element like for LinkedList.

• Lorelorelore: Do you need repetition on this collection? If you don't care of repetition you can use HashSet.
• adaslaw: @Lorelorelore: yes, I care about repetitions.
• Peter Lawrey: You can have a LinkedList of ArrayLists and iterate over them using a Stream.flatMap
• Wietlol: if you know the approximate length before you start adding, an ArrayList can be good because you can use .ensureCapacity(). however, if you insert in the middle, you still need to shift, if you really want O(1) insertion, you could use a HashMap or a ManyValuesMap (basically a Map<K, Collection<V>> (iirc guava has a good implementation) you could also go for a binary tree if the order matters, but insertion will not be as fast as the map approach
• adaslaw: @PeterLawrey: as far as I see Stream.flatMap would do the job here but: * it looks like an overkill for this problem :) * I don't know what is the performance of such solution. It is needed to perform some performance measurements to asset the runtime performance.

Answer 1

Since you care the memory allocation that much, don't use ArrayList nor LinkedList but use a simple array which is easy to manipulate and store large data.

Allocate the size of an array with ex. 1'000'000 elements:

MyClass[] array = new MyClass[1000000];

• Assigning an object to an index of array costs O(1) as well.
• Iteration is simple using the for-loop.

If you wish to perform additional operations, use the for-loop iteration. The main disadvantages are:

• Fixed size once declared.
• Can store a single type.

---

Also, consider the Stream-API (worth to try, I have no idea about the performance here):

Arrays.stream(array)...

• adaslaw: No. I am not able to preallocate such big chunks of memory.
• Nikolas: How big chunks of memory?
• adaslaw: I would expect that size of chunks wold be configurable via constructor argument. But we can also assume that this is 10 or 100 :)
• Nikolas: If I understand you well, you can do MyClass[] array = new MyClass[constructorArgument]; where int constructorArgument would be the size of the input?
• adaslaw: Yes, I can do it. But this collections must able to grow. I don't know if particular collection will contains 10 or 10'000'000 elements.

Answer 2

In LinkedList you are not allocating new memory to the list, just make a refenrence to the new element.

LinkedList is working like a chain, that contain reference to the previous/next element in the chain. If there is no previous element that mean, this is first element. If there are no reference to the next element, this mean it is last element of the list. So adding new element you are just creating reference at the end of your "chain".

It make allocating new elements really fast, but if you want to reach, for example 10th element on the list it need to iterate over the "chain" -> so it means that it is going to visit each element from the first one till the 10th. This is the biggest disadvantge comparing to the ArrayList, where reaching the element with specified index has O(1) performance. (using list.get(index) method)

Answer 3

Have you thought about using a Queue for java.util.Queue ?

It has O(1) time complexity for insertion and it is iterable with an iterator.

• adaslaw: But I am afraid that Java Queues implementations have the same drawback like ArrayList drawbacks described by me in my original question.