手写ArrayList源码

jdk API数组拷贝

Arrays.copyOf(objects, size);
System.arraycopy(src, srcPos, dest, destPos, length);
src：源数组
srcPos：原数组起始位置
dest：目标数组
destPos：目标数组起始位置
length：复制长度

注意点

1.ArrayList底层采用该数组实现，数组名称为elementData
2.ArrayList默认大小为10；
3.如果ArrayList构造器中指定初始化大小为1;初次位移扩容始终为1，新容量大小以最小容量为主

        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;

4.删除原理：使用System.arraycopy方法，往前移动数组，将最后一个元素设置为空
5.Arrays.asList返回的不是ArrayList，而是Arrays的私有静态内部类，它与ArrayList区别是没有实现Cloneable接口，其它一致，它没有实现添加方法，所以不能添加元素

Vector与ArrayList

1.vector线程安全，方法使用synchronize修饰，效率比ArrayList差
2.Vector和ArrayList都采用连续的存储空间，当存储空间不足的时候，vector默认增加为原来的一倍，ArrayList默认正价为原来的50%
3.Vector可以设置capacityIncrement(容量增长参数)，而ArrayList不可以设置

  public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

  //vector 扩容方式（注意:扩容参数）
  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

手写ArrayList代码

  public class ExtArrayList<E> implements ExtList<E>{
    
    //ArrayList底层采用数组存放
    private Object[] elementData;
    //默认数组容量
    private static final int DEFAULT_CAPACITY = 10;
    //记录实际ArrayList大小
    private int size;
    
    
    //默认初始化容量为10
    public ExtArrayList() {
        this(DEFAULT_CAPACITY);
    }
    
    //ArryList指定数组初始的容量
    public ExtArrayList(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("初始化容量不能小于0");
        }
        elementData = new Object[initialCapacity];
    }
    
    public void add(E e) {
        //1.判断实际存放的数据容量是否大于elementData
        ensureCapacityInternal(size + 1);
        //2.使用下标进行赋值
        elementData[size++] = e; 
    }
    
    public void add(int index, E e) {
        rangeCheck(index);
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = e;
        size ++; 
    }
    
    // int minCapacity 当前 size + 1
    private void ensureCapacityInternal(int minCapacity) {
        if (size == elementData.length) {
//          //新数组容量大小
//          int newCapacity = 2 * size;
//          Object[] newObjects = new Object[newCapacity];
            //新旧数组复制
//          for (int i = 0; i < elementData.length; i++) {
//              newObjects[i] = elementData[i];
//          }
//          elementData = newObjects;
            //新旧数组复制
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //最小扩容容量；防止初始容量大小为1
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
    
    //使用下标获取数组元素
    public Object get(int index) {
        return elementData[index];
    }
    
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
    
    public Object remove(int index) {
        rangeCheck(index);
        //1.使用下标查询该值是否存在
        Object object = get(index);
        //计算删除元素后面的长度
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            //2.删除原理分析
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        //将最后一个元素变为空
        elementData[--size] = null;
        return object;
    }
    
    // 删除相同元素 删除第一个
    public boolean remove(E e) {
        for (int i = 0; i < elementData.length; i++) {
            Object value = elementData[i];
            if (value.equals(e)) {
                remove(i);
                return true;
            }
        }
        return false;
    }
    
    //判断下标是否越界
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("越界啦!");
    }
    
    public int getSize() {
        return size;
    }

}