0 - 1 构建属于自己的ArrayList

ArrayList介绍

我们先来看在java1.8api官方文档（谷歌翻译版）上对于ArrayList类的介绍

可调整大小的数组的实现List接口。 实现所有可选列表操作，并允许所有元素，包括null 。 除了实现List 接口之外，该类还提供了一些方法来操纵内部使用的存储列表的数组的大小。 （这个类是大致相当于Vector，不同之处在于它是不同步的）。

该size，isEmpty，get，set，iterator和listIterator操作在固定时间内运行。 add操作以摊余常数运行 ，即添加n个元素需要O（n）个时间。 所有其他操作都以线性时间运行（粗略地说）。 与LinkedList实施相比，常数因子较低。

每个ArrayList实例都有一个容量 。 容量是用于存储列表中的元素的数组的大小。 它总是至少与列表大小一样大。 当元素添加到ArrayList时，其容量会自动增长。 没有规定增长政策的细节，除了添加元素具有不变的摊销时间成本。

应用程序可以添加大量使用ensureCapacity操作元件的前增大ArrayList实例的容量。 这可能会减少增量重新分配的数量。

请注意，此实现不同步。

简单来说，ArrayList就是一个可变长的数组结构，并且提供了很多功能强大的内置方法。

ArrayList定义

通过以上定义并结合1.8api文档，我整理出构建ArrayList框架部分成员变量以及内置方法

@Data
public class Mini_ArrayList<E> {

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    // 实际存放元素数组
    private Object[] elementData;
    // Mini_ArrayList容量
    private int size;

