Arraylist集合实现以及代码解读

原理

主要把插入后的元素向后移动一位

package 集合框架.Arraylist;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.Queue;

/**
 * 如果传入参数执行有参构造方法，进行判断如果intsize等于0 那么说明数组为空数组 如果大于0 那么此时初始为指定数组长度的数组,
 * 添加元素 ，执行ensureCapacityInternal(1),那么判断为空数组，然后进行选取最大容量默认为10，如果添加11个元素那么就选取为11，，
 * 扩容判断是否溢出了数组进行一个扩容操作默认容量10减去数组容量0，为true进行扩容，执行grow()  获取数组长度为0，那么扩容1.5
 * 数组容量小于默认容量进行扩容 数组容量等于 默认容量
 */
public class ArrayListTest<E> {
    private static final int DEFAULT_SIZE = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private int size;
    transient Object[] elementData;
    /**
     * Integer.MAX_VALUE:
     * 表示int类型最大值：（2^32-1）
     * JVM对数组长度有一个隐式的最大限制Integer.MAx_vALUE
     * 如果数组长度等于Integer.Max_VALUE,会导致内部计算错误或溢出问题
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //构造函数
    public ArrayListTest(int initSize) {
        if (initSize > 0) {
            this.elementData = new Object[initSize];
        } else if (initSize == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            new IllegalArgumentException("非法容量" + initSize);
        }
    }

    //无参构造函数
    public ArrayListTest() {
        this.elementData = EMPTY_ELEMENTDATA;
    }

    //   将元素添加数组末尾
    public boolean add(E e) {
        //容纳指定量元素(更改临时变量)
        ensureCapacityInternal(size + 1);
        //在ArrayList末尾添加元素
        elementData[size++] = e;
        return true;
    }

    //    指定索引，添加元素，对add进行重载
    public void add(int index, E element) {
        //检查索引越界
        rangeCheckForAdd(index);
        //确保容量足够
        ensureCapacityInternal(size + 1);
        //第一个参数为开始复制的源数组，第二个参数表示源数组中要复制的起始位置，即需要将 index 及其后面的元素向后移动一位，第三个参数为表示要复制到的目标数组，即 ArrayList 中的元素数组。，第四个参数为表示目标数组中复制的起始位置，即将 index 及其后面的元素向后移动一位后
        //第5个参数表示要复制的元素个数
        /**
         * 原理 就是如果此时数组元素为 1，2，3，4 ，我需要插入索引1的位置插入5那么，需要将2，3，4移动后面就是索引加1，然后告诉复制的元素个数2，3，4 个数减去索引4-1等于3
         */
       //重要部分数组
        /**
         *
         */
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

    public void rangeCheckForAdd(int index) {
        //如果你指定的索引大于数组长度或者小于0，就抛出越界异常给个提示给出索引index和数组长度size
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index);
        }
    }

    public String outOfBoundsMsg(int index) {
        return "索引越界!!" + "索引为：" + index + "，数组长度：" + size;
    }

    public void ensureCapacityInternal(int minCapacity) {
        //如果数组为空数组
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_SIZE, minCapacity);
        }
        //确保容量可以容纳指定元素
        ensureExplicitCapacity(minCapacity);
    }

    //检查集合容量是否足够，不够增加容量
    private void ensureExplicitCapacity(int minCapacity) {
        //检查超出数组范围，确保不会溢出
        if (minCapacity - elementData.length > 0)
//          超过数组默认范围10就需要扩容
            grow(minCapacity);
    }

    /**
     * 确保容量指定元素容量
     *
     * @param minCapacity 指定容量最小值
     */
    public void grow(int minCapacity) {
        int oldCapcity = elementData.length;
        //在老数组基础上扩容1.5倍
        int newCapcity = oldCapcity + (oldCapcity >> 1);
        //如果还是小于指定最小容量，就给它扩容到最小容量
        if (newCapcity - minCapacity < 0)
            newCapcity = minCapacity;
        //如果超过数组最大长度，就给它扩容到最大长度
        if (newCapcity - MAX_ARRAY_SIZE > 0)
            newCapcity = hugeCapacity(minCapacity);
        //将当前数组赋值到一个新数组
        elementData = Arrays.copyOf(elementData, newCapcity);
    }

    private static int hugeCapacity(int minCapacity) {
        //如果最小容量小于0，抛出内存溢出错误
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    public static String toString(Object[] a) {
        if (a == null) {
            return "null";
        }
        int maxIndex = a.length - 1;
        //如果数组为空数组
        if (maxIndex == -1) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < a.length; i++) {
            sb.append(a[i]);
            if (i == maxIndex) {
                sb.append("]");
            }
            sb.append(", ");
        }
        return sb.toString();
    }
  //更新Arraylist集合元素
    public E set(int index,E element){
      //检查索引越界
        rangeCheckForAdd(index);
       //获取原来指定位置元素
        E oldValue = (E) elementData[index];
        //更新指定位置元素
        elementData[index] = element;
        return oldValue;
    }
    //移除元素
    public E remove(int index){
        //检查索引越界
        rangeCheckForAdd(index);
        //获取指定位置元素
        E oldValue = (E) elementData[index];
        //将指定位置元素设置为null
        elementData[index] = null;
        //将指定位置元素后面的元素向前移动一位
        //重要部分
        System.arraycopy(elementData,index+1,elementData,index,size-index-1);
        //元素数量减一
        size--;
        return oldValue;
    }
    public static void main(String[] args) {

        ArrayListTest<Integer> list = new ArrayListTest<>(5);
        list.add(1);
        list.add(2);
        System.out.println(list.set(0, 3));
        System.out.println(ArrayListTest.toString(list.elementData));

    }
}