首页 💻 数据结构,🔴 Java

ArrayList

成员变量

private int size;    // 实际元素个数
transient Object[] elementData;    // 数据域
private static final int DEFAULT_CAPACITY = 10;    // 默认数据域容量大小
private static final Object[] EMPTY_ELEMENTDATA = {};    // 用于有参构造函数
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    // 用于无参构造函数

构造方法

1. 无参构造方法
/*源码的注释说的是构造一个初始容量为10的空列表, 但其实构造函数只给 elementData 赋值了一个空的数组, 
其实是在第一次添加元素时容量扩大至 10 的*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2. 有参构造方法
/* initialCapacity 就相当于要初始化的数据域容量大小, 如果大于0就初始化一个 initialCapacity 大小的数组
并赋值给 elementData ; 如果等于0则将上边定义的空数组赋值给 elementData ; 如果小于0则抛出异常*/
public ArrayList(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);
    }
}
3. 指定 Collection 来构造 ArrayList
/*将 Collection 转化为数组并赋值给 elementData , 把 elementData 中元素的个数赋值给 size; 如果 size 
不为零, 则判断 elementData 的 class 类型是否为 Object[], 不是的话则做一次转换; 如果 size 为零, 
则把 EMPTY_ELEMENTDATA 赋值给 elementData, 相当于new ArrayList(0)*/
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

主要操作方法

1. add操作
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

在列表的最后添加元素, 每次添加元素到集合中时都会先确认下集合容量大小, 然后将 size 自增1; 当然, 如果 minCapacity 大于 elementData 的长度时候则会触发扩容, 下面来看一下 grow 函数

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

将大小扩充到原来的1.5倍, 但是扩容之后的大小也有可能过大或者过小, 当过小时: 直接拿所需的最小容量来扩容; 当过大时, 拿 Integer.MAX_VALUE 或者 MAX_ARRAY_SIZE 来扩容, 然后将原数组中的数据复制到大小为 newCapacity 的新数组中, 并将新数组赋值给 elementData , 时间复杂度是O(n)

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

该方法是在指定索引添加元素, 首先判断索引合法性, 如果合法则将该位置之后的所有元素右移(从后往前执行), 然后将该值插入, 时间复杂度O(n)

2. remove操作
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

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;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

remove(int index) 方法为删除指定下标的元素, 先进行下标合法性判断, 合法则进行数组移位操作(从前往后执行)将该下标对象删除, 最后将最后一位赋值 null 并让 size-1; remove(Object o) 方法为删除于指定对象相对应的元素, 从前往后遍历数组, 如果找到则删除该元素, 并将其后元素都前移一位, 这里时间复杂的都是O(n)的

3. get操作
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

既然ArrayList内部是数组实现, 那么get方法就是先检查索引合法性, 然后返回该索引对应的元素即可, 时间复杂的O(1)


总结

ArrayList 内部使用数组实现, 是一个支持快速随机访问, 但插入删除速度很慢的数据结构, 所以在我们使用的时候, 应该先估计下应该用到的大小, 不要开始初始化赋值的太小, 这样在插入扩容的时候会很浪费时间的。




文章评论