    /**
     * Mini_ArrayList无参构造器
     */
    public Mini_ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    /**
     * Mini_ArrayList有参构造器
     * @param initialCapacity 传入初始容量
     */
    public Mini_ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = new Object[DEFAULT_CAPACITY];
        } else {
            throw new IllegalArgumentException("传参不合法~" + initialCapacity);
        }
    }

    /**
     * 将元素追加到此列表的末尾
     *
     * @param element 待添加元素
     * @return 是否添加成功
     */
    public boolean add(E element) {
        return true;
    }

    /**
     * 在指定索引位置处添加指定元素
     *
     * @param index 指定索引值
     * @param element 待添加元素
     * @return 是否添加成功
     */
    public boolean add(int index, E element) {
        return true;
    }

    /**
     * 移除指定索引位置上的元素
     *
     * @param index 索引值
     * @return 移除元素值
     */
    public E remove(int index) {
        return null;
    }

    /**
     * 移除列表中指定元素
     *
     * @param object 待移除元素
     * @return 是否移除成功
     */
    public boolean remove(Object object) {
        return true;
    }

    /**
     * 删除列表中所有元素
     */
    public void clear() {
    }

    /**
     * 判断列表中是否存在指定元素
     *
     * @param object 待判断元素
     * @return 是否存在
     */
    public boolean contains(Object object) {
        return true;
    }

    /**
     * 返回指定元素在列表中首次出现的索引值
     *
     * @param object 指定元素
     * @return 返回索引值
     */
    public int indexOf(Object object) {
        return 0;
    }

    /**
     * 返回指定元素在列表中最后出现的索引值
     *
     * @param object 指定元素
     * @return 返回索引值
     */
    public int lastIndexOf(Object object) {
        return 0;
    }

    /**
     * 获取指定索引位置处的元素
     *
     * @param index 指定索引值
     * @return 返回元素值
     */
    public E get(int index) {
        return null;
    }

    /**
     * 将指定索引位置上的值设置为指定元素
     *
     * @param index 指定索引值
     * @param element 指定元素
     * @return 返回设置前指定索引位置上元素值
     */
    public E set(int index, E element) {
        return null;
    }

    /**
     * 返回列表中的元素个数
     *
     * @return 列表元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 判断列表是否为空
     *
     * @return 列表是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

}

方法细节

接下来让我们来看看各个方法的实现细节吧

开始之前，我们先做一系列约定条件

• add方法越界检查

    // 判断索引是否合规
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException("参数不合规~");
        }
    }

• 其它方法越界检查

    // 判断索引是否合规
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("参数不合规~");
        }
    }

• 扩容条件：当前元素个数 + 1 已经大于列表容量
• 扩容大小：扩容为原来的 1.5 倍

    /**
     * 判断是否需要扩容
     */
    private void ensureCapacityInternal() {
        // 扩容条件：当前元素个数 + 1 已经大于列表容量
        boolean isOverCapacity = size + 1 > elementData.length;
        if (isOverCapacity) {
            // 需要扩容
            // 记录原列表
            int oldCapacity = elementData.length;
            // 扩容为原来的 1.5 倍
            int newCapacity = oldCapacity + ((oldCapacity / 2) > 1 ? (oldCapacity / 2) : 1);
            // 判断是否超过Integer.MAX_VALUE
            newCapacity = newCapacity <= Integer.MAX_VALUE ? newCapacity : Integer.MAX_VALUE;
            // 借用 Arrays.copyOf 方法完成扩容
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

说明：Mini_ArrayList省去了一些细节，例如在判断扩容条件时默认了 size + 1，后续扩容操作源码中是有分支判断逻辑的，本类中不涉及批量添加元素的操作所以给省去了。要想更加深入学习ArrayList扩容机制，还需去官方源码中探究~

再来看一个底层常用方法的使用

System.arraycopy

// 从指定数组的指定索引位置copy到目标数组的指定索引位置，长度为length

public static native void arraycopy(

    Object src,  // 原数组
    int  srcPos, // 原数组起始copy索引处
    Object dest, // 目标数组
    int destPos, // 目标数组起始copy索引处
    int length // copy 长度

); 

    @Test
    public void systemCopy() {
        int[] arr1 = new int[]{1, 2, 3, 4, 5, 0, 0, 0};
        int[] arr2 = new int[]{5, 6, 7, 0, 0, 0, 0};
        System.arraycopy(arr1, 1, arr2, 1, 4);
        System.out.println(Arrays.toString(arr2));
    }

我们来看这个测试案例

从arr1 索引 1 处开始复制元素到 arr2 索引 1 处，length 为 4

返回结果：[5, 2, 3, 4, 5, 0, 0]  

前置条件说完，下面来正式介绍各个方法的实现细节

    /**
     * 将元素追加到此列表的末尾
     *
     * @param element 待添加元素
     * @return 是否添加成功
     */
    public boolean add(E element) {

        // 判断是否需要扩容
        ensureCapacityInternal();
        elementData[size++] = element;

        return true;
    }

    /**
     * 在指定索引位置处添加指定元素
     *
     * @param index 指定索引值
     * @param element 待添加元素
     * @return 是否添加成功
     */
    public boolean add(int index, E element) {

        // 参数检查
        rangeCheckForAdd(index);
        // 判断是否需要扩容
        ensureCapacityInternal();
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;

        return true;
    }

    /**
     * 移除指定索引位置上的元素
     *
     * @param index 索引值
     * @return 移除元素值
     */
    public E remove(int index) {

        // 参数检查
        rangeCheck(index);
        // 拿到移除元素值
        E oldValue = (E) elementData[index];
        // 移除思路：将元素移动到列表尾端后置空
        int moveCount = size - index - 1;
        if (moveCount > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, moveCount);
        }
        elementData[--size] = null;

        return oldValue;
    }

    /**
     * 移除列表中指定元素
     *
     * @param object 待移除元素
     * @return 是否移除成功
     */
    public boolean remove(Object object) {

        // 判断待删除元素是否为 null
        if (object == null) {
            for(int index = 0; index < size; index++) {
                if (elementData[index] == null) {
                    // 和删除元素一致
                    int moveCount = size - index - 1;
                    if (moveCount > 0) {
                        System.arraycopy(elementData, index + 1, elementData, index, moveCount);
                    }
                    elementData[--size] = null;
                    return true;
                }
            }
        } else {
            for(int index = 0; index < size; index++) {
                if (object.equals(elementData[index])) {
                    // 和删除元素一致
                    int moveCount = size - index - 1;
                    if (moveCount > 0) {
                        System.arraycopy(elementData, index + 1, elementData, index, moveCount);
                    }
                    elementData[--size] = null;
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * 返回指定元素在列表中首次出现的索引值
     *
     * @param object 指定元素
     * @return 返回索引值 -1 为不存在
     */
    public int indexOf(Object object) {

        if (object == null) {
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (object.equals(elementData[i])) {
                    return i;
                }
            }
        }

        return -1;
    }

    /**
     * 返回指定元素在列表中最后出现的索引值
     *
     * @param object 指定元素
     * @return 返回索引值 -1 为不存在
     */
    public int lastIndexOf(Object object) {

        if (object == null) {
            for (int i = size - 1; i >= 0; i--) {
                if (elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = size - 1; i >= 0; i--) {
                if (object.equals(elementData[i])) {
                    return i;
                }
            }
        }

        return -1;
    }

    /**
     * 判断列表中是否存在指定元素
     *
     * @param object 待判断元素
     * @return 是否存在
     */
    public boolean contains(Object object) {
        return indexOf(object) >= 0;
    }

    /**
     * 获取指定索引位置处的元素
     *
     * @param index 指定索引值
     * @return 返回元素值
     */
    public E get(int index) {

        rangeCheck(index);

        return (E) elementData[index];
    }

    /**
     * 将指定索引位置上的值设置为指定元素
     *
     * @param index 指定索引值
     * @param element 指定元素
     * @return 返回设置前指定索引位置上元素值
     */
    public E set(int index, E element) {

        rangeCheck(index);
        E oldValue = (E) elementData[index];
        elementData[index] = element;

        return oldValue;
    }

    /**
     * 返回列表中的元素个数
     *
     * @return 列表元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 判断列表是否为空
     *
     * @return 列表是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 删除列表中所有元素
     */
    public void clear() {

        // 将列表所有元素都置空
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }
        size = 0;
    }

综上来看，ArrayList核心是理解并灵活运用System.arraycopy方法。

值得一提的是，源码中原扩容代码是

int newCapacity = oldCapacity + (oldCapacity >> 1);

可能会有小伙伴不理解 ">>" 运算符的作用，故我改为常规运算符计算。加上三元运算符是因为防止用有参构造器创建对象时传参为 1 导致的不扩容现象。

当 oldCapacity = 1 时

int newCapacity = 1+ (1 / 2) = 1

测试案例

    @Test
    public void systemCopy() {
        int[] arr1 = new int[]{1, 2, 3, 4, 5, 0, 0, 0};
        int[] arr2 = new int[]{5, 6, 7, 0, 0, 0, 0};
        System.arraycopy(arr1, 1, arr2, 1, 4);
        System.out.println(Arrays.toString(arr2));
        // [5, 2, 3, 4, 5, 0, 0]
    }

    @Test
    public void add() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("hello");
        list.add("world");
        System.out.println(Arrays.toString(list.getElementData()));
        // [hello, world, null, null, null, null, null, null, null, null]
    }

    @Test
    public void testAdd() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("world");
        list.add(1, "hello");
        System.out.println(Arrays.toString(list.getElementData()));
        // [world, hello, null, null, null, null, null, null, null, null]
    }

    @Test
    public void remove() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("world");
        list.add(1, "hello");
        list.remove(1);
        System.out.println(Arrays.toString(list.getElementData()));
        // [world, null, null, null, null, null, null, null, null, null]
    }

    @Test
    public void testRemove() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("world");
        list.add(1, "hello");
        String removeElement = list.remove(1);
        System.out.println("删除元素：" + removeElement);
        System.out.println(Arrays.toString(list.getElementData()));
        // 删除元素：hello
        // [world, null, null, null, null, null, null, null, null, null]
    }

    @Test
    public void clear() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("world");
        list.add(1, "hello");
        list.clear();
        System.out.println(Arrays.toString(list.getElementData()));
        // [null, null, null, null, null, null, null, null, null, null]
    }

    @Test
    public void indexOf() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("中国");
        list.add("你好");
        list.add("中国");
        int China = list.indexOf("中国");
        System.out.println("取到元素，index:" + China);
        // 取到元素，index:0
    }

    @Test
    public void lastIndexOf() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("你好");
        list.add("world");
        list.add("hello");
        list.add("你好");
        list.add("中国");
        int hello = list.lastIndexOf("你好");
        System.out.println("取到元素，index:" + hello);
        // 取到元素，index:3
    }

    @Test
    public void contains() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("world");
        list.add("hello");
        list.add("你好");
        list.add("中国");
        if (list.contains("你好")) {
            System.out.println("存在...");
        } else {
            System.out.println("不存在...");
        }
        // 存在...
    }

    @Test
    public void get() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("你好");
        list.add("world");
        list.add("hello");
        list.add("你好");
        list.add("中国");
        String element = list.get(2);
        System.out.println("元素值：" + element);
        // 元素值：hello
    }

    @Test
    public void set() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("你好");
        list.add("world");
        list.add("apple");
        list.add("pear");
        System.out.println(Arrays.toString(list.getElementData()));
        list.set(1, "tea");
        System.out.println(Arrays.toString(list.getElementData()));
        // [你好, world, apple, pear, null, null, null, null, null, null]
        // [你好, tea, apple, pear, null, null, null, null, null, null]
    }

    @Test
    public void size() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("你好");
        list.add("world");
        list.add("apple");
        list.add("pear");
        System.out.println("元素个数：" + list.size());
        // 元素个数：4
    }

    @Test
    public void isEmpty() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>();
        list.add("你好");
        list.add("world");
        System.out.println("是否空:" + list.isEmpty());
        list.clear();
        System.out.println("是否空:" + list.isEmpty());
        // 是否空:false
        // 是否空:true
    }

    @Test
    public void testEnlarge() {
        Mini_ArrayList<String> list = new Mini_ArrayList<>(1);
        for (int i = 0; i < 20; i++) {
            list.add("hello" + (i + 1));
        }
        System.out.println(Arrays.toString(list.getElementData()));
        System.out.println(list.size());
        System.out.println(list.getElementData().length);
        // [hello1, hello2, hello3, hello4, hello5, hello6, hello7, hello8, hello9, hello10,
        // hello11, hello12, hello13, hello14, hello15, hello16, hello17, hello18, hello19,
        // hello20, null, null, null, null, null, null, null, null]
        // 20
        // 28
    }

总结

我知道Mini_ArrayList中还存在很多不足和隐藏的bug，大家可在评论区留言建议，作者看到后定会答复并积极处理，同时也希望大家能够动手来实现一个属于自己丰富多彩的ArrayList。