前言ArrayList是由数组实现的List。与数组相比，它具有动态扩展的能力，所以也可以称为动态数组。ArrayList集合中可以存储任何类型的数据，它是一个顺序容器。存储数据的顺序和我们放入的顺序是一样的，也可以让我们放入null元素。继承系统publicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{...}ArrayList实现List，提供增删改查等基本操作。ArrayList实现了RandomAccess，它提供了随机访问的能力。ArrayList实现了Cloneable并且可以被克隆。ArrayList实现了Serializable，可以被序列化。源码解析属性/***默认容量*/privatestaticfinalintDEFAULT_CAPACITY=10;/***空数组，如果传入容量为0则使用*/privatestaticfinalObject[]EMPTY_ELEMENTDATA={};/***空数组，传入容量时使用，当第一个元素加入时，会重新初始化为默认容量大小*/privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};/***存放元素的数组*/瞬态对象[]元素数据；//非私有以简化嵌套类访问/***集合中元素的数量*/privateintsize;(1)DEFAULT_CAPACITY：默认容量为10，即newArrayList()创建时的默认容量。(2)EMPTY_ELEMENTDATA：一个空数组，这个空数组在通过newArrayList(0)创建的时候使用。(3)DEFAULTCAPACITY_EMPTY_ELEMENTDATA：也是一个空数组。newArrayList()创建时使用这个空数组。与EMPTY_ELEMENTDATA不同的是，在添加第一个元素时，空数组会被初始化为DEFAULT_CAPACITY(10)个元素。(4)elementData：实际存放元素的地方。(5)size：实际存储的元素个数，不是elementData数组的长度。ArrayList的elementData数组为什么要加上瞬态修饰？由于ArrayList有自动扩容机制，ArrayList的elementData数组的大小往往大于已有元素的个数。如果不加transient而直接序列化，数组中空出的位置也会被序列化。它不见了，浪费了很多空间。ArrayList中重写了序列化和反序列化对应的writeObject和readObject方法。遍历数组元素时，以size作为结束标记，只对ArrayList中已经存在的元素进行序列化。ArrayList(intinitialCapacity)构造方法publicArrayList(intinitialCapacity){if(initialCapacity>0){//如果传入的初始容量大于0，则新建一个数组存储元素this.elementData=newObject[initialCapacity];}elseif(initialCapacity==0){//如果传入的初始容量等于0，则使用空数组EMPTY_ELEMENTDATAthis.elementData=EMPTY_ELEMENTDATA;}else{//如果传入的初始容量小于0，则抛出异常thrownewIllegalArgumentException("IllegalCapacity:"+initialCapacity);}}ArrayList()构造方法publicArrayList(){//如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA//添加第一个元素时使用此数组展开到默认大小10this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}ArrayListconstructor/***初始化传入集合的元素到ArrayList中*/publicArrayList(Collectionc){//集合到数组elementData=c.toArray();if((size=elementData.length)!=0){//检查c.toArray()是否返回Object[]类型，如果不是，则复制到Object[].class类型if(elementData.getClass()!=对象[].类)elementData=Arrays.copyOf(elementData,size,Object[].class);}else{//如果c有一个空集合，它将被初始化为一个空数组EMPTY_ELEMENTDATAthis.elementData=EMPTY_ELEMENTDATA;}}add(Ee)方法添加元素到最后，平均时间复杂度为O(1)publicbooleanadd(Ee){//检查是否需要扩展ensureCapacityInternal(size+1);//插入元素到最后一个元素Data[size++]=e;returntrue;}privatevoidensureCapacityInternal(intminCapacity){ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));}privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){//如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA如果(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){returnMath.max(DEFAULT_CAPACITY,minCapacity)初始化为默认大小10}returnminCapacity;}privatevoidensureExplicitCapacity(intminCapacity){modCount++;if(minCapacity-elementData.length>0)//expandgrow(minCapacity);}privatevoidgrow(intminCapacity){intoldCapacity=elementData.length;//新容量是旧容量的1.5倍intnewCapacity=oldCapacity+(oldCapacity>>1);//如果发现新容量小于需求容量，则以需求容量为准if(newCapacity-minCapacity<0)newCapacity=minCapa城市;//如果新容量超过最大容量，则使用最大容量if(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//复制一个新容量的数组elementData=Arrays.copyOf(elementData,newCapacity);}add(intindex,Eelement)方法在指定位置添加一个元素，平均时间复杂度为O(n)publicvoidadd(intindex,Eelement){//检查是否越界rangeCheckForAdd(index);//检查是否需要扩容ensureCapacityInternal(size+1);//将inex和后面的元素往后移一位，则索引位置为空System.arraycopy(elementData,index,elementData,index+1,size-index);//将元素插入到索引的位置elementData[index]=element;//size增加1size++;}privatevoidrangeCheckForAdd(intindex){if(index>size||index<0)thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));}为什么ArrayList添加的时候慢？通过上面的源码我们可以看到，ArrayList有指定的索引需要添加，有的是直接添加的。在此之前，它会有一个检查长度的步骤来判断ensureCapacityInternal，即如果长度不够，就需要扩容。扩容的时候，老版本的jdk和8之后的版本是有区别的，8之后效率更高，使用位操作右移一位，其实就是除以的操作2.intnewCapacity=oldCapacity+(oldCapacity>>1);新增阵列的容量是旧阵列容量的1.5倍。添加指定位置时，校验后的操作很简单，就是数组的拷贝，System.arraycopy(elementData,index,elementData,index+1,size-index);为了更好的解释，这里有一个图片如下：比如有一个像下面这样的数组，我需要在index为4的位置添加一个元素a，从代码中我们可以看出它复制了一个数组，从索引4的位置开始，然后放到索引4+1的位置，为我们要添加的元素腾出空间，然后将元素a放到索引的位置，完成新增操作。这只是在这么小的List中的一个操作。如果我在一个百、几万、几万大小的List中添加一个元素，那么后面的所有元素都需要复制，然后如果涉及到扩容就比较慢了。是不是。addAll方法查找两个集合的并集。/***将集合c中的所有元素添加到当前ArrayList*/publicbooleanaddAll(Collectionc){//将集合c转换为数组Object[]a=c.toArray();intnumNew=a.length;//检查是否需要扩展ensureCapacityInternal(size+numNew);//将c中的所有元素复制到数组末尾System.arraycopy(a,0,elementData,size,numNew);//增加大小c的大小size+=numNew;//如果c不为空则返回true，否则返回falsereturnnumNew!=0;}get(intindex)方法获取指定索引位置的元素，时间复杂度为O(1)。publicEget(intindex){//检查是否越界rangeCheck(index);//返回数组索引位置的元素returnelementData(index);}privatevoidrangeCheck(intindex){if(index>=size)thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));}EelementData(intindex){return(E)elementData[index];}(1)检查索引是否越界，这里只检查是否越界，如果越界则抛出IndexOutOfBoundsException，如果下界则抛出ArrayIndexOutOfBoundsException被抛出。(2)返回索引位置的元素；remove(intindex)方法删除指定索引位置的元素，时间复杂度为O(n)。publicEremove(intindex){//检查是否越界rangeCheck(index);模数++；//获取索引位置的元素EoldValue=elementData(index);//如果index不是最后一个，则移除index之后的元素向前移动一位intnumMoved=size-index-1;如果(numMoved>0)System.arraycopy(elementData,index+1,elementData,index,numMoved);//删除最后一个元素帮助GCelementData[--size]=null;//明确让GC干活//返回旧值returnoldValue;}remove(Objecto)方法删除指定元素值的元素，时间复杂度为O(n)。publicbooleanremove(Objecto){if(o==null){//遍历整个数组，找到元素第一次出现的位置，快速删除for(intindex=0;index0)System.arraycopy(elementData,index+1,elementData,index,numMoved);//删除最后一个元素，帮助GCelementData[--size]=null;//明确让GC做它的工作}(1)找到第一个等于指定元素值的元素；(2)快速删除，快速与remove(intindex)相比，tRemove(intindex)少了检查索引越界的操作。retainAll方法找到两个集合的交集。publicbooleanretainAll(Collectionc){//集合c不能为nullObjects.requireNonNull(c);//调用批量删除方法，此时补码传true，表示删除c中不包含的元素returnbatchRemove(c,true);}/***批量删除元素*补码为true删除元素notincludedinc*complementisfalse删除c中包含的元素*/privatebooleanbatchRemove(Collectionc,booleancomplement){finalObject[]elementData=this.elementData;//使用读写两个指针同时遍历数组//每次读指针加1，放置元素时写指针加1//这样不需要额外的空间，只需要对原数组进行操作intr=0,w=0;布尔修改=假；try{//遍历整个数组，如果c包含该元素，则将该元素放在write指针的位置（以补码为准）for(;rc){//集合c不能为空Objects.requireNonNull(c);//同样调用批量删除方法，此时补码传入false，表示删除c中包含的元素returnbatchRemove(c,false);}类似于retainAll(Collectionc)method，但不在c中的元素在这里保留。总结（一）ArrayList内部使用数组来存储元素。扩展的时候，每次增加一半的空间，ArrayList不会收缩。(2)ArrayList支持随机访问，通过索引访问元素速度极快，时间复杂度为O(1)。(3)向ArrayList尾部添加元素速度极快，平均时间复杂度为O(1)。(4)ArrayList中间添加元素比较慢，因为移动元素的平均时间复杂度是O(n)。(5)ArrayList从尾部删除元素的速度极快，时间复杂度为O(1)。(6)ArrayList从中间删除元素比较慢，因为移动元素的平均时间复杂度是O(n)。(7)ArrayList支持并集，调用addAll(Collectionc)方法即可。(8)ArrayList支持交集，调用retainAll(Collectionc)方法即可。(7)ArrayList支持单向差分，调用removeAll(Collectionc)方法即可。
