ArrayList大纲.PNG
1.ArrayList简介
可调整大小数组的实现，该类还提供了一些方法来控制用于内部存储列表的数组大小。
用Collections.synchronizedList方法“列出”列表。这最好在创建时完成，以防止意外的不同步访问列表：
ArrayList继承关系图
/**
* RandomAccess:支持随机快速访问
* Cloneable：允许被复制（浅复制和深复制后面的文章会提到，这里不作过多描述）
* Serializable:标识着集合可被序列化
*/
public class ArrayList<E> extends AbstractList<E>
implements Cloneable, Serializable, RandomAccess
2.ArrayList的基本特点
- 快速随机访问
- 有序，元素可重复（允许多个null元素）
- 底层是可调整大小的数组
- 增删元素效率较低；索引元素效率较快
3.构造器
常用参数
/**
* ArrayList 默认的数组容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 另一个共享空数组实例，用的不多,用于区别上面的EMPTY_ELEMENTDATA
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList底层的容器
*/
transient Object[] elementData; // non-private to simplify nested class access
//当前存放了多少个元素 并非数组大小
private int size;
底层数组使用transient关键字，为什么？
资料 ，被transient标记的不能序列化的。
但是ArrayList实际容器就是这个数组为什么标记为不序列化??那岂不是反序列化时会丢失原来的数据?
其实是ArrayList在序列化的时候会调用writeObject()，直接将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。
原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
- ArrayList (int initialCapacity)
用指定的初始容量构造一个空列表 - ArrayList ()
构造一个初始容量为10的空列表
注意：此时我们创建的ArrayList对象中的elementData中的长度是1，size是0,当进行第一次add的时候，elementData将会变成默认的长度：10. - ArrayList (Collection<? extends E> c)
按照集合迭代器返回的顺序构造一个包含指定集合元素的列表。
3.特殊方法
- Object clone（）
返回此ArrayList实例的浅表副本。 （元素本身不被复制。）
ArrayList<A> as = new ArrayList<>();
as.add(new A("uart"));
as.add(new A("bobo"));
ArrayList<A> asList = new ArrayList<>(as.size());
ListIterator<A> aListIterator =
as.listIterator();
while (aListIterator.hasNext()){
try {
asList.add(aListIterator.next().clone());
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
}
as.set(0,new A("u"));
as.toString();
asList.toString();
}
static class A implements Cloneable{
private String name;
public A(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
protected A clone() throws CloneNotSupportedException {
A a = null;
a = (A) super.clone();
return a;
}
}
- void ensureCapacity (int minCapacity)
如有必要，增加此ArrayList实例的容量，以确保它至少能容纳由最小容量参数指定的元素数量。 - void trimToSize ()
将此ArrayList实例的容量修剪为列表的当前大小。应用程序可以使用此操作来最小化ArrayList实例的存储。 - void removeRange (int fromIndex, int toIndex)
从此列表中删除索引介于fromIndex和inclusive之间的所有元素。将任何后续元素向左移（减少索引）。此调用通过（toIndex - fromIndex）元素缩短列表。 （如果toIndex == fromIndex，则此操作无效。）
添加方法集合
/**
* ArrayList 默认的数组容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 另一个共享空数组实例，用的不多,用于区别上面的EMPTY_ELEMENTDATA
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList底层的容器
*/
transient Object[] elementData; // non-private to simplify nested class access
//当前存放了多少个元素 并非数组大小
private int size;
/**
* 1.先判断是否需要扩容（如果是一个空数组则自动扩容为10）
* 2.判断是否溢出，如果溢出则扩容为原来的1.5倍
* 3.通过Arrays.copyOf()复制
* 4.添加元素到末尾
*/
public boolean add(Object e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果是以ArrayList()构造方法初始化,那么数组指向的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA.第一次add()元素会进入if内部,
//且minCapacity为1,那么最后minCapacity肯定是10,所以ArrayList()构造方法上面有那句很奇怪的注释.
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
// overflow-conscious code
//1. 记录之前的数组长度
int oldCapacity = elementData.length;
//2. 新数组的大小=老数组大小+老数组大小的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
//3. 判断上面的扩容之后的大小newCapacity是否够装minCapacity个元素
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - 10000 > 0)
newCapacity = hugeCapacity(minCapacity);
//5. 复制数组,注意,这里是浅复制
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > 10000) ?
Integer.MAX_VALUE :
10000;
}
/**
* 1.判断index是否在限定范围内
* 2.判断是否需要扩容
* 3.将elementData元素从index开始的size - index个元素移动到elementData的index + 1处。
* 4.在移动的位置放入element
* @param index
* @param element
*/
public void add(int index,Object element){
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
//从elementData的indesx开始的size-index长度的元素复制到size+1的位置；
//相当于Index处开始，后面的元素向后移动了一位
System.arraycopy(elementData,index,elementData,index + 1 ,size - index);
elementData[index] = element;
size ++;
}
/**
* 1.判断是否需要扩容
* 2.集合c从0开始的number个元素移动到elementData元素的位置
* 3.记录元素长度
* @param c
* @return
*/
public boolean addAll(Collection<? extends Object> c){
Object[] array = c.toArray();
int number = array.length;
ensureCapacityInternal(size + number);
System.arraycopy(c,0,elementData,size,number);
size += number;
return number != 0;
}
/**
* 1.检查Index是否在指定范围
* 2.是否需要扩容
* 3.elementData从index开始的size - index个元素移动到elementData的index + length处
* 4.c从0开始的length个元素移动到elementData移动到Index元素的位置
* @param index
* @param c
* @return
*/
public boolean addAll(int index,Collection<? extends Object> c){
rangeCheckForAdd(index);
Object[] array = c.toArray();
int length = array.length;
ensureCapacityInternal(size + length);
if(size > index)
System.arraycopy(elementData,index,elementData,index + length,size - index);
System.arraycopy(c,0,elementData,index,length);
size += length;
return length != 0;
}
private void rangeCheckForAdd(int index) {
if(index > size || index < 0) {
throw new IndexOutOfBoundsException("out of bounds");
}
}
//集合删，改，查
public Object remove(int index) {
//1. 检查参数是否合法
rangeCheck(index);
//2. 记录下需要移除的元素
Object oldValue = elementData[index - 1];
//3. 需要往前面挪动1个单位的元素个数
int numMoved = size - index - 1;
if (numMoved > 0) //后面有元素才挪动
//4. 将index后面的元素(不包含index)往前"挪动"(复制)一位
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
//5. 这里处理得很巧妙,首先将size-1,然后将elementData原来的最后那个元素赋值为null(方便GC回收)
elementData[--size] = null; // clear to let GC do its work
//6. 将旧值返回
return oldValue;
}
//检查参数是否合法 参数>size抛出IndexOutOfBoundsException 参数小于0则抛出ArrayIndexOutOfBoundsException
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException("out of bounds");
}
public boolean remove(Object o) {
//1. 是否为null
if (o == null) {
//2. 循环遍历第一个为null的元素
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//3. 移除 移除之后就返回true
fastRemove(index);
return true;
}
} else {
//4. 循环遍历第一个与o equals()的元素
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
//5. 移除指定位置元素
fastRemove(index);
return true;
}
}
return false;
}
/*
私有的方法,移除指定位置元素,其实和remove(int index)是一样的.不同的是没有返回值
*/
private void fastRemove(int 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
}
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c);
}
/**
* 1.判断C集合中是否包含指定元素；没有就将数组设为改制并做自增处理
* 2.循环异常终止将r后面的元素移动到w之后。并且修改w下标值
* 3.循环遍历元素将w后面的元素置空
* @param c
* @return
*/
private boolean batchRemove(Collection<?> c) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++) {
if(!c.contains(elementData[r])) //C集合中不包含指定元素
elementData[w ++] = elementData[r];
}
} finally {
if(r != size) {//做一层安全校验
System.arraycopy(elementData,r,elementData,w,size - r);
w += size - r;
}
if(w != size) {//需要删除元素，否则不需要删除任何元素
for (int i = w ; i < size ; i ++){
elementData[i] = null;
}
size = w;
modified =true;
}
}
return modified;
}
private void clear(){
for (int i = 0 ; i < size ; i ++)
elementData[i] = null;
size = 0;
}
protected void removeRange(int fromIndex, int toIndex){
int numMoved = size - toIndex;
System.arraycopy(elementData,toIndex,elementData,fromIndex,numMoved);
int newSize = size - (toIndex - fromIndex);
for (int i = newSize ; i < size ; i ++){
elementData[i] = null;
}
size = newSize;
}
public Object set(int index,Object obj){
rangeCheck(index);
Object oldValue = elementData[index - 1];
elementData[index - 1] = obj;
return oldValue;
}
/**
* 返回指定位置处元素
*/
public Object get(int index) {
rangeCheck(index);
return elementData[index - 1];
}
4.特别注意
1.CopyOnWriteArrayList是List的一个特殊实现，专门用于并发编程
