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)

Answer 2

This insertion is happening in O(n) because it has to shift all the elements down and worst case scenario it will shift every element down. (Corrected java says it is O(n) because they use a mathematical formula to insert)

If you want a fast insertion either add it at the end of the arraylist or use a hashmap which is constant time.

Insert into hashmap: HashMap peopleMap = new Hashmap.....

peopleMap.put(person.name, person); //(or whatever you want to track)

This sets the key to th persons name and the value to person.

You can also try a hashmap with key (ehatver you want to track) and value the index where the person is in a holder array. The insert is O(i), lookup O(i) and you can sort it as well (I'll leave this as an exercise to the reader)

If the whole purpose of this is to sort, then for simplicity you could insert into a priorityQueue (nLogn) then pop everything into the array which will give you a sorted array

Answer 3

If you add using

arryListInstance.add(positionIndex, Object);

the object will be added after sifting the existing objects by 1 position. Therefore average case of this operation become O(n).

While simple add

arryListInstance.add(positionIndex, Object);

adds the object at the end of the arrayListInstance. At it's best case this operation is O(1), but at it's worst case it becomes O(n) when the maximum capacity is reached: as a new ArrayList instance is created internally and all the contents are copied there.

You are facing this issue because one of the two reasons of which 1st can be avoided:

1. You have not defined sufficient initial capacity for your ArrayList object. Therefore, before every arrayListInstance.add(positionIndex, object) a new arrayListInstance is being created with increased capacity and then the existing elements from the original list are being copied and then finally add is being performed. This can be avoided, if you know exactly how much data you want to handle by this list and define initial capacity accordingly (same as number of possible elments). If you cann't predict the initial capacity then it's better to process data in batches.
2. After every insert at any position except the last causes sifting of existing elements. This is unavoidable. Therefore, arrayListInstance.add(positionIndex, object) will be performed in O(n) time if positionIndex is not the last index of the arrayList. Even if you use LinkedList you cann't achieve constant time add operation which adds an element into the list at an index other than after the last element.