数据结构---ArrayList

前言

ArrayList:初始长度：10，扩容原来度的1.5倍，obejct动态数组，数据的特点就是查询数据快。只要不在末尾添加或删除元素，那么元素的位置都要进行移动，详情看之后的分析

ArrayList: add(E e)

public boolean add(E e) {
        //检查添加数据是否需要扩容
        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,如果大于调用grow()进行扩容操作。
假设elementData的长度为10，已经填满了数据，现在再添加一个数据,一直走到grow方法中，oldCapacity =10，newCapacity =15。15-10>0，第一个if不用走，第二个也不用走了，利用Arrays.copyOf()方法进行数组扩容。

newCapacity =15？怎么算

>>右移运算符：凡位运算符都是把值先转换成二进制再进行后续的处理，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));
        //判断数组需要扩容
        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;
        //判断数组需要扩容
        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};经过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() 并没有调用过这个方法

   /**
     * 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);
        }
    }