前言

ArrayList:初始長度：10，擴容原來度的1.5倍，obejct動態(tài)數(shù)組，數(shù)據(jù)的特點就是查詢數(shù)據(jù)快。只要不在末尾添加或刪除元素，那么元素的位置都要進行移動，詳情看之后的分析

ArrayList: add(E e)

public boolean add(E e) {
        //檢查添加數(shù)據(jù)是否需要擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        /**
          * size++;
          *  elementData[size]=e;
          */
        elementData[size++] = e;
        return true;
    }

下面把擴容的邏輯代碼貼出來分析

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(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);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

在ensureCapacityInternal()里面先判斷elementData的值是否等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果等于minCapacity =10,
否則等于傳進來的值,再進ensureExplicitCapacity()，判斷minCapacity 是否大于elementData.length,如果大于調(diào)用grow()進行擴容操作。
假設(shè)elementData的長度為10，已經(jīng)填滿了數(shù)據(jù)，現(xiàn)在再添加一個數(shù)據(jù),一直走到grow方法中，oldCapacity =10，newCapacity =15。15-10>0，第一個if不用走，第二個也不用走了，利用Arrays.copyOf()方法進行數(shù)組擴容。

newCapacity =15？怎么算

>>右移運算符：凡位運算符都是把值先轉(zhuǎn)換成二進制再進行后續(xù)的處理，10的二進制是1010，在計算機中是0000 1010，高位補零。二進制用短除法操作

image.png

下面用int[] 演示一下添加元素擴容的操作，int[] 的默認值位0

  private static int[] sourceArray={1,2,3,4,5,6,7,8,9,10};

    public static void main(String[] args){
        int index=10;
        int size=sourceArray.length;
        //多余判斷只是為了更好的理解
        if(size==sourceArray.length){
            int oldLength=sourceArray.length;
            int newLength=oldLength+(oldLength >> 1);
            sourceArray=Arrays.copyOf(sourceArray,newLength);
        }
        //也可以這樣寫
//        if(size==sourceArray.length){
//            int oldLength=sourceArray.length;
//            int newLength=oldLength+(oldLength >> 1);
//            int[] newInt= new int[newLength];
//            for (int i = 0; i < oldLength; i++) {
//                newInt[i]=sourceArray[i];
//            }
//            sourceArray=newInt;
//        }
        sourceArray[size++]=11;

        for (int i = 0; i <sourceArray.length; i++) {
            System.out.print(sourceArray[i]+",");
        }
        System.out.println("sourceArray的長度："+sourceArray.length);
    }

打印的值：1,2,3,4,5,6,7,8,9,10,11,0,0,0,0,sourceArray的長度：15

ArrayList:add(int index, E element), addAll(Collection<? extends E> c)這兩個差不多，分析add(int index, E element)就ok了

public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //判斷數(shù)組需要擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

 public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        //判斷數(shù)組需要擴容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

image.png

下面用int[] 演示一下add(int index, E element)的操作，int[] 的默認值位0，
int[] sourceArray={1,2,3,4,5,6,7,8,9,10};經(jīng)過System.arraycopy()操作之后變成
sourceArray={1,2,3,4,5,6,6,7,8,9,10,0,0,0,0} [index,index]

private static int[] sourceArray={1,2,3,4,5,6,7,8,9,10};

    public static void main(String[] args){
        int index=5;
        int size=sourceArray.length;
        //多余判斷只是為了更好的理解
        if(size==sourceArray.length){
            int oldLength=sourceArray.length;
            int newLength=oldLength+(oldLength >> 1);
            sourceArray=Arrays.copyOf(sourceArray,newLength);
        }
            System.arraycopy(sourceArray,index,sourceArray,index+1,size-index);

            sourceArray[index]=15;
            size++;
        for (int i = 0; i <sourceArray.length; i++) {
            System.out.print(sourceArray[i]+",");
        }
        System.out.println("sourceArray的長度："+sourceArray.length);
    }

刪除元素和添加元素都是一樣的原理，基本沒有太大差別。還有在刪除元素中它并沒有進行一個縮容的操作，在ArrayList源碼中trimToSize() 并沒有調(diào)用過這個方法

   /**
     * Trims the capacity of this <tt>ArrayList</tt> instance to be the
     * list's current size.  An application can use this operation to minimize
     * the storage of an <tt>ArrayList</tt> instance.
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }