JDK源码解析 java.util.ArrayList类 jdk1.6
?
?
/*
?* @(#)ArrayList.java 1.56 06/04/21
?*
?* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
?* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
?*/
?
package java.util;
?
/**
List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）
?
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行，也就是说，添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行（大体上讲）。与用于 LinkedList 实现的常数因子相比，此实现的常数因子较低。
?
每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。
?
在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
?
注意，此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须 保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：
?
? ? ? ?List list = Collections.synchronizedList(new ArrayList(...)); 此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
?
注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。
?
此类是 Java Collections Framework 的成员。?
?
?
?
从以下版本开始：?
1.2?
另请参见：
Collection, List, LinkedList, Vector, Collections.synchronizedList(List), 序列化表格
?*/
?
public class ArrayList<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8683452581122892189L;
?
/**
* 用来存放数据的Object[] ?由此可知ArrayList是用过数组来存放数据的?
*/
private transient Object[] elementData; //该变量是transient的Object的数组，用来构造ArrayList。实际上ArrayList是用数组实现的。
?
/**
* ArrayList所具有的元素的个数
* 目前Object[] 存放的个数 ?！= Object.length()?
*?
* @serial
*/
private int size; //ArrayList数组的大小。
?
/**
构造一个具有指定初始容量的空列表。?
?
参数：
initialCapacity - 列表的初始容量?
抛出：?
IllegalArgumentException - 如果指定的初始容量为负
?
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0) //如果传入的初始容量小于0，则抛异常
throw new IllegalArgumentException("Illegal Capacity: "
+ initialCapacity);
this.elementData = new Object[initialCapacity]; //初始化大小为intialCapacity的Object类型的数组
}
?
/**
* 构造一个初始容量为 10 的空列表。?
*/
public ArrayList() { //可以看到，如果调用默认的构造方法，则jdk为我们提供的ArrayList的大小为10。
this(10);
}
?
/**
构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。?
?
参数：
c - 其元素将放置在此列表中的 collection?
抛出：?
NullPointerException - 如果指定的 collection 为 null
?
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //直接调用Collection的toArray将传入的Collection变成整个数组赋值给数组变量。
size = elementData.length; //ArrayList的大小即为传入的Collection的长度
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class); //使用Arrays.copyof来复制元素
}
?
/**
将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量。?
*/
public void trimToSize() { //将ArrayList调整为列表的当前大小，减少内存开销
/** modCount的含义：
已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小，或者打乱列表，从而使正在进行的迭代产生错误的结果。?
此字段由 iterator 和 listIterator 方法返回的迭代器和列表迭代器实现使用。如果意外更改了此字段中的值，则迭代器（或列表迭代器）将抛出 ConcurrentModificationException 来响应 next、remove、previous、set 或 add 操作。在迭代期间面临并发修改时，它提供了快速失败 行为，而不是非确定性行为。?
子类是否使用此字段是可选的。如果子类希望提供快速失败迭代器（和列表迭代器），则它只需在其 add(int, E) 和 remove(int) 方法（以及它所重写的、导致列表结构上修改的任何其他方法）中增加此字段。对 add(int, E) 或 remove(int) 的单个调用向此字段添加的数量不得超过 1，否则迭代器（和列表迭代器）将抛出虚假的 ConcurrentModificationExceptions。如果某个实现不希望提供快速失败迭代器，则可以忽略此字段。?
*/
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size); //ArrayList中所有元素的变化经常使用Arrays.copyof来操作
}
}
?
/**
如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。?
?
参数：
minCapacity - 所需的最小容量
?
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length; //原来的大小
if (minCapacity > oldCapacity) { //如果传入的minCapacity比原来的大小要大，那么就可以扩容
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3) / 2 + 1; //扩容默认的事原来大小的1.5倍。
if (newCapacity < minCapacity) //如果扩容后(即容量变为1.5倍后)还是小于传入的minCapacity的大小，那么就不是1.5倍了，而是直接用传入的大小。
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //仍然用Arrays.copyof进行对原ArrayList的操作，扩容。
}
}
?
/**
返回此列表中的元素数。?
?
指定者：
接口 Collection<E> 中的 size
指定者：
接口 List<E> 中的 size
指定者：
类 AbstractCollection<E> 中的 size
返回：
此列表中的元素数
?
*/
public int size() {
return size; //直接返回size
}
?
/**
如果此列表中没有元素，则返回 true?
?
指定者：
接口 Collection<E> 中的 isEmpty
指定者：
接口 List<E> 中的 isEmpty
覆盖：
类 AbstractCollection<E> 中的 isEmpty
返回：
如果此列表中没有元素，则返回 true
?
*/
public boolean isEmpty() {
return size == 0; //判断是否为空，就是size是否为0。
}
?
/**
如果此列表中包含指定的元素，则返回 true。更确切地讲，当且仅当此列表包含至少一个满足 (o==null ? e==null : o.equals(e)) 的元素 e 时，则返回 true。?
?
指定者：
接口 Collection<E> 中的 contains
指定者：
接口 List<E> 中的 contains
覆盖：
类 AbstractCollection<E> 中的 contains
参数：
o - 测试此列表中是否存在的元素?
返回：
如果此列表包含特定的元素，则返回 true
?
*/
public boolean contains(Object o) {
return indexOf(o) >= 0; //判断是否存在某个特定的数据，直接调用indexOf来寻找该数据的位置，如果位置大于等于0，则包含该数据。
}
?
/**
返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。更确切地讲，返回满足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引 i ，如果不存在此类索引，则返回 -1。?
?
指定者：
接口 List<E> 中的 indexOf
覆盖：
类 AbstractList<E> 中的 indexOf
参数：
o - 要搜索的元素?
返回：
此列表中第一次出现的指定元素的索引，如果列表不包含该元素，则返回 -1
*/
public int indexOf(Object o) { //查找某元素首次出现的位置，是从第一个元素开始找的。遍历整个数组来查找。
if (o == null) {
for (int i = 0; i < size; i++) //如果传入的元素为null，则用==来比较。
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++) //如果传入的元素不为null，则用equals来比较。
if (o.equals(elementData[i]))
return i;
}
return -1; //或如果此列表不包含索引，则返回 -1?
}
?
/**
返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。更确切地讲，返回满足 (o==null ? get(i)==null : o.equals(get(i))) 的最高索引 i，如果不存在此类索引，则返回 -1。?
?
指定者：
接口 List<E> 中的 lastIndexOf
覆盖：
类 AbstractList<E> 中的 lastIndexOf
参数：
o - 要搜索的元素?
返回：
列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1
?
*/
public int lastIndexOf(Object o) { //这里是通过反向来查找的。即从最后一个元素开始往前找，找到该元素第一次出现的位置。
if (o == 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 (o.equals(elementData[i]))
return i;
}
return -1; //或如果此列表不包含索引，则返回 -1?
}
?
/**
返回此 ArrayList 实例的浅表副本。（不复制这些元素本身。）?
?
覆盖：
类 Object 中的 clone
返回：
此 ArrayList 实例的一个副本
另请参见：
Cloneable
?
*/
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
?
/**
按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。?
由于此列表不维护对返回数组的任何引用，，因而它将是“安全的”。（换句话说，此方法必须分配一个新的数组）。因此，调用者可以自由地修改返回的数组。?
?
此方法担当基于数组的 API 和基于 collection 的 API 之间的桥梁。?
?
?
指定者：
接口 Collection<E> 中的 toArray
指定者：
接口 List<E> 中的 toArray
覆盖：
类 AbstractCollection<E> 中的 toArray
返回：
包含此列表中所有元素的数组（按适当顺序）
另请参见：
Arrays.asList(Object[])
?
* ? ? ? ? sequence
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size); //toArray就是直接调用Arrays.copyof方法来实现的。
}
?
/**
按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。如果指定的数组能容纳列表，则将该列表返回此处。否则，将分配一个具有指定数组的运行时类型和此列表大小的新数组。?
如果指定的数组能容纳队列，并有剩余的空间（即数组的元素比队列多），那么会将数组中紧接 collection 尾部的元素设置为 null。（仅 在调用者知道列表中不包含任何 null 元素时才能用此方法确定列表长度）。?
?
?
指定者：
接口 Collection<E> 中的 toArray
指定者：
接口 List<E> 中的 toArray
覆盖：
类 AbstractCollection<E> 中的 toArray
参数：
a - 要在其中存储列表元素的数组（如果它足够大）；否则，为此分配一个具有相同运行时类型的新数组。?
返回：
包含列表元素的数组?
抛出：?
ArrayStoreException - 如果指定数组的运行时类型不是此列表每个元素的运行时类型的超类型?
NullPointerException - 如果指定数组为 null
?
*/
public <T> T[] toArray(T[] a) {
if (a.length < size) //如果传入的数组a的长度小于该构造的ArrayList的大小，那么直接调用Arrays.copyof方法来操作。
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size); //如果传入的数组a的长度大于该构造的ArrayList的大小，就调用System.arraycopy来操作。
// if (a.length > size) //并且将传入的数组超出构造的ArrayList的那些元素置为null。即只取前面部分。
a[size] = null;
return a;
}
?
// Positional Access Operations
?
/**
返回此列表中指定位置上的元素。?
?
指定者：
接口 List<E> 中的 get
指定者：
类 AbstractList<E> 中的 get
参数：
index - 要返回元素的索引?
返回：
此列表中指定位置上的元素?
抛出：?
IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index >= size())
?
*/
public E get(int index) {
RangeCheck(index); //先检查传入的索引值是否超出范围。如果超出范围，则直接抛异常。
?
return (E) elementData[index]; //否则返回数组的第index位置的元素。
}
?
/**
用指定的元素替代此列表中指定位置上的元素。?
?
指定者：
接口 List<E> 中的 set
覆盖：
类 AbstractList<E> 中的 set
参数：
index - 要替代的元素的索引
element - 存储在指定位置上的元素?
返回：
以前位于该指定位置上的元素?
抛出：?
IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index >= size())
?
*/
public E set(int index, E element) {
RangeCheck(index); //先检查索引范围。
?
E oldValue = (E) elementData[index]; //取得原来索引位置的元素，将他替换为传入的元素值，并且返回。
elementData[index] = element;
return oldValue;
}
?
/**
将指定的元素添加到此列表的尾部。?
?
指定者：
接口 Collection<E> 中的 add
指定者：
接口 List<E> 中的 add
覆盖：
类 AbstractList<E> 中的 add
参数：
e - 要添加到此列表中的元素?
返回：
true（按照 Collection.add(E) 的指定）
?
*/
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!! 如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。?
elementData[size++] = e; //将下一个元素指向传入的元素值。
return true;
}
?
/**
将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素（如果有）以及所有后续元素（将其索引加 1）。?
?
指定者：
接口 List<E> 中的 add
覆盖：
类 AbstractList<E> 中的 add
参数：
index - 指定元素所插入位置的索引
element - 要插入的元素?
抛出：?
IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index > size())
?
*/
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
?
ensureCapacity(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size ? //这里如果在中间加入某个元素，那么涉及到其后面元素的移动，所以使用System.arraycopy来完成。
- index);
elementData[index] = element;
size++;
}
?
/**
移除此列表中指定位置上的元素。向左移动所有后续元素（将其索引减 1）。?
?
指定者：
接口 List<E> 中的 remove
覆盖：
类 AbstractList<E> 中的 remove
参数：
index - 要移除的元素的索引?
返回：
从列表中移除的元素?
抛出：?
IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index >= size())
?
*/
public E remove(int index) { //根据索引来移除元素。
RangeCheck(index); //检查索引范围。
?
modCount++;
E oldValue = (E) elementData[index]; //取出传入索引值的元素。
?
int numMoved = size - index - 1; //要移动的元素的个数。
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, //还是调用System.arraycopy来移动元素。
numMoved);
elementData[--size] = null; // Let gc do its work 然后将原来索引的那个元素置为null，以便垃圾回收。
?
return oldValue; //返回被移除的元素。
}
?
/**
移除此列表中首次出现的指定元素（如果存在）。如果列表不包含此元素，则列表不做改动。更确切地讲，移除满足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引的元素（如果存在此类元素）。如果列表中包含指定的元素，则返回 true（或者等同于这种情况：如果列表由于调用而发生更改，则返回 true）。
?
?
指定者：
接口 Collection<E> 中的 remove
指定者：
接口 List<E> 中的 remove
覆盖：
类 AbstractCollection<E> 中的 remove
参数：
o - 要从此列表中移除的元素（如果存在）?
返回：
如果此列表包含指定的元素，则返回 true
?
*/
public boolean remove(Object o) { //根据传入的元素值来移除元素，这里就需要遍历每个元素，去跟传入的元素进行比较了。同时只移除第一次查找到的元素。
if (o == null) {
for (int index = 0; index < size; index++) //
if (elementData[index] == null) {
fastRemove(index); //这里内部还是使用System.arraycopy来移动元素的。
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
}
?
/**
移除此列表中的所有元素。此调用返回后，列表将为空。?
?
指定者：
接口 Collection<E> 中的 clear
指定者：
接口 List<E> 中的 clear
覆盖：
类 AbstractList<E> 中的 clear
?
*/
public void clear() { //遍历元素，将所有元素置为null，并把size改为0。
modCount++;
?
// Let gc do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
?
size = 0;
}
?
/**
按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。如果正在进行此操作时修改指定的 collection ，那么此操作的行为是不确定的。（这意味着如果指定的 collection 是此列表且此列表是非空的，那么此调用的行为是不确定的）。?
?
指定者：
接口 Collection<E> 中的 addAll
指定者：
接口 List<E> 中的 addAll
覆盖：
类 AbstractCollection<E> 中的 addAll
参数：
c - 包含要添加到此列表中的元素的 collection?
返回：
如果此列表由于调用而发生更改，则返回 true?
抛出：?
NullPointerException - 如果指定的 collection 为 null
另请参见：
AbstractCollection.add(Object)
?
*/
public boolean addAll(Collection<? extends E> c) { //增加一个集合到ArrayList中
Object[] a = c.toArray(); //首先是将集合变为数组。
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount 进行扩容，容量为原来ArrayList的大小加上传入的集合的大小。
System.arraycopy(a, 0, elementData, size, numNew); //移动元素，将两数组合并为一个数组。
size += numNew; //修正size的值。
return numNew != 0; ?//如果传入的Collection中没有元素需要加到ArrayList中，则返回false；否则返回true。
}
?
/**
从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。向右移动当前位于该位置的元素（如果有）以及所有后续元素（增加其索引）。新元素将按照指定 collection 的迭代器所返回的元素顺序出现在列表中。?
?
指定者：
接口 List<E> 中的 addAll
覆盖：
类 AbstractList<E> 中的 addAll
参数：
index - 插入指定 collection 中的首个元素的位置索引
c - 包含要添加到此列表中元素的 collection?
返回：
如果此列表由于调用而发生更改，则返回 true?
抛出：?
IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index > size())?
NullPointerException - 如果指定的 collection 为 null
?
*/
public boolean addAll(int index, Collection<? extends E> 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;
}
?
/**
移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。向左移动所有后续元素（减小其索引）。此调用将列表缩短了 (toIndex - fromIndex) 个元素。（如果 toIndex==fromIndex，则此操作无效。）?
?
覆盖：
类 AbstractList<E> 中的 removeRange
参数：
fromIndex - 要移除的首个元素的索引
toIndex - 最后一个要移除的元素后面那个元素的索引?
抛出：?
IndexOutOfBoundsException - 如果 fromIndex 或 toIndex 超出范围 (fromIndex < 0 || fromIndex >= size() || toIndex > size() || toIndex < fromIndex)
?
*/
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;
}
?
/**
* Checks if the given index is in range. If not, throws 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) { //范围校验，即简单的校验传入的值是否大于ArrayList的大小。
if (index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
}
?
/**
* 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;
s.defaultWriteObject();
?
// Write out array length
s.writeInt(elementData.length);
?
// Write out all elements in the proper order.
for (int i = 0; i < size; i++)
s.writeObject(elementData[i]);
?
if (modCount != expectedModCount) {
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 {
// Read in size, and any hidden stuff
s.defaultReadObject();
?
// Read in array length and allocate array
int arrayLength = s.readInt();
Object[] a = elementData = new Object[arrayLength];
?
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
a[i] = s.readObject();
}
}
