ArrayList概述（一）ArrayList是一个基于定长数组实现的变长集合类。(2)ArrayList允许空值和重复元素。当添加到ArrayList的元素数量大于其底层数组的容量时，它会通过扩容机制重新生成一个更大的数组。(3)由于ArrayList底层是基于数组实现的，因此可以保证在O(1)复杂度下完成随机查找操作。(4)ArrayList是一个非线程安全的类。在并发环境下，多个线程同时操作ArrayList，会导致不可预知的异常或错误。ArrayList的成员属性在介绍ArrayList的各种方法之前，先来看看基本的属性成员。DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA之间的区别是：当我们将第一个元素添加到数组时，DEFAULTCAPACITY_EMPTY_ELEMENTDATA将知道数组应该扩展多少。//默认初始化容量privatestaticfinalintDEFAULT_CAPACITY=10;//默认空数组，这个主要是为了使用privatestaticfinalObject[]EMPTY_ELEMENTDATA={};//构造函数初始化空数组时使用默认大小空数组实例的大小与EMPTY_ELEMENTDATA区别开来，//这样我们就可以知道在添加第一个元素时要扩展多少privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};//ArrayList底层存储数据是通过数组形式，ArrayList的长度就是数组的长度。//一个空的实例elementData就是上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当添加第一个元素的时候//就会扩容，扩容大小就是上面默认的容量DEFAULT_CAPACITYtransientObject[]elementData;//非私有以简化嵌套类访问//arrayListsizeprivateintsize;复制代码静态修改EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATAArrayList构造方法（1）构造方法参数初始化容量大于0，elementData初始化为initialCapacity大小数组参数小于0，elementData初始化为空数组参数小于0，抛出异常//参数为初始容量publicArrayList(intinitialCapacity){//判断容量的合法性if(initialCapacity>0){//elementData为实际存放元素的数组this.elementData=newObject[initialCapacity];}elseif(initialCapacity==0){//如果传入的长度为0，则直接使用自己定义的成员变量（空数组）this.elementData=EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("IllegalArgumentException:"+initialCapacity);}}复制代码(2)在无参构造方法中，将elementData初始化为空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA在调用add方法添加第一个元素时，会扩容直到大小为DEFAULT_CAPACITY=10//无参数构造，使用默认大小为10的空数组，构造方法中没有设置数组的长度，会在后续调用add方法时扩容publicArrayList(){this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}复制代码(3)参数为Collection类型的构造函数//将参数为Collection的集合转换为ArrayList(实际上，集合数组中的元素都变成了数组的形式）如果//传入的集合为null，则会抛出空指针异常（调用c.toArray()方法时）publicArrayList(Collectionc){elementData=c.toArray();if((size=elementData.length)!=0){//c.toArray()可能无法正确返回Object[]数组，然后使用Arrays.copyOf()methodif(elementData.getClass()!=Object[].class)elementData=Arrays.copyOf(elementData,size,Object[].class);}else{//如果数组的长度是0集合转换为数组后，直接使用自己的空间成员变量初始化elementDatathis.elementData=EMPTY_ELEMENTDATA;}}复制代码以上构造方法比较简单易懂。关注前两种构造方法的作用。目的是初始化底层数组elementData(this.elementData=XXX)。不同之处在于，无参数构造函数会将elementData初始化为空数组，而在插入元素时，扩展会使用默认值重新初始化数组。带参数的构造函数会将elementData初始化为参数值大小的数组(>=0)。一般情况下，我们可以使用默认的构造方法。如果您知道有多少元素将被插入到ArrayList中，您可以使用参数化构造函数。上面说了，使用无参结构时，调用add方法时会扩容，下面具体看一下add方法和扩容的细节。最后publicbooleanadd(Ee){//因为需要添加元素，添加后容量可能不够，所以需要在添加（扩展）前判断ensureCapacityInternal(size+1);//递增modCount!!(后面我们会介绍fast-fail)elementData[size++]=e;returntrue;}复制代码我们看到在add方法中添加元素之前，会先判断size的大小，所以我们来看一下ensureCapacityInternal方法的详细信息。ensureCapacityInternal方法分析privatevoidensureCapacityInternal(intminCapacity){//这里是判断elementData数组是否为空数组//（使用无参构造时，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA）//如果是，则比较size+1（第一次调用的时候，size+1=1)andDEFAULT_CAPACITY,//那么显然容量是10if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);}复制代码当要添加第一个元素时，minCapacity为(size+1=0+1=)1，经过Math.max()方法比较后，minCapacity为10。然后调用ensureExplicitCapacity更新modCount的值，判断是否需要扩展ensureExplicitCapacity方法来分析privatevoidensureExplicitCapacity(intminCapacity){modCount++;//这里是add方法中注释掉的IncrementsmodCount//overflowif(minCapacity-elementData.length>0)grow(minCapacity);//这里是进行扩容的方法}复制代码先看main扩容方法grow。grow方法分析privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;privatevoidgrow(intminCapacity){//oldCapacity为旧数组的容量intoldCapacity=elementData.length;//newCapacity为新数组的容量（oldCap+oldCap/2：更新为旧容量的1.5倍）intnewCapacity=oldCapacity+(oldCapacity>>1);//检查新容量的大小是否小于所需的最小容量，如果小于旧容量，则最小容量为数组的新容量if(newCapacity-minCapacity<0)newCapacity=minCapacity;//如果新容量大于MAX_ARRAY_SIZE，则使用hugeCapacity比较两者if(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//minCapacity通常接近size，所以这是一个win://复制原数组中的元素elementData=Arrays.copyOf(elementData,newCapacity);}复制代码hugeCapacity方法这里简单看一下hugeCapacity方法privatestaticinthugeCapacity(intminCapacity){if(minCapacity<0)//overflowthrownewOutOfMemoryError();//比较minCapacity和MAX_ARRAY_SIZE//如果minCapacity很大，使用Integer.MAX_VALUE作为新数组的大小//如果MAX_ARRAY_SIZE很大，使用MAX_ARRAY_SIZE作为新数组的大小//MAX_ARRAY_SIZE=Integer.MAX_VALUE-8;返回（分钟容量>MAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;}复制代码Add方法执行流程总结下面用一张图简单梳理下使用无参构造时add方法第一次调用后的执行流程。这是第一次调用add方法的过程。当扩容值capacity为10时，继续添加第二个元素（首先注意调用ensureCapacityInternal方法传递的参数为size+1=1+1=2）在ensureCapacityInternal方法中，elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA不成立，所以直接执行ensureExplicitCapacity方法。ensureExplicitCapacity方法中，minCapacity是刚刚传过来的2，所以第二次if判断(2-10=-8)不会成立，即如果newCapacity不大于MAX_ARRAY_SIZE，则不会进入grow的容量方法数组为10，在add方法中返回true，size增加为1。假设添加了3、4...10个元素（过程类似，但不会执行grow扩展方法）。当添加第11个元素时，会进入grow方法，计算出newCapacity为15，高于minCapacity（10+1=11），第一个if判断不成立。如果新容量不大于数组的最大尺寸，则不会进入hugeCapacity方法。数组容量扩容到15，add方法返回true，大小增加到11。add(intindex,Eelement)method//在元素序列的索引位置插入publicvoidadd(intindex,Eelement){rangeCheckForAdd(index);//检查传入的index参数是否合法//1.检测是否需要扩容ensureCapacityInternal(size+1);//递增modCount!!//2.将索引及其后的所有元素向后移动一位System.arraycopy(elementData,index,elementData,index+1,size-index);//3.插入一个新元素indexelementData[index]=element;size++;}privatevoidrangeCheckForAdd(intindex){if(index>size||index<0)//这里判断的index>size（保证数组的连续性），index为lessthan0thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));}复制代码add(intindex,Eelement)方法（在元素序列的指定位置插入（假设位置合理））大概下面检查是否有数组中有足够的空间（这里和上面的实现）将索引和它之后的所有元素向后移动一位并将新元素插入索引。要将新元素插入序列的指定位置，需要先将该位置和后面的元素向后移动一位，为新元素腾出空间。该操作的时间复杂度为O(N)，频繁移动元素可能会造成效率问题，尤其是当集合中的元素数量较多时。在日常开发中，除非必要，尽量避免在大集合中调用第二个insert方法。ArrayList的remove方法ArrayList支持两种方式删除元素1.remove(intindex)根据下标删除publicEremove(intindex){rangeCheck(index);//检查下标是否合法（如果index>size，old会抛出IndexOutOfBoundsException）modCount++;//修改链表结构，需要更新这个值EoldValue=elementData(index);//直接在数组中查找这个值intnumMoved=size-index-1;//这里计算要移动的个数//如果这个值大于0，说明还有后续元素需要移动到theleft(size=index+1)//如果为0，表示移除的对象是最后一个元素（不需要移动其他元素）if(numMoved>0)//移动索引index的所有元素向左移动一位覆盖索引位置的元素System.arraycopy(elementData,index+1,elementData,index,numMoved);//移动后，原数组中的大小PositionnullelementData[--size]=无效的;//清除让GC做它的工作//返回旧值returnoldValue;}//src:源数组//srcPos:从源数组的srcPos位置开始移动//dest:目标数组//desPos:The从源数组的srcPos位置开始移动的元素，这些元素从目标数组的desPos开始填充//length：移动源数组的长度publicstaticnativevoidarraycopy(Objectsrc,intsrcPos,Objectdest,intdestPos,int长度);复制代码删除流程如下图2.remove(Objecto)按元素删除，删除public匹配参数的第一个元素booleanremove(Objecto){//如果元素为null，遍历数组去掉第一个nullif(o==null){for(intindex=0;index
