ArrayList

1. 概述2. 类3. 属性4. 方法构造方法add()add(index)remove()removeAll()retainAll()batchRemove()indexOf()get(int)set(int, E)

1. 概述

ArrayList 是 List 的一个实现, 其底层使用数组来存储元素, 且支持数组动态扩容

因为底层使用数组, 所以 ArrayList 的查找较快, 增加和删除较慢。

2. 类

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ...... }

继承实现关系图

继承 AbstractList 抽象类 说明其是一个List，且实现了List相关的方法。

实现 RandomAccess 接口 RandomAccess 是一个标记接口, 用来标记支持快速访问的类。RandomAccess 接口主要用在 Collections 工具类上, Collections 中的一些静态方法在操作集合遍历元素时, 如果该集合实现了RandomAccess 接口则使用 for 循环遍历, 如果没有则使用迭代器遍历。

实现 Clone 接口 实现了clone（）方法。

实现 Serializable 接口 标记接口，表明 ArrayList 可以被序列化，并且加入了 serialVersionUID 字段标识版本。

实现 List 接口 AbstractList 已经实现了 List 接口，此处却又实现了一次是因为，如果不这样做的话在使用代理时会报异常，具体参考附录链接。

3. 属性

// 序列化版本号 private static final long serialVersionUID = 8683452581122892189L; // 默认容量 private static final int DEFAULT_CAPACITY = 10; // 空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 默认容量空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 元素数组 transient Object[] elementData; // 集合的元素个数, 不一定等于elementData.length private int size;

4. 方法

构造方法

构造方法共有三个

无参构造 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

该方法将默认的空数组赋给 elementData , 在调用 add 方法时会为其分配一个默认长度为10的数组。

可分配初始数组大小的有参构造 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); } } 参数为Collection集合的构造方法 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // toArray() 方法有可能不会返回Object[]对象 if (elementData.getClass() != Object[].class) // 使用Native方法 Arrays.copy（） elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 数组长度为0，为其分配空数组 this.elementData = EMPTY_ELEMENTDATA; } }

add()

public boolean add(E e) { // 确保数组容量够用, size是元素个数 ensureCapacityInternal(size + 1); // Increments modCount!! // 将元素加在末尾 elementData[size++] = e; return true; }

进入 ensureCapacityInternal (int minCapacity)

private void ensureCapacityInternal(int minCapacity) { // 通过 calculateCapacity 计算容量, 默认容量则返回10, 否则返回minCapacity, 在当做参数传递, ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }

进入ensureExplicitCapacity(int minCapacity)

private void ensureExplicitCapacity(int minCapacity) { modCount++; // 需要的容量大于元素数组的长度则调用grow(minCapacity)方法进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }

进入grow(int minCapacity)

private void grow(int minCapacity) { int oldCapacity = elementData.length; // 新容量为旧容量的1.5倍, >> 向右移位运算, 相当于 / 2 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新容量还是小于最小需要的容量 if (newCapacity - minCapacity < 0) // 那么直接将需要的容量作为新容量 newCapacity = minCapacity; // 如果新容量大于了数组大小的最大值, 那么就将最大值赋给它 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 调用 Native 方法进行数组拷贝 elementData = Arrays.copyOf(elementData, newCapacity); // 扩容完成, 返回add方法添加元素 }

add(index)

public void add(int index, E element) { // 范围检查 index要在 0 到 size 之间, 否则抛出异常 rangeCheckForAdd(index); // 同上add()方法一样, 确保数组大小够用, 不够扩容 ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

remove()

public E remove(int index) { // 检查index 在 0 到 size 之间 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; }

remove(Object)

public boolean remove(Object o) { // 判空处理, 防止空指针异常 if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { // index后的元素向前移动 同 remove(int)中的逻辑 fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) // 对象的话调用equals() if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }

removeAll()

public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); }

retainAll()

public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); }

batchRemove()

removeAll() 和 retainAll() 的逻辑类似, 所以都同一由同一个方法batchRemove()实现, 只是在传参的时候, removeAll() 传 false表示不保留相同的元素, retainAll()传true表示只保留相同的元素

private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { // 遍历 elementData for (; r < size; r++) // complement 为 false 表示 c 不包含的复制保存, c 包含的不复制 true 则相反 if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // 如果 contains 方法抛异常, 则执行finally, r != size 表示还没复制完成 if (r != size) { // 继续复制剩下的元素 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // 发生了删除, 元素数量变少, 需要把末尾的重复对象引用释放掉, 以便GC回收 if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; // 更新size大小 size = w; modified = true; } } return modified; }

indexOf()

public int indexOf(Object o) { // 判空, 防止equals空指针 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; }

get(int)

public E get(int index) { rangeCheck(index); return elementData(index); }

set(int, E)

public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }

elementData(int)

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