[Java知识库]每日一类-手写ArrayList

概述? ? ? ??

????????ArrayList是开发中用得相对频繁的一个类，以前侧重业务，在意使用，今天来尝试还原一下ArrayList源码设计，自己DIY一个自己的ArrayList。

????????ArrayList定位为动态数组，底层是一个可以自动扩容的数组，用于存储同类型的数据。那么自己DIY的ArrayList就必须满足这些功能操作，结合ArrayList源码，确定手写的MyArraylist的方法有下面几个：??

?构造器

public class App {
    public static void main(String[] args) {
        //使用默认的容积
        ArrayList list = new ArrayList();
        //使用指定容积
        ArrayList list2 = new ArrayList(10);
        //根据传入的集合创建新集合
        ArrayList list3 = new ArrayList(Collections.emptyList());
    }
}

上面代码是JDK版ArrayList的构造器，有3个，一个默认数组大小，一个指定数组大小，一个由传入的其他集合决定，结合这个信息，可以自己yy一下，ArrayList里面必定有1个数组，数组通过构造器进行初始化，初始化方式有3种，对应的MyArrayList可以定义成下面的样子。

public class MyArrayList {

    private int size;  //存放数据大小
    private Object[] elementData;  //存放数据数组

    //模仿ArrayList初始化 2个空数组，执行add时才进行扩容
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //为什么弄2个空数组，官方给出解释：
    // We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate 
    //when first element is added.
    //翻译过来就是：我想知道它啥时候塞值进去
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   
}

空参数构造器

默认还是使用空数组，当执行add时在扩容

    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

指定初始化容积构造器

这里3个分支，1>指定初始化值大于0，按照指定大小扩容，如果等于0，默认就是空值，其他情况抛异常

    public MyArrayList(int initialCapacity){
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }

指定集合的构造器

