* * The size, isEmpty, get, set, * iterator, and listIterator operations run in constant * time. The add operation runs in amortized constant time, * 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 LinkedList implementation.
* * Each ArrayList instance has a capacity. 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.
* * An application can increase the capacity of an ArrayList instance * before adding a large number of elements using the ensureCapacity * operation. This may reduce the amount of incremental reallocation.
* * Note that this implementation is not synchronized. If * multiple threads access an ArrayList instance concurrently, and at * least one of the threads modifies the list structurally, it must 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 synchronizing on some * object that naturally encapsulates the list. If no such object exists, the * list should be "wrapped" using the Collections.synchronizedList * method. This is best done at creation time, to prevent accidental * unsynchronized access to the list: *
* List list = Collections.synchronizedList(new ArrayList(...)); *
* * The iterators returned by this class's iterator and * listIterator methods are fail-fast: if list is structurally * modified at any time after the iterator is created, in any way except * through the iterator's own remove or add methods, the iterator will throw a * ConcurrentModificationException. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the * future.
* * Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw ConcurrentModificationException on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs.
*
* This class is a member of the
*
* Java Collections Framework.
*
* @author Josh Bloch
* @author Neal Gafter
* @version 1.50, 09/02/05
* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @see Collections#synchronizedList(List)
* @since 1.2
*/
public class ArrayList
*
* 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
* null. This is useful in determining the length of the list
* only 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
* same runtime type is allocated for this purpose.
* @return an array containing the elements of the list.
* @throws ArrayStoreException if the runtime type of a is not a supertype
* of the runtime type of every element in this list.
*/
public
*
* @param o element to be removed from this list, if present.
* @return true if the list contained the specified element.
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
}
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
// Let gc do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* Appends all of the elements in the specified Collection to the end of
* this list, in the order that they are returned by the
* specified Collection's Iterator. The behavior of this operation is
* undefined if the specified Collection is modified while the operation
* 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 the elements to be inserted into this list.
* @return true if this list changed as a result of the call.
* @throws NullPointerException if the specified collection is null.
*/
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* Inserts all of the elements in the specified Collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified Collection's iterator.
*
* @param index index at which to insert first element
* from the specified collection.
* @param c elements to be inserted into this list.
* @return true if this list changed as a result of the call.
* @throws IndexOutOfBoundsException if index out of range (index
* < 0 || index > size()).
* @throws NullPointerException if the specified Collection is null.
*/
public boolean addAll(int index, Collection c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* Removes from this List all of the elements whose index is between
* fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
* elements to the left (reduces their index).
* This call shortens the list by (toIndex - fromIndex) elements.
* (If toIndex==fromIndex, this operation has no effect.)
*
* @param fromIndex index of first element to be removed.
* @param toIndex index after last element to be removed.
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}
/**
* Check if the given index is in range. If not, throw an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
/**
* Save the state of the ArrayList instance to a stream (that
* is, serialize it).
*
* @serialData The length of the array backing the ArrayList
* instance is emitted (int), followed by all of its elements
* (each an Object) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
int expectedModCount = modCount;
// Write out element count, and any hidden stuff
s.defaultWriteObject();
// Write out array length
s.writeInt(elementData.length);
// Write out all elements in the proper order.
for (int i=0; itrue if the specified element is present;
* false otherwise.
*/
public boolean contains(Object elem) {
return indexOf(elem) >= 0;
}
/**
* Searches for the first occurence of the given argument, testing
* for equality using the equals method.
*
* @param elem an object.
* @return the index of the first occurrence of the argument in this
* list; returns -1 if the object is not found.
* @see Object#equals(Object)
*/
public int indexOf(Object elem) {
if (elem == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (elem.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in
* this list.
*
* @param elem the desired element.
* @return the index of the last occurrence of the specified object in
* this list; returns -1 if the object is not found.
*/
public int lastIndexOf(Object elem) {
if (elem == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (elem.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns a shallow copy of this ArrayList instance. (The
* elements themselves are not copied.)
*
* @return a clone of this ArrayList instance.
*/
public Object clone() {
try {
ArrayList