Summary

Add information about asymptotic running time of certain methods of ArrayList.

Problem

ArrayList currently has a short paragraph describing the asymptotic running time of several methods. However, information about several other methods is missing from this list.

Note that most classes in the JDK do not include asymptotic running time or other performance characteristics of their operations. ArrayList does, however, for historical reasons probably having to do with contrasting it with LinkedList. Since ArrayList does have this information, it should be kept up to date.

Solution

Add information for the missing methods.

Specification

Changes to the java.util.ArrayList class specification:

  * {@code Vector}, except that it is unsynchronized.)
  *
  * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
- * {@code iterator}, and {@code listIterator} operations run in constant
- * time.  The {@code add} operation runs in <i>amortized constant time</i>,
- * that is, adding n elements requires O(n) time.  All of the other operations
- * run in linear time (roughly speaking).  The constant factor is low compared
- * to that for the {@code LinkedList} implementation.
+ * {@code getFirst}, {@code getLast}, {@code removeLast}, {@code iterator},
+ * {@code listIterator}, and {@code reversed} operations run in constant time.
+ * The {@code add}, and {@code addLast} operations runs in <i>amortized
+ * constant time</i>, that is, adding n elements requires O(n) time.  All of
+ * the other operations run in linear time (roughly speaking).  The constant
+ * factor is low compared to that for the {@code LinkedList} implementation.
  *
  * <p>Each {@code ArrayList} instance has a <i>capacity</i>.  The capacity is
  * the size of the array used to store the elements in the list.  It is always