ArrayList中有完整集合体系，可将Collection集合转换成ArrayList元素，而MyArrayList仅仅是模仿，没有继承/实现Collection体系，所以就自己合并自己。

    public MyArrayList(MyArrayList list){
        elementData = list.toArray();
        if ((size = elementData.length) == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

里面涉及到元素的拷贝与合并，多了toArray方法，将集合元素转换成数组

    public Object[] toArray() {
        //借用工具类啦
        return Arrays.copyOf(elementData, size);
    }

添加-add

可变数组(list集合)有2类添加方法，一个还add(element)，一个是add(index, element)

    /**
     * 往数组中添加元素(默认添加到最后)
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(Object element) {
        return false;
    }

    /**
     * 往数组指定位置添加元素(默认添加到最后)
     * @param index 索引
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(int index, Object element) {
        return false;
    }

不过哪一个add方法，都需要考虑一下几个问题：

1>第一次添加时，数组初始化

2>添加的数据超过初始化(默认/指定)长度时，数组如何扩容

add(element)?

    //默认长度
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 往数组中添加元素(默认添加到最后)
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(Object element) {
        if(size == elementData.length){
            this.grow();
        }
        elementData[size++] = element;
        return true;
    }
    //拓展方法
    private void grow() {
        int oldCapacity = elementData.length; //新长度
        int newCapacity;
        if(oldCapacity == 0){
            newCapacity = DEFAULT_CAPACITY;
        }else{
            //扩展增幅是 1.5倍
            newCapacity = oldCapacity + (oldCapacity >> 1);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

第一次添加时需要对数组进行初始化(默认初始化数组长度为10)，当添加数据个数超过数组长度时，也需要拓展，那么统一使用grow方法进行数据拓展。是否拓展，判定标准就是

size == elementData.length

add(index, element)

与add(element)存在不同,add(index, element) 多了index索引校验跟数据移动，

比如下面例子：

?list.add(3, 444)，索引为3， 4， 5位置需要往后挪一位，将所以为3位位置空出来，将444值设置到索引为3的位置。

    /**
     * 往数组指定位置添加元素(默认添加到最后)
     * @param index 索引
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(int index, Object element) {
        //检查索引是否正确
        this.rangeCheck(index);
        if(size == elementData.length){
            this.grow();
        }
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
        return true;
    }

    //检查索引是否正确
    private void rangeCheck(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }

这里解析一下：arraycopy方法

System.arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

src：源数组

srcPos：源开始拷贝索引

dest：目标数组

destPos：目标数组开始替换位置

length：拷贝长度

按上面的例子， list.add(3, 444), 则表示，将源数组索引为3， 4， 5索引位置的数据拷贝目标数组(跟源数组一样)索引为4， 5， 6索引位置。

System.arraycopy(elementData, 3, elementData, 3+ 1, 6- 3);

优化：

add(element)? 跟 add(index, element)? 存在一定代码重复， add(element）等价于add(size, element), 所以可以调用实现。

    /**
     * 往数组中添加元素(默认添加到最后)
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(Object element) {
        this.add(size, element);
        return true;
    }

    /**
     * 往数组指定位置添加元素(默认添加到最后)
     * @param index 索引
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(int index, Object element) {
        //检查索引是否正确
        this.rangeCheck(index);
        if(size == elementData.length){
            this.grow();
        }
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
        return true;
    }

删除-remove/clear

remove操作有2中，一种是根据内容删除， 一种是根据索引删除。根据内容删除这个相对麻烦，需要引入泛型，这里暂时放弃，重点来弄根据索引删除：

remove(index)

    /**
     * 根据指定索引删除数据
     * @param index 索引
     * @return 被删除的数据
     */
    public Object remove(int index){
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        Object old  = elementData[index];
        if(size - 1 > index){
            System.arraycopy(elementData, index + 1, elementData, index, size -1 - index);
        }
        elementData[size-1] = null;
        size --;
        return old;
    }

clear

清除， 将所有数据清空

    /**
     * 清空集合元素
     */
    public void clear() {
        for (int i = 0; i < size; i++){
            elementData[i] = null;
        }
        size = 0;
    }

修改-set

list集合的set操作，set(index, element), 因为没有涉及到数据个数变化，操作起来相对简单。

    /**
     * 修改指定位置元素数据
     * @param index 索引
     * @param element 元素
     * @return 返回被改动的数据
     */
    public Object set(int index, Object element) {
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        Object oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    }

查询-get

get(index), 这个操作也相对简单

    /**
     * 获取指定索引的数据
     * @param index 索引
     * @return 数据
     */
    public Object get(int index) {
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        return elementData[index];
    }

到这，一个很初级的ArrayList就出现啦。最终代码：

public class MyArrayList {

    private int size;  //存放数据大小
    private Object[] elementData;  //存放数据数组

    //默认长度
    private static final int DEFAULT_CAPACITY = 10;


    //模仿ArrayList初始化 2个空数组，执行add时才进行扩容
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //为什么弄2个空数组，官方给出解释：
    // We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate
    //when first element is added.
    //翻译过来就是：我想知道它啥时候塞值进去
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public MyArrayList(int initialCapacity){
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }


    public MyArrayList(MyArrayList list){
        elementData = list.toArray();
        if ((size = elementData.length) == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    public Object[] toArray() {
        //借用工具类啦
        return Arrays.copyOf(elementData, size);
    }


    /**
     * 往数组中添加元素(默认添加到最后)
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(Object element) {
        this.add(size, element);
        return true;
    }
    //拓展方法
    private void grow() {
        int oldCapacity = elementData.length; //新长度
        int newCapacity;
        if(oldCapacity == 0){
            newCapacity = DEFAULT_CAPACITY;
        }else{
            //扩展增幅是 1.5倍
            newCapacity = oldCapacity + (oldCapacity >> 1);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 往数组指定位置添加元素(默认添加到最后)
     * @param index 索引
     * @param element 元素
     * @return 添加成功返回true， 不成功返回false
     */
    public boolean add(int index, Object element) {
        //检查索引是否正确
        this.rangeCheck(index);
        if(size == elementData.length){
            this.grow();
        }
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
        return true;
    }

    //检查索引是否正确
    private void rangeCheck(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }


    /**
     * 根据指定索引删除数据
     * @param index 索引
     * @return 被删除的数据
     */
    public Object remove(int index){
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        Object old  = elementData[index];
        if(size - 1 > index){
            System.arraycopy(elementData, index + 1, elementData, index, size -1 - index);
        }
        elementData[size-1] = null;
        size --;
        return old;
    }
    /**
     * 清空集合元素
     */
    public void clear() {
        for (int i = 0; i < size; i++){
            elementData[i] = null;
        }
        size = 0;
    }


    /**
     * 修改指定位置元素数据
     * @param index 索引
     * @param element 元素
     * @return 返回被改动的数据
     */
    public Object set(int index, Object element) {
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        Object oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    }

    /**
     * 获取指定索引的数据
     * @param index 索引
     * @return 数据
     */
    public Object get(int index) {
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        return elementData[index];
    }
    @Override
    public String toString() {
        return "MyArrayList{" +
                "size=" + size +
                ", elementData=" + Arrays.toString(elementData) +
                '}';
    }
}