src/share/classes/java/util/ArrayList.java
Print this page
rev 9490 : 8035584: ArrayList(c) should avoid inflation if c is empty
Reviewed-by: martin
*** 28,64 ****
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
/**
! * Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
! * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
! * <tt>Vector</tt>, except that it is unsynchronized.)
*
! * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
! * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
! * time. The <tt>add</tt> 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 <tt>LinkedList</tt> implementation.
*
! * <p>Each <tt>ArrayList</tt> 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
* at least as large as the list size. As elements are added to an ArrayList,
* its capacity grows automatically. The details of the growth policy are not
* specified beyond the fact that adding an element has constant amortized
* time cost.
*
! * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
! * before adding a large number of elements using the <tt>ensureCapacity</tt>
* operation. This may reduce the amount of incremental reallocation.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
! * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
* and at least one of the threads modifies the list structurally, it
* <i>must</i> be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
* resizes the backing array; merely setting the value of an element is not
* a structural modification.) This is typically accomplished by
--- 28,64 ----
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
/**
! * Resizable-array implementation of the {@code List} interface. Implements
* all optional list operations, and permits all elements, including
! * {@code null}. In addition to implementing the {@code List} interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
! * {@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.
*
! * <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
* at least as large as the list size. As elements are added to an ArrayList,
* its capacity grows automatically. The details of the growth policy are not
* specified beyond the fact that adding an element has constant amortized
* time cost.
*
! * <p>An application can increase the capacity of an {@code ArrayList} instance
! * before adding a large number of elements using the {@code ensureCapacity}
* operation. This may reduce the amount of incremental reallocation.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
! * If multiple threads access an {@code ArrayList} instance concurrently,
* and at least one of the threads modifies the list structurally, it
* <i>must</i> be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
* resizes the backing array; merely setting the value of an element is not
* a structural modification.) This is typically accomplished by
*** 92,101 ****
--- 92,103 ----
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
+ * @param <E> the type of elements in this list
+ *
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
* @see List
* @see LinkedList
*** 139,160 ****
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
! super();
! if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
! this.elementData = new Object[initialCapacity];
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
- super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
--- 141,164 ----
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
! if (initialCapacity > 0) {
! this.elementData = new Object[initialCapacity];
! } else if (initialCapacity == 0) {
! this.elementData = EMPTY_ELEMENTDATA;
! } else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
! }
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
*** 163,193 ****
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
/**
! * Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
! * the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
/**
! * Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
--- 167,201 ----
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
+ if (!c.isEmpty()) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
+ } else {
+ this.elementData = EMPTY_ELEMENTDATA;
+ }
}
/**
! * Trims the capacity of this {@code ArrayList} instance to be the
* list's current size. An application can use this operation to minimize
! * the storage of an {@code ArrayList} instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
/**
! * Increases the capacity of this {@code ArrayList} instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
*** 262,297 ****
public int size() {
return size;
}
/**
! * Returns <tt>true</tt> if this list contains no elements.
*
! * @return <tt>true</tt> if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
/**
! * Returns <tt>true</tt> if this list contains the specified element.
! * More formally, returns <tt>true</tt> if and only if this list contains
! * at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
! * @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
! * More formally, returns the lowest index <tt>i</tt> such that
! * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
--- 270,305 ----
public int size() {
return size;
}
/**
! * Returns {@code true} if this list contains no elements.
*
! * @return {@code true} if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
/**
! * Returns {@code true} if this list contains the specified element.
! * More formally, returns {@code true} if and only if this list contains
! * at least one element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
! * @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
! * More formally, returns the lowest index {@code i} such that
! * {@code (o==null ? get(i)==null : o.equals(get(i)))},
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
*** 306,317 ****
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
! * More formally, returns the highest index <tt>i</tt> such that
! * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
--- 314,325 ----
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
! * More formally, returns the highest index {@code i} such that
! * {@code (o==null ? get(i)==null : o.equals(get(i)))},
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
*** 324,337 ****
}
return -1;
}
/**
! * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
*
! * @return a clone of this <tt>ArrayList</tt> instance
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
--- 332,345 ----
}
return -1;
}
/**
! * Returns a shallow copy of this {@code ArrayList} instance. (The
* elements themselves are not copied.)
*
! * @return a clone of this {@code ArrayList} instance
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
*** 370,380 ****
* this list.
*
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
! * <tt>null</tt>. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
--- 378,388 ----
* this list.
*
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
! * {@code null}. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
*** 435,445 ****
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
! * @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
--- 443,453 ----
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
! * @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
*** 490,507 ****
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
! * <tt>i</tt> such that
! * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
! * (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
! * @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
--- 498,515 ----
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
! * {@code i} such that
! * {@code (o==null ? get(i)==null : o.equals(get(i)))}
! * (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
! * @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
*** 553,563 ****
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
! * @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
--- 561,571 ----
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
! * @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
*** 576,586 ****
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
! * @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
--- 584,594 ----
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
! * @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
*** 724,739 ****
}
return modified;
}
/**
! * Save the state of the <tt>ArrayList</tt> instance to a stream (that
* is, serialize it).
*
! * @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
! * (each an <tt>Object</tt>) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
--- 732,747 ----
}
return modified;
}
/**
! * Save the state of the {@code ArrayList} instance to a stream (that
* is, serialize it).
*
! * @serialData The length of the array backing the {@code ArrayList}
* instance is emitted (int), followed by all of its elements
! * (each an {@code Object}) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
*** 751,761 ****
throw new ConcurrentModificationException();
}
}
/**
! * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
--- 759,769 ----
throw new ConcurrentModificationException();
}
}
/**
! * Reconstitute the {@code ArrayList} instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;