ArrayList 的自白

大家好，我的名字叫 ArrayList，是 Josh Bloch、Neal Gafter 在 JDK1.2 的时候创造的我。下面是我的 “基因序列”（ 继承的接口 ）

并且，我还有很多的兄弟姐妹，以后我会一一介绍他们：

• LinkedList
• Vector
• …

自我讲解

首先，我是 Java 世界中对 数组 这个数据结构的实现。并且我是一个天生可以自动扩容的 动态数组。

那么接下来，我就先讲一下什么是数组，然后再深入讲一下我是如何自动扩容的。

数组

看，这就是一维数组。它是一段连续的空间，并且不能进行扩容。相同数据类型的元素按照先后顺序排列，每个元素都有一个下标。下标从 0 开始。

在 Java 中，你可以使用以下方式创建一个数组。

int [] array = new int []{99,88,77,66,55};
复制代码

多维数组

既然有一维数组，则就有多维数组。如上图所示，理论可以创建无数维数组。

其余操作与一位数组基本一致。说白了，就是俄罗斯套娃

在 Java 中，你可以使用以下方式来创建多维数组。

    int[][] _2DArray = {{1, 2}, {3, 4}};
复制代码

查找

由于数组有下标，如果你拥有该元素的下标。那么你查找到该元素的时间非常快，其时间复杂度为O(1)。

如果你不理解什么是时间复杂度，请点击传送门 。

但如果你没有下标，那么很不幸。你需要遍历所有的节点才能找到你想要的元素。其时间复杂度为O(n)。也许有一些算法可以帮助你，但这不在本篇文章的讨论范围内。

在 Java 中，你可以使用下标来获取。

class Scratch {
    public static void main(String[] args) {
        int[] array = new int[]{99, 88, 77, 66, 55};
        System.out.println(array[0]); // output is 99
    }
}
复制代码

也可以通过foreach遍历来寻找需要的元素。

class Scratch {
    public static void main(String[] args) {
        int[] array = new int[]{99, 88, 77, 66, 55};
        Integer ninety_nine = findNinetyNine(array);
        if (ninety_nine != null)
            System.out.println(ninety_nine);  // output is 99
        System.out.println("Can not found 99!");
    }

    private static Integer findNinetyNine(int[] array) {
        for (int i : array) 
            if (i == 99) return i;
        return null;
    }
}
复制代码

添加

由于数组每次都是申请好的内存，所以不允许添加元素。但是你可以将值重新赋值给一个新的数组，从而实现添加的功能。

删除

数组的删除直接将该数组的元素设置为 null 即可，但它在删除后不会调整数组的长度。

动态数组

经过上面的讲解，我们已经知道了什么是 数组，并且也知道了其大致的优缺点：

优点：

• 数组内元素按照先后顺序进行排列
• 数组在依靠下标 index 进行索引时，其时间复杂度为 O(1)

缺点：

• 数组不支持动态添加节点与扩容
• 数组不支持删除节点后自动调整数组长度

为了解决上述的缺点，就出现了动态数组。

在 Java 世界中，我就是动态数组的一个标准实现。接下来我和大家一起剖析一下我是如何实现自动扩容和删除后调整长度的吧～

自动扩容

理论

理论上其实很简单，我们预先申请一段内存空间。每次添加时都判断一下当前节点是否达到我们的最大长度，如果达到了我们就扩容一下即可。

实践

打开我（ ArrayList ）的源码，里面有一个 add 方法详细的讲述了该过程。为了简洁我们截取了片段代码。

/**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)  //(1)
            elementData = grow();     //(2)
        elementData[s] = e;           //(3)
        size = s + 1;                 //(4)
    }
复制代码

• (1) 判断当前下标是否超出当前数组的最大长度。
• (2) 如果超出最大长度则对数组进行扩容
• (3) 进行赋值
• (4) 长度 + 1

/**
     * 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
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,             // （1）
                                           newCapacity(minCapacity));
    }
    
    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;              
        int newCapacity = oldCapacity + (oldCapacity >> 1);       // （2）
        if (newCapacity - minCapacity <= 0) {                     // （3）
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)                // (4)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
复制代码

• (1) 使用 Arrays 提供的 copyOf 进行扩容，变成一个更大的 数组
• (2) 容量为当前数组长度加上当前数组长度的 右移一位 ( 除以 2 )
• (3) 对初始设置数组长度太小的情况进行兼容
• (4) 对于一些长度特别大的数组进行兼容

自动改变长度

在这里我们以删除一个元素为例。

理论

当我们执行删除操作时将该下标元素后面所有元素前移，并删除最后多出来的一个元素。即可实现删除时自动改变其长度。

实践

打开我（ ArrayList ）的源码，里面有一个 delete 方法详细的讲述了该过程。为了简洁我们截取了片段代码。

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        Objects.checkIndex(index, size);  // (1)
        final Object[] es = elementData; 

        E oldValue = (E) es[index];        
        fastRemove(es, index);           //  (2)

        return oldValue;
    }
复制代码

• (1) 检查下标是否存在
• (2) 删除该元素

  /**
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)                       // （1）
            System.arraycopy(es, i + 1, es, i, newSize - i); //（2）
        es[size = newSize] = null;                          // （3）
    }
复制代码

• (1) 判断是否是最后一个元素
• (2) 调用 Native 方法将该 index 后面的所有元素前移（ 通过复制覆盖 ）
• (3) 删除最后一个元素

在指定位置添加一个新元素和删除类似，只不过是先将该位置后所有元素复制后移。然后在将需要添加的值赋值给指定位置。

结束语

经过我的自我介绍，相信大家对我已经有了深入的了解。并且已经知道我是如何实现的动态数组。在接下来的文章里，我将会为大家介绍我的兄弟姐妹 LinkedList — 基于链表的实现。

参考

• JDK8 官方文档：Oracle

• 数据结构之——数组 ：DobbyKim