概述
在分析ArrayList源码之前，先看一下ArrayList在数据结构中的位置，常见的数据结构按照逻辑结构跟存储结构如下：
数据结构分类
先看看源码的注释：
- 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.) - 实现了List接口的可调整大小的数组，也就是经常说的动态数组，实现了所有的可选的列表的操作，并且能够插入任何元素，包括空值。除了实现了List接口之外，对于内部存储的数组，也提供了相应的改变数组大小的方法。(这个类除了不是线程安全的，几乎可以相当于Vector)
很明显，ArrayList是一个线性结构，底层通过数组实现，并且是动态数组。
下面看一下ArrayList的继承关系，这个是通过IDEA生成的继承关系图，很清晰，终于不用自己画了。
ArrayList继承关系
通过图可以看到ArrayList继承自AbstractList，并且实现了List<E>, RandomAccess, Cloneable, Serializable接口，而AbstractList实现了Collection接口，则ArrayList具有Collection的所有方法，而且能够进行clone,序列化，下面开始开始对ArrayList的源码进行分析，吼吼。
正文
成员变量
//序列化ID
private static final long serialVersionUID = 8683452581122892189L;
//默认的初始化数组的容量为10
private static final int DEFAULT_CAPACITY = 10;
//共享的空数组，也就是调用空的构造方法的时候会进行默认用这个数组进行初始化
private static final Object[] EMPTY_ELEMENTDATA = {};
//数组缓冲区，也就是从来存放List元素的数组。ArrayList的容量就是缓冲区数组的长度。对于一个空数组，在添加第一个元素的时候，List的容量会被设置成默认的DEFAULT_CAPACITY，也就是10，
transient Object[] elementData;
//elementData的长度
private int size;
构造方法
构造一个空数组，采用默认容量(Constructs an empty list with an initial capacity of ten)
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
前面有提到过，当初始化数组为空的时候，在add的时候会进行判断，如果数组的长度为0，数组的长度就是默认的数组长度
构造一个空的数组，自定义数组容量(Constructs an empty list with the specified initial capacity)
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
这个跟上面的区别在于创建了一个新的数组，数组的最大长度就是传入的初始化容量，数组的长度为0。
传入一个集合进行初始化(Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.)
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);
}
数组的长度就是传入的集合的长度，将集合传入缓冲数组
Add方法
在末尾添加一个元素(Appends the specified element to the end of this list.)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
在指定位置添加一个元素(Inserts the specified element at the specified position in this list.)
public void add(int index, E element) {
//判断index是否合乎规范
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//拷贝数组
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//进行赋值
elementData[index] = element;
//将数组的长度自增
size++;
}
在末尾添加一个集合(Appends all of the elements in the specified collection to the end of this list)
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(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)
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(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;
}
Add操作有如上几个重载方法，仔细观察一下，大同小异，我们选择第二个重载方法，也就是在指定位置添加一个元素：
- 判断index是否合理
- 检查是否需要扩容
- 拷贝数组
- 进行赋值
- 将数组的长度自增
这里面比较有营养的就是第二步了，下面重点分析第二步：
调用ensureCapacityInternal(size++1)
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
传入了此时数组需要的长度，只要数组为初始化的时候没有指定容量，就会在minCapacity(size+1)跟DEFAULT_CAPACITY中间取一个最大值，之所以这样，是因为如果将数组的容量设置成太小，会导致数组频繁的扩容，影响性能。
调用ensureExplicitCapacity(minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
//这个变量来自于ArrayList的父类AbstractList，主要用来记录集合的操作次数
modCount++;
// overflow-conscious code
//如果此时需要的数组长度大于数组本身的长度，则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
执行扩容操作grow(minCapacity)
private void grow(int minCapacity) {
// overflow-conscious code
//数组当前的容量
int oldCapacity = elementData.length;
//扩容后新数组的容量,增大了0.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的数组比当前的所需要的数组长度要小，则区当前需要的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//将扩容后的数组长度跟定义的数组最大长度进行比较，防止越界
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//进行扩容操作
elementData = Arrays.copyOf(elementData, newCapacity);
}
Remove方法
remove指定位置元素（Removes the element at the specified position in this list）
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) 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;
}
移除某个具体元素(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)
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 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
}
仔细观察一下上面两个重载方法，其实是差不多的，删除元素分两步走：
- 找到这个元素
- 执行删除操作
比较简单，不过多描述
Set方法
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
直接替换掉对应的元素
查找索引操作
寻找元素第一次出现的下标(Returns the index of the first occurrence of the specified element)
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
寻找最后出现的某个元素的索引(Returns the index of the last occurrence of the specified element in this list)
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.
Get方法
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
总结
ArrayList的特点
- 有序的，元素可以重复
- 查询快，增删慢
- 当容量不够的时候，会进行扩容至当前size的1.5倍
- 非线程安全
关于ArrayList的源码就分析到这里，因为底层的实现是数组，所以不管是扩容还是其它的增删改查操作都是对数组进行操作，所以只要对数组足够了解，基本上还是挺好理解的。
网友评论