Add element in an ArrayList efficiently at a given index in java

Question

I need to insert a element of type Person (my own defined class) in an ArrayList at index i

I know I can use add(int index, E element).

But is there any efficient method to do this as in my list it is taking around 1.5 ms on an average (data collected over 1000 insertion and then average).

Solution

If your task is more insertion / deletion intensive, you can always use java.util.LinkedList.

• ArrayList has a limited size. Every time you add an element, Java ensures that it can fit - so it grows the ArrayList. If the ArrayList grows faster, there will be a lot of array copying taking place.
• LinkedList just adds the element to the correct place (linking the nodes around), without growing and copying of the whole ArrayList.
• Drawbacks of the LinkedList are when you are searching for an element. Since it has no indexes, it must traverse from the beginning to the end of the list to find an item.

For LinkedList:

• get is O(n)
• add is O(1)
• remove is O(n)
• Iterator.remove is O(1)

For ArrayList:

• get is O(1)
• add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• remove is O(n)

Comments

[learner]

how can it be O(n^2) I need to shift complete array i will start from end. I guess this is how System.arraycopy work and it is really fast

[Andrea Ligios]

put(index, value); where index is the key

[learner]

@waf but that actually depend on way of implementation if what you are saying is always correct then insertion sort will be O(n^3) isn't it ?

[learner]

I need to first do a binary search to find index and then need to insert, I can't use Linkedlist as what I am doing is to insert in tableview which is using arraylist as underlying model (ObservableList<S>).

[darijan]

Can you be more specific on the TableView?

[Guillaume Polet]

This is a copy of this answer (which is much more detailed)

[learner]

@GuillaumePolet +1 I have already check that answer before asking my question

[William Falcon]

Just read the details of Java's implementation and it is O(n) due to some formula they use for insert

[Jerry Destremps]

You are using the same add in both cases, thus the down vote. The second add is not the "simple" add.

[anhtuannd]

should be arryListInstance.add(Object);