几个要点
- ArrayList非线程安全;
- ArrayList基于动态数组，是一种线性表。随机访问友好,其可以保证在 O(1) 复杂度下完成随机查找操作，插入和删除效率低;
- ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；
- 容量动态调节，有一套扩容和优化空间的机制,ArrayList 允许空值和重复元素，当往 ArrayList 中添加的元素数量大于其底层数组容量时，其会通过扩容机制重新生成一个更大的数组;
- ArrayList继承了AbstractList，实现了List、RandomAccess、Cloneable、Serializable接口;
- ArrayList扩容的长度是原长度的1.5倍;
- 删除和插入需要复制数组，性能差（可以使用LinkindList替代），ArrayList适合读多写少的场景；
定义
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
成员属性
//默认初始化容量 private static final int DEFAULT_CAPACITY = 10; //默认的空的数组，这个主要是在构造方法初始化一个空数组的时候使用 private static final Object[] EMPTY_ELEMENTDATA = {}; //使用默认size大小的空数组实例，和EMPTY_ELEMENTDATA区分开来， //这样可以知道当第一个元素添加的时候进行扩容至多少 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList底层存储数据就是通过数组的形式，ArrayList长度就是数组的长度。 //一个空的实例elementData为上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当添加第一个元素的时候 //会进行扩容，扩容大小就是上面的默认容量DEFAULT_CAPACITY transient Object[] elementData; // non-private to simplify nested class access //arrayList的大小 private int size; // 数组最大长度 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造方法
无参构造函数
如果不传入参数，则使用默认无参构建方法创建ArrayList对象，如下：
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
注意：此时我们创建的ArrayList对象中的elementData中的长度是1，size是0,当进行第一次add的时候，elementData将会变成默认的长度：10.
带int类型的构造函数
如果传入参数，则代表指定ArrayList的初始数组长度，传入参数如果是大于等于0，则使用用户的参数初始化，如果用户传入的参数小于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); }
包含集合，把collection对象的内容（可以理解为深拷贝）copy到elementData中
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; } }
扩容
每次扩0.5倍进新容量newCapacity
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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
add
/** 在元素序列尾部插入 */ public boolean add(E e) { // 1. 检测是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! // 2. 将新元素插入序列尾部 elementData[size++] = e; return true; }
add主要的执行逻辑如下：
1）确保数组已使用长度（size）加1之后足够存下 下一个数据
2）修改次数modCount 标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组，grow方法会将当前数组的长度变为原来容量的1.5倍。
3）确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
4）返回添加成功布尔值。
/** 在元素序列 index 位置处插入 */ public void add(int index, E element) { rangeCheckForAdd(index); // 1. 检测是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! // 2. 将 index 及其之后的所有元素都向后移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 3. 将新元素插入至 index 处 elementData[index] = element; size++; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
remove
public E remove(int index) { rangeCheck(index); //校验下标是否合法（如果index>size，旧抛出IndexOutOfBoundsException异常） modCount++;//修改list结构，就需要更新这个值 E oldValue = elementData(index); //直接在数组中查找这个值 int numMoved = size - index - 1;//这里计算所需要移动的数目 //如果这个值大于0 说明后续有元素需要左移(size=index+1) //如果是0说明被移除的对象就是最后一位元素(不需要移动别的元素) if (numMoved > 0) //索引index只有的所有元素左移一位 覆盖掉index位置上的元素 System.arraycopy(elementData, index+1, elementData, index, numMoved); //移动之后，原数组中size位置null elementData[--size] = null; // clear to let GC do its work //返回旧值 return oldValue; } //src:源数组 //srcPos:从源数组的srcPos位置处开始移动 //dest:目标数组 //desPos:源数组的srcPos位置处开始移动的元素，这些元素从目标数组的desPos处开始填充 //length:移动源数组的长度 public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); //私有删除方法，不进行边界检查，不返回被删除元素 private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) //native方法，速度比for和clone都"fast" System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; } //删除[fromIndex,toIndex)的元素 protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex;//要移动的数量 System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // 删除后，list 的长度 int newSize = size - (toIndex-fromIndex); //将失效元素置空 for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } //移除c集合中的元素 public boolean removeAll(Collection<?> c) { //判断集合是否为空，否则抛出NPE Objects.requireNonNull(c); return batchRemove(c, false); } //保留c集合中的元素 public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); }
get
public E get(int index) { rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); } //顺序找，返回首先出现的位置，找不到返-1。O(n) 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; } //逆序找，返回最后出现的位置，找不到返-1。O(n) 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; } //顺序找实现，根据返回值判断 public boolean contains(Object o) { return indexOf(o) >= 0; }
遍历的4种方法
ArrayList<String> list = new ArrayList<String>(); list.add("a"); list.add("b"); list.add("c"); 方式1 Iterator<String> it = strList.iterator(); while (it.hasNext()) { System.out.println(it.next()); } 方式2 for (int i = 0; i < list.size(); i++) { list.get(i); } 方式3 for(String tmp:list){ System.out.println(tmp); } 方式4 Consumer<String> consumer = (a) -> System.out.println(a); list.forEach(consumer);