在Java中，List列表是我们经常需要使用的一种数据结构，List作为一个接口，定义了集合列表的基本行为，在java api的具体实现有ArrayList以及LinkedList，这两个实现也是经常需要用到的。本篇主要从源码看下ArrayList各个常用方法的具体实现
1.类继承实现关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到，ArrayList在类的结构上 继承了AbstractList<E>类，实现上实现了List接口，
RandomAccess接口提供随机快速访问的能力，起标记作用，随机访问时会根据有无实现此接口选择不同的算法；
Cloneable克隆接口，对象调用clone()方法时会在堆中新建一个与之前对象状态一样的对象，
Serializable序列化接口
2.类的一些重要的域
//默认的缺省容量 可以定义初始数组的长度
private static final int DEFAULT_CAPACITY = 10;
//默认的空数组 构造函数会用到
private static final Object[] EMPTY_ELEMENTDATA = {};
//也是一个空数组，构造函数以及扩容时会用到
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//被操作的数组 数据的存放数组
transient Object[] elementData;
//维护当前集合的长度大小（此处的size并不一定等于elementData数组的长度，在add和remove方法中可以看到）
//size大小总是小于或等于elementData.length
private int size;
从ArrayList的这些域中可以看到，ArrayList数据结构的底层是通过数组来实现的，数组是一种线性的数据结构，具有查找快，插入/删除慢的特点
3.构造方法
ArrayList一共有3个构造函数,接下来分别来看下3个构造函数的具体内容
ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
这个构造函数会传入一个数组初始化大小的参数，如果大于0的话，则新创建一个大小为initialCapacity的数组，并将引用赋值给elementData，如果等于0的话，则将域中的空数组EMPTY_ELEMENTDATA引用赋值给elementData。
ArrayList()
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
此构造函数是一般用到的空构造函数，里面内容很简单，将DEFAULTCAPACITY_EMPTY_ELEMENTDATA引用赋值给elementData。
ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
和ArrayList(int initialCapacity)的实现差不多，会判断一下大小和类型,类型一致且大小不为0时会使用Arrays.copyOf方法复制数组所以这时初始化不为空,
前面了解了ArrayList的类的结构以及3个构造函数，还有一些比较重要的域(变量),接下来就看下ArrayList在实际比较常用的几个方法的源码吧
4.添加
add(E e)
public boolean add(E e) {
//判断数组长度是否足够新增新的元素进去
ensureCapacityInternal(size + 1); // Increments modCount!!
//数组下标赋值 并将列表size的大小加1
elementData[size++] = e;
return true;
}
以下几个方法是判断当前数组长度是否足够添加新的元素进去
private void ensureCapacityInternal(int minCapacity) {
//如果是刚初始化的空数组，则取值缺省容量因子和参数的最大值表示新的数组长度
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//判断当前数组长度是否足够 新增后的长度
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//当前数组长度不足 则对当前的数组进行长度扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//一开始增量为原数组长度的一半
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:
//复制长度为newCapacity的数组赋值给elementData
elementData = Arrays.copyOf(elementData, newCapacity);
}
总结
新添加一个元素到ArrayList中时，会将表示新增后的列表大小size+1作为参数调用ensureCapacityInternal方法，在ensureCapacityInternal方法中会判断当前数组是否为空数组，取得列表需要到达的大小，调用ensureExplicitCapacity
判断当前的elementData数组的大小是否足够放下新的元素，如果不够的话，就要对elementData的数组大小进行动态扩容；
也就是说add方法先判断当前数组大小是否足够容下新增元素，不够的话就动态扩容当前数组，最后下标赋值,size自增1。
5.移除元素
remove(int index),remove(Object o)
首先来看下remove(int index)方法
public E remove(int index) {
//下面的方法检测下标是否越限
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
//判断是否移除的最后一项，如果不是，则将移除项前后拼接成新的数组
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将最后一项置为空，size自减1,数组长度并没有发生变化
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
接下来看下remove(Object o)方法
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;
}
先判断移除的对象是否为空，为空则从数组中遍历找到第一个为空的下标，通过fastRemove方法移除该下标的元素
不为空则遍历数组 找到第一个相等的下标，也是通过fastRemove移除
fastRemove方法的代码和remove(int index)中的一些代码块一样
6.获取元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
此方法较为简单，先判断下标是否越限，再通过数组下标取出元素强转返回
7.设置元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
先判断下标是否越限，将数组对应的下标引用重新赋值到新对象引用上
8.清除
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
遍历数组，将每一个下标的引用置为null，size大小重置为0，数组未发生变化
9.遍历
在集合中，一般遍历都是通过 Iterator 类来进行的，ArrayList也实现了该类 以及返回该 类的方法
public Iterator<E> iterator() {
return new Itr();
}
Itr是在ArrayList中定义的一个实现 Iterator接口的 一个内部类，如下
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
可以看到在 Itr 实现的next()方法，remove方法，最终c操作的还是ArrayList的elementData数组以及remove方法，比较简单
总结
以上从源码看到ArrayList的类结构，构造方法以及一些常规的方法，还有其他方法没有贴上来，大体上都差不多，像addAll,removeAll和all，remove方法比较类似，所以就不贴上来了。ArrayList是通过数组来实现的，从Add方法可以看到当数组长度不够时，会对当前数组进行扩容，增量大小一般情况下为之前长度的一半，间接促使数组拥有动态的变化，可以使我们无所顾虑的向列表增加新的元素，占用内存只增不少，从remove，clear方法也可以看到并不会对数组的长度发生变化，数组占用的空间还是那么大。
所以ArrayList的特点是占用内存不灵活，查找快，插入和删除慢
网友评论