系列文章目录

线性表之动态数组（ArrayList）的自实现_crazy_xieyi的博客-CSDN博客

文章目录

前言

一、ArrayList的三个构造方法解析

 public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        ArrayList<Integer> arrayList2 = new ArrayList<>(12);
        arrayList1.add(1);
        ArrayList<Integer> arrayList3 = new ArrayList<>(arrayList1);
        System.out.println(arrayList3);
    }

 注意：使用ArrayList(Collection<? extends E> c)这个构造方法时候，因为这里是通配符的上界，所以注意传入的类型必须是E或者E的子类。

二、ArrayList是如何扩容的？（源码分析）

首先看不带参数的构造方法：

 DEFAULT_CAPACITY = 10 默认容量为10；transient Object[] elementData，类似于顺序表背后的数组；private int size，size为有效元素的个数，此时为0，说明DEFAULTCAPACITY_EMPTY_ELEMENTDATA的长度为0，这个构造方法没有分配数组内存。

那么现在就有一个问题，DEFAULTCAPACITY_EMPTY_ELEMENTDATA的长度为0 与 默认容量为10为什么是矛盾的呢？此时没有大小，那第一次add添加数据的时候是怎么放进去的呢？

接下来，我们继续点击进入add方法里面：

 说明存储元素的时候，默认放到最后一个元素的后边的。但是这里用到了一个ensureCapacityInternal(size + 1)方法，我们在点击进入，

此时size为0，当size+1传进入的时候，这个时候， minCapacity为1；那么这里又有两个方法，这个calculateCapacity(elementData, minCapacity)方法的返回值  要作为 ensureExplicitCapacity()这个方法的参数。

那么我们再点击进入calculateCapacity(elementData, minCapacity)方法，这里顾名思义就是计算容量，此时minCapacity为1，因为此时调用的是没有带参数的构造方法，那么此时 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

此时 If 语句满足，那么就会求最大值，此时  minCapacity为1，DEFAULT_CAPACITY = 10，所以第一次调用add的时候，这个时候就会返回10。那么这个时候，返回值10就会作为ensureExplicitCapacity()的参数，那么我们再点击进入这个方法内部：

此时 minCapacity为10，此时 elementData这个数组的长度为0，那么10-0 > 0，那么就会调用grow这个函数，把10传过去。我们再点击grow进入这个函数内部：

 此时oldCapacity、newCapacity通过计算出来都是0，因为0 – 10 < 0的，那么此时newCapacity = minCapacity = 10。接下来再看下面一个if语句：

此时MAX_ARRAY_SIZE为 int 的最大值减8。这个时候这个if语句进不来，继续往下执行，那么此时这个数组才真正的分配内存。

elementData = Arrays.copyOf(elementData, newCapacity);

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

相当于 ensureCapacityInternal(size + 1)这个方法走完，数组的容量才是10，然后才能把元素放进去。所以可以总结，前提是调用不带参数的构造方法，第一次add的时候，默认容量才是10。

那么它是如何扩容的呢？比如在放第11个元素的时候？

接下来，我们还是继续看grow这个函数。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //按照1.5倍方式扩容
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小 
        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);
    }

 int newCapacity = oldCapacity + (oldCapacity >> 1);其实这一句代码就是在进行扩容，而且是1.5倍的扩容。 

其实带参数的构造方法，初始值给的多少，那么初始容量就是多少：

ArrayList(Collection<? extends E> c)这种构造方法，其实是进行的数组拷贝：

 小结：

三、ArrayList的常用方法

 这里需要注意List<E> subList(int fromIndex, int toIndex)这个方法：

 public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(3);
        arrayList1.add(4);
        arrayList1.add(5);
        List<Integer> list = arrayList1.subList(1,3);
        System.out.println(list);//2,3
        list.set(0,99);
        System.out.println(arrayList1);// 1,99,3,4,5
        System.out.println(list);//99,3
}

这个会发现，如果修改list里面的数据，那么arraylist里面的数据也会被修改。来看一张内存图就会明白怎么回事。

四、ArrayList的三种遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

 public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(3);
        arrayList1.add(4);
        arrayList1.add(5);

        int size = arrayList1.size();
        for (int i = 0; i < size; i++) {
            System.out.print(arrayList1.get(i)+" ");
        }
        System.out.println();
        for (int x : arrayList1) {
            System.out.print(x+" ");
        }
        System.out.println();

        Iterator<Integer> it =  arrayList1.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
}

五、ArrayList的缺陷