Arraylist insert at specific index performance query

[Maya Dolas]

Given an arraylist of objects with size 10. I need to insert two elements, one at index 2 and other at index 9. Which of the two insertions would be faster?

[Arka Guhathakurta]

ArrayList is nothing other than a LIST itself so whether you insert at 2 or 9 doesn't make a difference as far as insertion time is concerned. However note that the situation would have been different had it been a LinkedList since it involves an insertion order. The insertion has to take place though HEAD and ends at TAIL. So in such a situation insertion at 2 will definitely be faster than insertion at 9.
Please correct me if I am wrong.

[Rob Spoor]

ArrayList uses an array as its backing storage. When you add something at index 9, it has to shift the element at position 9 up by one. That's one element. When you add something at index 2, it has to shift the elements at positions 2 and higher up by one. That's 8 elements initially.

LinkedList will not shift anything but instead just puts a new link in between. That is equally fast regardless of the position. However, it first must find the position, and that will take (just a bit) longer for index 2. That might surprise you, but LinkedList knows that 9 is nearer to its end than to its start so it will go backwards from the end.

[Maneesh Godbole]

"Maya Dolas"
Please check your private messages for an important administrative matter.