CODEWITHSUNDEEP
java
lakeskysea
lakeskysea

Reputation: 621

What is the time complexity of adding an element at the beginning of an ArrayList?

Say I have a ArrayList with n element in this array, and I add an element at the beginning:

myArrayList.add(0,'some value');

What will be the time complexity of this operation?

The Java Doc doesn't specify this.

Also

I just start learning Java, and I saw the sentence

An ArrayList in Java is a List that is backed by an array.

What does 'backed' here mean? Thank you!

Upvotes: 13

Views: 24167

Answers (4)

Clark Thomborson
Clark Thomborson

Reputation: 180

The ArrayList documentation is indeed obscure on this point -- I looked at it in SE11 just now, and it's unchanged since the first release of the Collections Framework (in Java 1.2).

I believe the intent of the authors of the ArrayList documentation was to specify that, on any implementation of Java, the appending operation (i.e. the add(E e) method) must run in constant amortized time, and that the list insertion operation (i.e. the add(int index, E e) method) must run in O(n) time, where n is the size of the list.

Upvotes: 1

Roland
Roland

Reputation: 7853

  • Building the list from scratch and adding lots of elements to the beginning runs in quadratic time: O(n2).
  • Adding all elements to the end of the list and then calling Collections.reverse(list) runs in linear time: O(n).

Upvotes: 0

gkamal
gkamal

Reputation: 21000

Adding an element to beginning of array is O(n) - it would require to shift all the existing elements by one position.

All elements in an array list are stored in a contiguous array. If you add more elements than the current size of the array - it will be grown automatically to accommodate the new element.

Addition to the end is O(1) amortized over multiple insertions.

Upvotes: 27

Louis Wasserman
Louis Wasserman

Reputation: 198023

ArrayList.add(0, element) takes linear time, but the constant is very low, because it can use the blazing fast System.arraycopy.

Upvotes: 13

Related Questions