zy19982004--容器学习七：ArrayList源码分析

一.成员变量

// 在AbstractList里面定义的
protected transient int modCount = 0;

// 内部用数组实现
private transient Object[] elementData;

private int size;

 

二.构造函数

// 自己在写代码的时候为了严谨，最好是先判断参数抛出IllegalArgumentException
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "
                + initialCapacity);
    this.elementData = new Object[initialCapacity];
}

// 初始化容量10
public ArrayList() {
    this(10);
}

 

 三.存数据

//增加数据
public boolean add(E e) {
    //1.保证容量，size+1和容量比较，看是否有位置插入e
    ensureCapacity(size + 1); // Increments modCount!!
    //2.直接赋值
    elementData[size++] = e;
    return true;
}

//在指定位置增加数据
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
                + size);
    //1.保证容量
    ensureCapacity(size + 1); // Increments modCount!!
    //2.向右移动当前位于该位置的元素（如果有）以及所有后续元素（将其索引加 1）。
    System.arraycopy(elementData, index, elementData, index + 1, size
            - index);
    //3.将指定的元素插入此列表中的指定位置
    elementData[index] = element;
    size++;
}

// 检查容量，minCapacity=size+1
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    // 如果超过容量
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        // 新容量=(老容量 * 3)/2 + 1
        // 如果老容量为10，则新容量为16
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        //newCapacity < minCapacity会产生这样的情况？？？？？
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        //复制原数组数据到大小为newCapacity的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

//替换数据
public E set(int index, E element) {
    RangeCheck(index);
    //保存index处旧值
    E oldValue = (E) elementData[index];
    //赋新值
    elementData[index] = element;
    return oldValue;
}
//下标志检查
private void RangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
                + size);
}

 

四.取数据

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

// 返回第一次出现o的下标，用equals比较
// 如果不存在o，返回-1
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i] == null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

// 想想为什么不这么实现
// 上面的实现方式比较次数2+n，下面的比较次数2*n
public int indexOf(Object o) {
    for (int i = 0; i < size; i++) {
        if (o == null) {
            if (elementData[i] == null)
                return i;
        } else {
            if (o.equals(elementData[i]))
                return i;
        }
    }
    return -1;
}

// 从size-1往0遍历
public int lastIndexOf(Object o) {
    if (o == 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 (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

 

五.删数据

//移除index处的元素是List接口里新加的方法
//同Map一样，在插入元素的操作中会扩容，删除元素并不去减容
public E remove(int index) {
    RangeCheck(index);

    modCount++;
    E oldValue = (E) elementData[index];
    //需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //数组内（间）元素移动，五个参数依次为
        //src - 源数组。
        //srcPos - 源数组中的起始位置。
        //dest - 目标数组。
        //destPos - 目标数据中的起始位置。
        //length - 要复制的数组元素的数量。
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    //让GC回收因移动空出的数组最后一位
    elementData[--size] = null;

    return oldValue;
}

//remove某个元素是Collection接口里的方法
//同Map一样，在插入元素的操作中会扩容，删除元素并不去减容
//remove(int index)和remove(Object o)一次只会移除一个元素
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

//把index后的元素移往前移一位
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    //让GC回收因移动空出的数组最后一位
    elementData[--size] = null;
}

 

六.List与Array

//ArrayList转换成数组
//将ArrayList内部的数组0到size-1位返回即可
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

//ArrayList转换成指定数组a
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}