ArrayList

package com.lius.javase.demo.collection;
import java.util.Arrays;
import java.util.Objects;
/**
 * 手撸 ArrayList
 */
public class MyArrayList {
    private Object[] elementData; // 存放元素的数组
    private int size; // 元素个数
    private static final Object[] EMPTY_ELEMENT_DATA = {}; // 空数组
    private static final int DEFAULT_LENGTH = 10; // 默认长度为10
    public MyArrayList() {
        this.elementData = EMPTY_ELEMENT_DATA;
    }
    public MyArrayList(int length) {
        if(length > 0) {
            this.elementData = new Object[length];
        } else if(length == 0) {
            this.elementData = EMPTY_ELEMENT_DATA;
        } else {
            throw new IllegalArgumentException("集合长度不能为负数");
        }
    }
    public int size() {
        return this.size;
    }
    public boolean add(Object object) {
        int minCapacity; // 最小容量
        if(elementData == EMPTY_ELEMENT_DATA) {
            minCapacity = DEFAULT_LENGTH; // 初始为10
        } else {
            minCapacity = size + 1; // 需要至少 size+1 个桶
        }
        if(minCapacity > elementData.length) {
            // 需要进行扩容
            grow(minCapacity);
        }
        elementData[size++] = object;
        return true;
    }
    /**
     * 扩容
     * @param minCapacity   最小容量
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 新容量的大小: 源码中是 oldCapacity + (oldCapacity >> 1), 其结果一致, 只不过移位速度快
        int newCapacity = oldCapacity + (oldCapacity / 2);
        if(minCapacity > newCapacity) {
            newCapacity = minCapacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    public boolean remove(Object object) {
        // 注意: 空和非空时的比较  要区分开
        if(object == null) {
            for(int index = 0; index < this.size; index++) {
                if(this.elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
            }
        } else {
            for(int index = 0; index < this.size; index++) {
                if(Objects.equals(object, elementData[index])) {
                    fastRemove(index);
                    return true;
                }
            }
        }
        return false;
    }
    public Object remove(int index) {
        if(index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("数组越界:" + index);
        } else {
            Object oldObject = elementData[index];
            int numRemoved = size - index - 1;
            System.arraycopy(elementData, index+1, elementData, index, numRemoved);
            elementData[--size] = null;
            return oldObject;
        }
    }
    /**
     * System.arraycopy(this.elementData, index+1, this.elementData, index, numMoved);
     * 将指定源数组中的数组从指定位置复制到目标数组的指定位置。
     *
     * public static void arraycopy(
     *                  Object src,     要复制的数组(源数组)
     *                  int srcPos,     复制源数组的起始位置
     *                  Object dest,    目标数组
     *                  int destPos,    目标数组的下标位置
     *                  int length);    要复制的长度
     */
    private void fastRemove(int index) {
        int numMoved = this.size - index - 1; // 需要移动的个数
        if(numMoved > 0) {
            System.arraycopy(this.elementData, index+1, this.elementData, index, numMoved);
        }
        elementData[--size] = null; // 删除完之后, 都会前移一个, 把原来的最后一个置为空
    }
    public void print() {
        for(int i=0; i<size; i++) {
            System.out.println(elementData[i]);
        }
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public boolean contains(Object object) {
        return indexOf(object) >= 0;
    }
    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;
    }
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    public Object get(int index) {
        if(index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("数组越界:" + index);
        }
        return elementData[index];
    }
    public Object set(int index, Object object) {
        if(index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("数组越界:" + index);
        }
        Object oldValue = elementData[index];
        elementData[index] = object;
        return oldValue;
    }
    public void clear() {
        for (int i=0; i<size; i++) {
            elementData[i] = null;
        }
        size = 0;
    }
}