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).

Answer 1

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)