ArrayList源码分析带案例

ArrayList

数组结构实现，查询快、增删慢

JDK1.2版本加入，运行效率快、线程不安全

源码分析

默认参数

参数解释默认值size当前数据个数0DEFAULT_CAPACITY默认容量10EMPTY_ELEMENTDATA初始数据{}DEFAULTCAPACITY_EMPTY_ELEMENTDATA初始容量及数据容量：0，数据：{}MAX_ARRAY_SIZE最大容量Integer.MAX_VALUE - 8

add()方法

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = 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); } - 案例一，当初始size()为0时，也就是在空的ArrayList内添加元素时，底层执行情况  - 案例二，当初始size()为10时，也就是在空的ArrayList内添加元素时，底层执行情况  - ==结论：初始长度为0，size为(0，10)时长度为10，之后递增5== remove()方法 //通过索引删除 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); elementData[--size] = null; // clear to let GC do its work return oldValue; } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. A subsequence of array components are copied from the source array referenced by `src` to the destination array referenced by `dest`. The number of components copied is equal to the `length` argument. The components at positions `srcPos` through `srcPos+length-1` in the source array are copied into positions `destPos` through `destPos+length-1`, respectively, of the destination array.If the `src` and `dest` arguments refer to the same array object, then the copying is performed as if the components at positions `srcPos` through `srcPos+length-1` were first copied to a temporary array with `length` components and then the contents of the temporary array were copied into positions `destPos` through `destPos+length-1` of the destination array. * @param src the source array. * @param srcPos starting position in the source array. * @param dest the destination array. * @param destPos starting position in the destination data. * @param length the number of array elements to be copied. **/ /** 从指定的源数组将数组从指定位置开始复制到目标数组的指定位置。数组组件的子序列从“src”引用的源数组复制到“dest”引用的目标数组。复制的组件数等于“length”参数。源数组中位置为“srcPos”到“srcPos+length-1”的组件将分别复制到目标的位置“destPos”到“destPos+length-1”数组。如果“src”和“dest”参数引用同一个数组对象，然后执行复制，就好像首先将位置为“srcPos”到“srcPos+length-1”的组件复制到具有“length”组件的临时数组中，然后将临时数组的内容复制到目标数组的“destPos”到“destPos+length-1”的位置。 *@param src源数组。 *@param srcPos源数组中的起始位置。 *@param dest目标数组。 *@param destPos目标数据中的起始位置。 *@param length要复制的数组元素数。 **/ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); //通过对象删除 public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == 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 static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); - 案例一，通过索引删除，index为2，size为8

- 案例二，通过对象删除

- ==总结：删除一个节点后，需要将后续的节点先复制到一个备用数组中，然后再讲备用数组内的数组，拷贝到目标数组的对应位置；根据对象删除的方法需要先找到``数组中第一个``与给定对对象相同的值得索引，然后根据索引删除的方法将其删除==