Java集合类源码之List——ArrayList
2017-03-04 本文已影响308人
丁木木木木木
主要内容：
- ArrayList继承关系、关键属性、构造函数
- 插入、删除、修改及查找元素
- 与LinkedList、Vector比较
ArrayList概述
大致介绍下ArrayList。
- 基于动态数组的实现，容量可自动增长，初始容量为10。
- 获取元素迅速，但插入、删除操作耗时。
- 非线程安全，创建线程安全的ArrayList可以使用
Collections.synchronizedList或者并发包下的CopyOnWriteArrayList类。
ArrayList map = Collections.synchronizedList(new ArrayList());
源码分析
继承关系
ArrayList继承关系.png
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 继承AbstractList抽象类，实现List接口，是数组队列，提供了相关的插入、删除、查询等操作
- 实现RandomAccess接口，支持快速随机访问
- 实现java.io.Serialization接口，支持序列化
- 实现Cloneable接口，支持对象克隆，浅复制
关键属性
//初始容量为10
private static final int DEFAULT_CAPACITY = 10;
//空数组，无参构造函数时默认为空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//保存ArrayList元素的数组。当第一个元素插入时，任何空的ArrayList会被扩大到初始容量
private transient Object[] elementData;
//实际存储的元素个数
private int size;
构造函数
//使用指定容量大小创建ArrayList
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
//构造一个空ArrayList，在第一次插入数据时初始化默认容量大小10的数组
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
//构造指定collection的ArrayList，按照集合的迭代顺序排序
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);
}
插入
插入元素
插入单个元素的方法主要有boolean add(E e)和void add(int index, E element)。
-
boolean add(E e)：将指定元素插入到ArrayList尾部。插入元素之前调用ensureCapacityInternal(int minCapacity)判断数组是否需要扩容。扩容时需要复制当前数组的元素，容量扩大到原来的1.5倍，代价较高。因此一般初始化ArrayList的时候先考虑下大致的长度，使用指定容量大小的构造函数初始化。
//指定元素插入到ArrayList尾部
public boolean add(E e) {
ensureCapacityInternal(size + 1); //判断是否扩容，增加modCount
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//modCount增加，实现fail-fast机制
if (minCapacity - elementData.length > 0)//超过数组可容纳的数量
grow(minCapacity);//扩容
}
private void grow(int minCapacity) {//扩容
int oldCapacity = elementData.length;//当前数组的长度
int newCapacity = oldCapacity + (oldCapacity >> 1);//扩大1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
-
add(int index, E element)：将指定元素插入到ArrayList指定位置处。
//将指定元素插入到ArrayList指定的位置处
public void add(int index, E element) {
rangeCheckForAdd(index);//索引范围判断
ensureCapacityInternal(size + 1); //判断是否扩容，增加modCount
/**
* 将index位置处及其右边所有元素向后移动一位。
* 将elementData中index位置开始，长度为size-index的元素
* 复制到位置为index+1的elementData
**/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
插入集合元素
插入集合的方法主要有boolean addAll(Collection<? extends E> c)和boolean addAll(int index, Collection<? extends E> c)。
//按照集合迭代器的顺序，将集合的元素插入到链表尾部
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);//判断是否扩容
System.arraycopy(a, 0, elementData, size, numNew);//复制
size += numNew;
return numNew != 0;
}
//从指定位置开始，插入集合的元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); //判断扩容
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;
}
删除
删除元素方法主要有E remove(int index)和remove(Object o)。
//删除索引位置上的元素
public E remove(int index) {
rangeCheck(index);//数组越界检查
modCount++;//fail-fast机制
E oldValue = elementData(index);
int numMoved = size - index - 1;//要移动的元素个数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//移除位置之后的元素往前移动一位
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//移除首次出现的指定元素
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;
}
//与public E remove(int index)类似
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; // clear to let GC do its work
}
修改
将数组中指定位置上的元素替换掉，返回以前位于该位置上的元素。
public E set(int index, E element) {
rangeCheck(index);//判断index范围
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
查找
返回ArrayList指定位置上的元素。
public E get(int index) {
rangeCheck(index);//判断index的范围
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
与LinkedList、Vector比较
LinkedList比较
- 实现：ArrayList基于数组实现，LinkedList基于链表实现。
- 查询：ArrayList速度更快，因为是随机访问；而LinkedList要遍历链表元素查询。
- 插入、删除：ArrayList要移动数据，缓慢；而LinkedList快速。
Vector比较
- 扩容：ArrayList扩容时1.5倍原容量，Vector为1倍。
- 线程安全：ArrayList非线程安全；Vector线程安全，需要更大的系统开销。
