用java源代码学数据结构<三>:ArrayList 详解(一)

2014-11-24 08:51:45 · 作者: · 浏览: 17
查看java文档可以知道,抽象类AbstractList有两个实现子类:Vector和ArrayList。二者的内部结构、基本方法大致相同.只不过Vector是线程安全的,ArrayList是不安全的。ArrayList相比于一般的Array,就是多了一个变长的功能,但相应的时间效率有所下降。
由于ArrayLIst和Vector很想,大部分代码基本一致,就不在提供详细的注释,可以对比参考Vector类的分析(http://blog.csdn.net/wanghao109/article/details/13162419)。
[java]
package java.util;
/*
1.ArrayList实现了List接口,允许包含null
2.ArrayList和Vector基本一致,除了ArrayList是非同步的(unsynchronized)
要想使ArrayList多线程同步,可以封装ArrayList,如
List list = Collections.synchronizedList(new ArrayList(...));
*/
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
{
//序列号
private static final long serialVersionUID = 8683452581122892189L;
//默认的capacity为10,和vector一样大小
private static final int DEFAULT_CAPACITY = 10;
//ArrayList类共享的数组对象,
private static final Object[] EMPTY_ELEMENTDATA = {};
/*
1.ArrayList存储元素的数组,Arraylist的capacity等于数组的length
2.对于所有一开始为空的ArrayList(就是指elementData == EMPTY_ELEMENTDATA),
当第一个元素被加入时,ArrayList扩充为DEFAULT_CAPACITY
*/
private transient Object[] elementData;
//包含元素的数目
private int size;
//初始化大小为initialCapacity的ArrayList
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
//无参构造函数
public ArrayList() {
super();
//注意这里:默认使用静态数组EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
}
//和vector类似,使用集合c初始化ArrayList
public ArrayList(Collection< extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//函数使用说明参见Vector分析
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
/*
如果ArrayList当前实际元素数目小于capacity,将vector缩小。
常用于减少ArrayList的存储空间
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
/*
1.增大ArrayList的大小,确保能存放至少minCapacity个元素
*/
public void ensureCapacity(int minCapacity) {
/*
如果elementData等于EMPTY_ELEMENTDATA,表示ArrayList对象只初始化,
还未包含任何元素,那么将ArrayList扩展为DEFAULT_CAPACITY
*/
int minExpand = (elementData != EMPTY_ELEMENTDATA)
// any size if real element table
0
// larger than default for empty table. It's already supposed to be
// at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//内部函数,功能和vector类相似
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplic