List集合接口
设置了一些List的公共方法，继承了Collection
RandomAccess标记接口
RandomAccess: 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。也就是说，实现了这个接口的集合是支持快速随机访问策略的。
Cloneable标记接口
Cloneable:是一个标记接口,按照约定，实现Cloneable的类应当重写Object.clone()方法,但是此接口不包含clone方法，在不实现Cloneable接口的对象上调用Object的clone方法会抛CloneNotSupportedException异常。
Serializable序列化接口
说明此类可以序列化，网络传输需要序列化，只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，这个类的所有属性和方法都会自动序列化
属性变量： //默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小的空实例的共享空数组实例。我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList 的大小（它实际包含的元素数）。
private int size;
构造函数：
//有参构造
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果设置的初始容量>0(正常)
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果参数等于0，设置成默认的共享空数组实例
this.elementData = EMPTY_ELEMENTDATA;
} else {
//负数抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//c.toArray 可能有时候（错误地）或者返回的不是 Object[]类型，
//例如List strList= Arrays.asList("abc");返回的结果是String[]
if (elementData.getClass() != Object[].class)
//如果返回的不是Object类型的，用本地的native方法Arrays.copyOf再拷贝一次
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 赋值为默认的空数组.
this.elementData = EMPTY_ELEMENTDATA;
}
}
方法函数：
private void grow(int minCapacity)
数组扩容机制，核心方法
private void grow(int minCapacity) {
// overflow-conscious code
//保存原数组长度
int oldCapacity = elementData.length;
//扩容：位运算将原来的数组长度扩大到1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新容量小于最小容量，将最小容量赋值给新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于（Integer类型的最大值-8）,则被赋值为integer的最大值(0x7fffffff)
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity 通常接近 size，所以这是一个胜利
//实现数组扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//最小容量为负数
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//最小容量大于(integer的最大值-8)则返回integer的最大值，否则返回integer的最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public void trimToSize()
将此ArrayList实例的容量修剪为列表的当前大小。
public void trimToSize() {
modCount++;
//如果list中的实际存在的元素数量小于数组的容量，例如{1，2，3，4,5,6,null,null,null,null}
if (size < elementData.length) {
//如果elementData等于0，则将空数组实例传给他，如果不等于0再拷贝一次，将实例的容量修剪为列表的当前大小
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
public void ensureCapacity(int minCapacity)
//方法用于设置具有指定容量大小的动态数组。
public void ensureCapacity(int minCapacity) {
int minExpand =
//数组不为空
(elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 任何大小，如果不是默认空元素表
? 0
// 大于默认空表的默认值。设置为默认大小10
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
//检查是否需要扩容
ensureExplicitCapacity(minCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity)
计算容量的方法
// 计算容量的方法calculateCapacity(elementData,minCapacity)方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果elementData的数组为空数组：
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//返回默认空数组的长度和传入参数两个中较大的值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//否则直接返回最小容量
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity)
//在add方法中首先调用了ensureCapacityInternal(size+1)的方法，用来确定添加元素成功需要的最小集合容量minCapacity
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(
//先计算容量
calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity)
检查是否需要扩容
//方法来确保集合容器为了将元素添加成功，是否需要扩容，将计数器加1，
// 然后判断minCapacity和当前数组的长度大小，当minCapacity的值比当前数组的长度大时，则说明需要扩容。
private void ensureExplicitCapacity(int minCapacity) {
//记录改动数组次数
modCount++;
// overflow-conscious code
//如果设置数组容量大于目前的容量就要实现扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
public int indexOf(Object o)
返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。
public int indexOf(Object o) {
//如果参数o等于null，返回数组中第一个为null的下标索引
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
//返回第一个与o相等的数组元素下标
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
//没有返回-1
return -1;
}
public int lastIndexOf(Object o)
返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1
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;
}
public boolean contains(Object o)
判断数组中是否包含参数o
//判断数组中是否包含参数o
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public Object clone() 克隆函数
返回此ArrayList 实例的浅拷贝（元素本身不会被复制）
//返回此ArrayList 实例的浅拷贝（元素本身不会被复制）
//@return 此 ArrayList 实例的克隆
public Object clone() {
try {
ArrayList v = (ArrayList) super.clone();
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);
}
}
为什么要克隆？
1.想要复制一个对象，把属性一个一个的赋值给新new的对象很麻烦
2.clone是一个native方法，调用底层方法，操作系统实现，速度快
3.Object中本地clone()方法，默认是浅拷贝
Object person=new Object(); Object people=person;
这种形式的代码拷贝的是引用，即对象在内存中的地址，person和people对象仍然指向了同一个对象。而通过clone方法赋值的对象跟原来的对象时同时独立存在的
浅拷贝
在浅克隆中，如果原型对象的成员变量是值类型，将复制一份给克隆对象；如果原型对象的成员变量是引用类型，则将引用对象的地址复制一份给克隆对象，也就是说原型对象和克隆对象的成员变量指向相同的内存地址。
简单来说，在浅克隆中，当对象被复制时只复制它本身和其中包含的值类型的成员变量，而引用类型的成员对象并没有复制。
- 被复制的类需要实现Clonenable接口（不实现的话在调用clone方法会抛出CloneNotSupportedException异常)， 该接口为标记接口(不含任何方法)
- 覆盖clone()方法，访问修饰符设为public。方法中调用super.clone()方法得到需要的复制对象。（native为本地方法)
深拷贝
在深克隆中，无论原型对象的成员变量是值类型还是引用类型，都将复制一份给克隆对象，深克隆将原型对象的所有引用对象也复制一份给克隆对象。
简单来说，在深克隆中，除了对象本身被复制外，对象所包含的所有成员变量也将复制。
在Java语言中，如果需要实现深克隆，可以通过
-
重写Object类的clone()方法实现
-
通过序列化(Serialization)等方式来实现。
（如果引用类型里面还包含很多引用类型，或者内层引用类型的类里面又包含引用类型，使用clone方法就会很麻烦。这时我们可以用序列化的方式来实现对象的深克隆。）
序列化就是将对象写到流的过程，写到流中的对象是原有对象的一个拷贝，而原对象仍然存在于内存中。==通过序列化实现的拷贝不仅可以复制对象本身，而且可以复制其引用的成员对象，因此通过序列化将对象写到一个流中，再从流里将其读出来，可以实现深克隆。==需要注意的是能够实现序列化的对象其类必须实现Serializable接口，否则无法实现序列化操作。
public E get(int index)
public E get(int index) {
//检查索引是否在正确范围
rangeCheck(index);
return elementData(index);
}
public E set(int index, E element)
public E set(int index, E element) {
//检查索引是否在正确范围内
rangeCheck(index);
//记录之前元素的值
E oldValue = elementData(index);
//将index对应位置的元素替换
elementData[index] = element;
//返回之前指定位置的元素
return oldValue;
}
public boolean add(E e)
public boolean add(E e) {
//检查数组是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!! 增加被修改次数
//在末尾增加元素
elementData[size++] = e;
return true;
}
public void add(int index, E element)
在此列表中的指定位置插入指定元素。将当前在该位置的元素（如果有）和任何后续元素向右移动（向它们的索引添加一个）
public void add(int index, E element) {
//检查索引正确性 不能<0或者大于>size
rangeCheckForAdd(index);
//检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//将当前在该位置的元素（如果有）和任何后续元素向右移动
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//对应索引位置赋值
elementData[index] = element;
//元素个数++
size++;
}
public E 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);
//元素个数-1，最后一个设置为空
elementData[--size] = null; // clear to let GC do its work
//返回被删除的值
return oldValue;
}
public boolean remove(Object o)
从此列表中删除第一次出现的指定元素（如果存在）。
如果列表不包含该元素，则它保持不变。
public boolean remove(Object o) {
//如果要删除空位置
if (o == null) {
//遍历elementData
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//如果等于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
}
public void clear()
从此列表中删除所有元素。此调用返回后，列表将为空。
public void clear() {
//记录更改次数
modCount++;
// clear to let GC do its work
//遍历设置数组元素都为null
for (int i = 0; i < size; i++)
elementData[i] = null;
//元素个数设置为0
size = 0;
}
总结：
- ArrayList底层存储为数组，实现了RandomAccess接口，可以实现随机访问模式，因此查询和修改效率高
- 线程不安全，效率高
- 删除，插入效率慢，因为要移动整个数组
- 每次扩容为原来的1.5倍
源码里多次调用了System.arraycopy（），属于native方法
- 使用native关键字说明这个方法是原生函数，也就是这个方法是用C/C++语言实现的，并且被编译成了DLL，由java去调用。这些函数的实现体在DLL中，JDK的源代码中并不包含，对于不同的平台它们也是不同的。这也是java的底层机制，实际上java就是在不同的平台上调用不同的native方法实现对操作系统的访问的。
- native 是用做java 和其他语言（如c++）进行协作时用的，也就是native 后的函数的实现不是用java写的
- native的意思就是通知操作系统，让操作系统实现函数，java只能调用。
- java是跨平台的语言，既然是跨了平台，所付出的代价就是牺牲一些对底层的控制，而java要实现对底层的控制，就需要一些其他语言的帮助，这个就是native的作用了
- Java的不足除了体现在运行速度上要比传统的C++慢许多之外，Java无法直接访问到操作系统底层（如系统硬件等)，为此Java使用native方法来扩展Java程序的功能。
