- ArrayList的大小是如何自动增加的
- 什么情况下你会使用ArrayList？什么时候你会选择LinkedList？
- 如何复制某个ArrayList到另一个ArrayList中去
- 在索引中ArrayList的增加或者删除某个对象的运行过程？效率很低吗？解释一下为什么？
- ArrayList插入删除一定慢么？
- ArrayList的遍历和LinkedList遍历性能比较如何？
- ArrayList是线程安全的么？
- ArrayList如何remove
不想看源码解析的同学，可以直接去最下方查看答案
源码解析
List是最简单的线性数据结构，Java在最上层提供了List接口，然后通过AbstractList实现了List接口。
ArrayList和LinkedList是Java中最常用的List实现类。
ArrayList底层是由数组实现的，相当于动态数组。LinkedList底层相当于链表的实现方式。
下面我们开始分析源码
ArrayList
底层数据结构
/** * 默认初始化的数组大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 所有ArrayList实例共享的空list实例 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA区分，标识 * elementData数组是通过默认构造方法创建的空数组，并且还没有向其中添加 * 元素 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 底层用来真实存储数据的数组，在调用ArrayList默认构造方法时，该数组会被 * 赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。直到第一次向数组中添加元素时， * 会被扩容为DEFAULT_CAPACITY */ transient Object[] elementData; /** * 数组中元素的数量 */ private int size; /** * 可以分配的最大数组大小。某些VM在数组中保留一些header words。 * 尝试分配更大的数组可能会导致OutOfMemoryError */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;复制代码构造方法
/** * 通过给定的初始容量创建一个空list */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 如果指定的容量大于0，就新建一个数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // 如果指定的容量等于0，那么就是一个空数组 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } } /** * 不指定初始容量，创建一个容量为10的空数组 */ public ArrayList() { // 使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA标识elementData数组 // 是通过默认构造方法创建的，在第一向ArrayList添加元素时，会进行 // 扩容，而扩充的容量为DEFAULT_CAPACITY(10) this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 创建一个ArrayList，包含给定集合c中的所有元素，顺序即为c迭代器遍历的顺序。 * * @throws NullPointerException 如果c为null，抛出NPE */ public ArrayList(Collection c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // 如果给定集合c的size不为0 // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) // c.toArray()并不一定返回Object[]类型，如果返回的不是 // Object[]类型，就调用Arrays的复制方法变为Object类型 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 如果给定集合c的size为0，那么就构造一个空数组 this.elementData = EMPTY_ELEMENTDATA; } }复制代码动态扩容
/** * 修剪elementData多余的槽，使ArrayList的capacity修剪为当前的size */ public void trimToSize() { modCount++; if (size minExpand) { // 如果需要扩容 ensureExplicitCapacity(minCapacity); } } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * @param minCapacity 需要的最小容量 */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // newCapacity = 1.5 * oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity 0) newCapacity = hugeCapacity(minCapacity); // 对elementData进行扩容，然后将elementData原有的内容， // 复制到扩容后的数组中 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }复制代码插入/替换
/** * 添加元素e到list尾部 */ public boolean add(E e) { // 检查是否需要扩容，并将modCount + 1 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } /** * 在指定index插入元素element，并将原先在index位置及右方元素向右移动一位 */ public void add(int index, E element) { // 检查index是否有效 rangeCheckForAdd(index); // 检查是否需要扩容，并将modCount + 1 ensureCapacityInternal(size + 1); // 把index及index右面的元素全部向右移动一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } /** * 将给定的集合c中的所有元素按照c迭代器的顺序添加到list的末尾。 * * 在遍历集合c的过程中，如果对c进行了修改，那么会产生未定义的现象。 */ public boolean addAll(Collection c) { Object[] a = c.toArray(); int numNew = a.length; // 扩容，并修改modCount ensureCapacityInternal(size + numNew); // 将数组a复制到数组elementData尾部 System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } /** * 将给定的集合c中的所有元素按照c迭代器的顺序添加到list的index位置。 * 并把index及index之后的元素的位置向后移动n个位置，n为集合c的大小。 */ public boolean addAll(int index, Collection c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; // 扩容并修改modCount ensureCapacityInternal(size + numNew); int numMoved = size - index; if (numMoved > 0) // 如果index小于size，即为在之前的元素中间插入，所以要把index及之后的 // 元素向右移动numNew位 System.arraycopy(elementData, index, elementData, index + numNew, numMoved); // 将数组a的元素，复制到elementData数组中 System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; } /** * 用element替换下标为index的元素，并返回之前的元素 */ public E set(int index, E element) { // 检查index是否超过限制 rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }复制代码
删除
/** * 删除指定下标的元素，并将该下标右边的元素全部向左移动一位 */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) // 将index+1及之后的元素全部向左移动一位 System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null; return oldValue; } /** * 如果list中包含一个或多个元素o，那么删除第一个o(下标最小的)，并将第一个o对应 * 下标右边的元素全部向左移动一位。 * * 如果list中不包含元素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 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } /** * 清空elementData中的所有元素的引用 */ public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) // 帮助GC elementData[i] = null; size = 0; } /** * 移除下标在 [fromIndex, toIndex) 之间的元素，并将toIndex和之后 * 的元素全部向左移动至fromIndex的位置 */ protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; // 将toIndex和之后的元素向左移动至fromIndex的位置 System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // 计算新的数组的大小 int newSize = size - (toIndex - fromIndex); // 将多余的元素引用置为null，帮助GC for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } /** * 从list中删除指定集合c中包含的所有元素。 */ public boolean removeAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, false); } /** * 保留在list中且在指定集合c中包含的所有元素 */ public boolean retainAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, true); } /** * @param complement false-remove，true-retain */ private boolean batchRemove(Collection c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { // 双指针遍历list for (; r < size; r++) // c.contains(elementData[r])判断给定集合c中是否存 // 在r指针对应的元素。 // 如果complement为false，代表remove集合c中的元素。 // 如果complement为true，代表retain集合c中的元素。 if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // 如果c.contains抛出异常，仍能保证与AbstractCollection相同的兼容性 if (r != size) { // 如果r指针没有遍历完数组，就把r指针未遍历的元素，复制到r指针 // 之后，因为r指针-w指针之间的元素应该被移除 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // 清空不用的元素引用，帮助GC for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }复制代码
遍历
/** * 返回list中第一次出现给定元素o的下标，如果不存在元素o * 则返回-1 */ public int indexOf(Object o) { // 将o为null和非null的情况分开做处理 if (o == null) { for (int i = 0; i < size; i++) if (elementData[i] == null) return i; } else { for (int i = 0; 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的元素 */ @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } /** * 返回下标为index的元素 */ public E get(int index) { // 检查index是否超过限制 rangeCheck(index); return elementData(index); } @Override public void forEach(Consumer action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData; final int size = this.size; // forEach的内部实现其实就是遍历内部elementData数组， // 然后对每个元素进行action.accept操作。 // 遍历过程中要比较modCount是否发生变化，如果发生了变化， // 会抛出ConcurrentModificationException，快速失败 for (int i = 0; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }复制代码迭代器
private class Itr implements Iterator { int cursor; // 下一个要访问的元素的下标 int lastRet = -1; // 上一次访问的元素的下标，如果没有则为-1 int expectedModCount = modCount; // 是否包含下一个元素 public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; // 如果要访问的下标大于最大长度，则抛出异常 if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); // cursor后移 cursor = i + 1; // 返回下标为i的元素，并将lastRet置为i return (E) elementData[lastRet = i]; } public void remove() { // 如果上一个访问的元素不存在，则抛出异常 if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { // 删除上一个访问的元素 ArrayList.this.remove(lastRet); // 重置下标 cursor = lastRet; // 因为上一个访问的元素已经删除了，所以不存在了 // 要把lastRet置为-1 lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } // 防止并发冲突 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } /** * 在Iterator的基础上，支持了双向遍历 */ private class ListItr extends Itr implements ListIterator { ListItr(int index) { super(); cursor = index; } public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } /** * 与Iterator的next方法一样，只不过改成了向前遍历 */ @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i = elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; // 向list添加元素后，上一次访问的元素就发生了变化， // 所以要将lastRet置为-1 lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }复制代码其他
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * 返回ArrayList的浅拷贝 */ public Object clone() { try { ArrayList v = (ArrayList) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } } /** * 以数组的形式返回list中的所有元素 */ public Object[] toArray() { return Arrays.copyOf(elementData, size); } /** * 以数组的形式返回list中的所有元素, 数组的类型为T */ @SuppressWarnings("unchecked") public T[] toArray(T[] a) { if (a.length size) a[size] = null; return a; } /** * 检查index是否超出限制，需要检查index的原因是当list动态扩容时，会分配出 * 未使用的空间，访问时并不会报错。而size记录了当前真实使用的空间，所以 * 需要将index与size比较。 * * 不检查index为负的情况，因为当index为负时，访问数组会抛出ArrayIndexOutOfBoundsException */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * add and addAll 时检查是否index是否有效 */ private void rangeCheckForAdd(int index) { // 与rangeCheck版本不同，这里index是可以等于size的，因为size的值 // 就是下一个要插入的下标值，所以index==size就相当于在list尾插入 // // 不知道为什么这里还判断了index size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size; }}复制代码
LinkedList
// 待定复制代码
面试题解答
ArrayList的大小是如何自动增加的
当调用ArrayList的add, addAll等方法时，会调用ensureCapacityInternal方法检查底层数组容量是否满足所需容量，如果容量不够大，就调用grow方法将容量扩展至原来的1.5倍(一般情况下)
什么情况下你会使用ArrayList？什么时候你会选择LinkedList？
待定
如何复制某个ArrayList到另一个ArrayList中去
public class Node implements Cloneable { public Node() {} public Object clone() { Node node = null; try { node = (Node) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return node; }}public static void main(String[] args) { ArrayList srcList = new ArrayList(); srcList.add(new Node()); srcList.add(new Node()); for (Node node : srcList) { System.out.println("srcList: " + node); } /* --------------------- 浅复制 --------------------- */ System.out.println("浅复制"); // 循环遍历 List destList1 = new ArrayList(); srcList.forEach(src -> destList1.add(src)); System.out.println("循环遍历"); for (Node node : destList1) { System.out.println("descList: " + node); } // 构造方法 List destList2 = new ArrayList(srcList); System.out.println("构造方法"); for (Node node : destList2) { System.out.println("descList: " + node); } // addAll方法 List destList3 = new ArrayList(); destList3.addAll(srcList); System.out.println("addAll方法"); for (Node node : destList3) { System.out.println("descList: " + node); } // clone方法 List destList4 = (List) srcList.clone(); System.out.println("clone方法"); for (Node node : destList4) { System.out.println("descList: " + node); } // System.arraycopy Node[] destArray = new Node[srcList.size()]; System.arraycopy(srcList.toArray(), 0, destArray, 0, srcList.size()); System.out.println("System.arraycopy方法"); for (Node node : destArray) { System.out.println("descList: " + node); } /* --------------------- 深复制 --------------------- */ System.out.println("深复制"); // 改造后的clone方法 List destList5 = (List) srcList.clone(); System.out.println("改造后的clone方法"); for (Node node : destList5) { System.out.println("descList: " + node.clone()); }}复制代码返回结果
srcList: Node@71bc1ae4srcList: Node@6ed3ef1---------- 浅复制 ---------- 循环遍历descList: Node@71bc1ae4descList: Node@6ed3ef1构造方法descList: Node@71bc1ae4descList: Node@6ed3ef1addAll方法descList: Node@71bc1ae4descList: Node@6ed3ef1clone方法descList: Node@71bc1ae4descList: Node@6ed3ef1System.arraycopy方法descList: Node@71bc1ae4descList: Node@6ed3ef1---------- 深复制 ---------- 改造后的clone方法descList: Node@17d99928descList: Node@3834d63f复制代码
ArrayList插入/删除一定慢吗
取决于插入与删除的位置
插入：在插入过程中会将index及之后的元素向后移动，如果插入的位置是数组靠后的位置。那么要移动的元素并不多，通过index直接访问的，操作并不会很慢。
删除：与插入相同，插入过程中会将index及之后的元素向前移动，如果位置靠后，移动的元素也不多。
ArrayList的遍历和LinkedList遍历性能比较如何？
待定
ArrayList是线程安全的么？
不是。对ArrayList的操作并没有做任何同步或者加锁的行为。可以看到对ArrayList的结构性操作中，都会对modCount值进行修改。这样在操作时，通过比较modCount可以实现fail-fast机制，在并发冲突时，抛出ConcurrentModificationException
ArrayList如何remove
public static void main(String[] args) { List list = new ArrayList(); list.add(1); list.add(1); list.add(2); list.add(2); list.add(3); list.add(3); List list2 = new ArrayList(list); for (int i = 0; i < list2.size(); i++) { if ((list2.get(i) % 2) == 0) { list2.remove(i); } } System.out.println(list2); // [1, 1, 2, 3, 3] list2 = new ArrayList(list); Iterator iterator = list2.iterator(); while (iterator.hasNext()) { if ((iterator.next() % 2) == 0) { iterator.remove(); } } System.out.println(list2); // [1, 1, 3, 3] list2 = new ArrayList(list); for (Integer data : list2) { // ConcurrentModificationException if ((data % 2) == 0) { list2.remove(data); } } System.out.println(list2); }复制代码通过遍历下标的方式删除(×)：
这种方式是错误的，有可能会遗漏元素。比如数组中的元素为[1, 1, 2, 2, 3, 3]，当下标index为2时，对应的元素为第一个[2]，满足条件删除后，数组中的元素变为[1, 1, 2, 3, 3]，因为[2]被删除后，之后的[2, 3, 3]向左移动。在遍历中，index++ 变为3，对应的元素为[3]，所以数组中第二个[2]被遗漏了，没有遍历到。
通过迭代器进行迭代(√)：
这种方式是删除的正确方式
在forEach中进行删除(×)：
这种方式是错误的，会抛出ConcurrentModificationException。原因在于ArrayList中的forEach方法：
final int expectedModCount = modCount; 在整个遍历之前会先记录modCount。复制代码
在调用ArrayList的remove方法时，会通过modCount++对modCount值进行修改， 这时modCount与遍历前记录的modCount已经不一致了。复制代码
for (int i = 0; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } 遍历每个元素时，会检查modCount是否与之前一致。而在remove方法中， 已经进行了修改，所以在删除元素后的下次遍历时会退出循环。复制代码if (modCount != expectedModCount) { throw new ConcurrentModificationException(); }如果modCount与之前不一致了，就抛出ConcurrentModificationException复制代码