数组：一旦初始化长度就不可以发生变化。
增删慢：每次增删元素，都需要改变数组的长度，且移动元素的位置。查询快：数组在内存中是一块连续的空间，可根据地址+索引的方式快速获取对应位置上的元素。
ArrayList：List接口的大小可变数组的实现。
ArrayList底层的数据结构就是数组，数组元素类型为Object类型。对ArrayList类的实例的所有的操作，在底层都是基于数组的。
二、 ArrayList继承关系 2.1 Serializable标记性接口 2.1.1 Serializable介绍类的序列化由实现java.io.Serializable接口的类启用。 不实现此接口的类将不会使任何状态序列化或反序列化。 可序列化类的所有子类型都是可序列化的。 序列化接口没有方法或字段，仅用于标识可串行化的语义。
序列化：将对象的数据写入到文件（写对象）。反序列化：将文件中对象的数据读取出来（都对象）。 2.1.2 Serializable源码
public interface Serializable {
// 该接口仅用于标识，没有方法和字段
}
2.2 Cloneable标记性接口
2.2.1 Cloneable介绍
一个类实现Cloneable接口，以指示Object.clone()方法，该方法对于该类的实例进行现场复制是合法的。
在不实现Cloneable接口的实例上调用对象的克隆方法导致抛出异常CloneNotSupportedException 。
2.2.2 Cloneable源码public interface Cloneable {
// 该接口没有字段和方法名
}
2.2.3 克隆的前提条件
被克隆对象所在的类必须实现Cloneable接口。必须重写clone()方法。 2.2.4 ArrayList中的clone()方法源码
public Object clone() {
try {
// 调用Object中的clone()
ArrayList v = (ArrayList) super.clone();
// 将ArrayList对象中的元素，拷贝成长度相同的Object[] elementData数组。
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(e);
}
}
2.2.5 浅克隆与深克隆
浅克隆
直接调用父类Object类的clone()方法。
局限性：基本数据类型可以达到完全复制。但是引用数据类型不可以，它们会相互影响。
原因：引用数据类型仅仅克隆了一份引用（即地址），当它的值发生改变时，被克隆对象的属性值也会发生改变。
深克隆
不能直接调用父类Object类的clone()方法，需要程序员手动重写。既要克隆该对象，也要更深一步依次克隆对象的所有引用数据类型的属性，再将属性重写赋值。
深克隆出对象中的所用数据，与原来被克隆对象中的数据不会相互影响，彻底分离。
@Override
public Object clone() throws CloneNotSupportedException {
// 浅克隆
//return super.clone();
// 深克隆
Student stu = (Student) super.clone(); // 将对象克隆
Skill skill = (Skill)this.skill.clone(); // 将对象的引用数据类型的属性克隆
stu.setSkill(skill); // 将属性重新赋值
return stu;
}
2.3 RandomAccess标记性接口
2.3.1 RandomAccess介绍
List实现使用的标记界面，表明它们支持快速（通常为恒定时间）随机访问。 此接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能。
如果一个List实现了这个接口，则随机访问比顺序访问更快。
随机访问列表
for (int i=0, n=list.size(); i < n; i++) list.get(i);
顺序访问列表
for (Iterator i=list.iterator(); i.hasNext(); ) i.next();2.3.2 RandomAccess源码
public interface RandomAccess {
// 该接口没有字段和方法名
}
2.4 AbstractList抽象类
该类提供了List接口的骨架实现。
三、ArrayList源码分析 3.1 类的属性// 序列化ID
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始化容量为10
private static final int DEFAULT_CAPACITY = 10;
// 容量大小为0的空实例的共享数组/
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认容量大小的空实例的共享数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
// ArrayList的实际大小（数组包含的元素个数/实际数据的数量）默认为0
private int size;
3.2 构造器
3.2.1 ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 指定容量
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 容量大小为0
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 指定容量不合法，抛出异常
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
3.2.2 ArrayList()
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3.2.3 ArrayList(Collection c)
public ArrayList(Collection c) {
Object[] a = c.toArray(); // 将集合c装成数组
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
// 数组的创建和拷贝
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// 集合c为空
elementData = EMPTY_ELEMENTDATA;
}
}
3.3 主要方法
3.3.1 get(int index)
public E get(int index) {
// 检查索引范围
rangeCheck(index);
// 返回指定位置元素
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
3.3.2 set(int index, E element)
public E set(int index, E element) {
rangeCheck(index); // 越界检查
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
3.3.3 grow(int minCapacity)
private void grow(int minCapacity) {
// overflow-conscious code
// 获取当前数组的容量
int oldCapacity = elementData.length;
// 扩容。新容量 = 旧容量 + 旧容量/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 扩容后的新容量 小于 所需最小容量
if (newCapacity - minCapacity < 0)
// 将容量再次扩容成所需最小容量
newCapacity = minCapacity;
// 扩容后的新容量 大于 最大容量临界值
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 再次扩容
newCapacity = hugeCapacity(minCapacity);
// 拷贝数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
3.3.4 add(E e)
public boolean add(E e) {
// 确保容量，容量不够需扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 确保容量。容量不够就扩容。
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 操作次数+1
// 所需最小容量 大于 数组长度
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 扩容
}
3.3.5 add(int index, E element)
public void add(int index, E element) {
// 越界检查
rangeCheckForAdd(index);
// 确保容量
ensureCapacityInternal(size + 1); // Increments modCount!!
// 拷贝数组，空出index位置，后面元素后移一位
// arraycopy(源数组，源数组中元素移动的起始位置，目标数组，目标数据中的起始位置，要复制的数组元素的数量)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
3.3.6 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;
}
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
}
