其余方法大都是线性时间

发布时间：2025-06-24 20:51:55  作者：北方职教升学中心  阅读量：021

【3】DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认容量为空数组实例。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。
【5】size：当前ArrayList中的元素数量。

三、

/**     * Increases the capacity of this <tt>ArrayList</tt> instance, if     * necessary, to ensure that it can hold at least the number of elements     * specified by the minimum capacity argument.     *     * @param   minCapacity   the desired minimum capacity     */publicvoidensureCapacity(intminCapacity){intminExpand =(elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// any size if not default element table?0// larger than default for default empty table. It's already// supposed to be at default size.:DEFAULT_CAPACITY;if(minCapacity >minExpand){ensureExplicitCapacity(minCapacity);}}privatevoidensureCapacityInternal(intminCapacity){if(elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity =Math.max(DEFAULT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);}privatevoidensureExplicitCapacity(intminCapacity){modCount++;// overflow-conscious codeif(minCapacity -elementData.length >0)grow(minCapacity);}/**     * The maximum size of array to allocate.     * Some VMs reserve some header words in an array.     * Attempts to allocate larger arrays may result in     * OutOfMemoryError: Requested array size exceeds VM limit     */privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;/**     * Increases the capacity to ensure that it can hold at least the     * number of elements specified by the minimum capacity argument.     *     * @param minCapacity the desired minimum capacity     */privatevoidgrow(intminCapacity){// overflow-conscious codeintoldCapacity =elementData.length;intnewCapacity =oldCapacity +(oldCapacity >>1);if(newCapacity -minCapacity <0)newCapacity =minCapacity;if(newCapacity -MAX_ARRAY_SIZE>0)newCapacity =hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData =Arrays.copyOf(elementData,newCapacity);}privatestaticinthugeCapacity(intminCapacity){if(minCapacity <0)// overflowthrownewOutOfMemoryError();return(minCapacity >MAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;}

七、它继承自AbstractList并实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。删除元素

publicEremove(intindex){rangeCheck(index);modCount++;EoldValue =elementData(index);intnumMoved =size -index -1;if(numMoved >0)System.arraycopy(elementData,index+1,elementData,index,numMoved);elementData[--size]=null;// clear to let GC do its workreturnoldValue;}

【1】remove(int index)：删除指定索引处的元素。
【3】elementData[size++] = e：将元素添加到数组中，并增加size。其余方法大都是线性时间。

publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{privatestaticfinalintDEFAULT_CAPACITY=10;privatestaticfinalObject[]EMPTY_ELEMENTDATA={};privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};transientObject[]elementData;// non-private to simplify nested class accessprivateintsize;}

【1】DEFAULT_CAPACITY：默认初始容量为10。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。获取元素

publicEget(intindex){rangeCheck(index);returnelementData(index);}privatevoidrangeCheck(intindex){if(index >=size)thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));}EelementData(intindex){return(E)elementData[index];}

【1】get(int index)：获取指定索引处的元素。当添加元素时，如果内部数组容量不足，就会创建一个更大的数组，并将旧数组中的元素复制到新数组中。

四、

六、在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

一、

二、每个ArrayList都有一个容量capacity，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。
【3】elementData(index)：返回数组中指定位置的元素。构造方法

publicArrayList(){this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}publicArrayList(intinitialCapacity){if(initialCapacity >0){this.elementData =newObject[initialCapacity];}elseif(initialCapacity ==0){this.elementData =EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("Illegal Capacity: "+initialCapacity);}}

【1】无参构造方法：初始化elementData为默认容量的空数组。
【4】ensureCapacityInternal(int minCapacity)：检查并确保内部数组的容量。
【6】grow(int minCapacity)：增加数组的容量，通常是原来容量的1.5倍。添加元素

publicbooleanadd(Ee){ensureCapacityInternal(size +1);// Increments modCount!!elementData[size++]=e;returntrue;}privatevoidensureCapacityInternal(intminCapacity){if(elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity =Math.max(DEFAULT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);}privatevoidensureExplicitCapacity(intminCapacity){if(minCapacity -elementData.length >0)grow(minCapacity);}privatevoidgrow(intminCapacity){intoldCapacity =elementData.length;intnewCapacity =oldCapacity +(oldCapacity >>1);if(newCapacity -minCapacity <0)newCapacity =minCapacity;if(newCapacity -MAX_ARRAY_SIZE>0)newCapacity =hugeCapacity(minCapacity);elementData =Arrays.copyOf(elementData,newCapacity);}

【1】add(E e)：添加元素到ArrayList中。

这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。
【4】elementData：存储元素的数组。
【2】rangeCheck(index)：检查索引是否越界。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。

五、
【2】ensureCapacityInternal(size + 1)：确保内部数组有足够的容量。
【2】rangeCheck(index)：检查索引是否越界。
【2】指定初始容量的构造方法：根据传入的初始容量创建数组。大小调整

ArrayList的核心在于其动态调整大小的能力，通过grow方法来实现。
【4】elementData[--size] = null：将最后一个元素设为null，帮助垃圾回收。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。
【5】ensureExplicitCapacity(int minCapacity)：如果需要，增加数组的容量。总结

Fail-Fast机制：ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。为追求效率，ArrayList没有实现同步synchronized，如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。成员变量

size(), isEmpty(), get(),set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。