不想看源码解析的同学,可以直接去最下方查看答案
List是最简单的线性数据结构,Java在最上层提供了List接口,然后通过AbstractList实现了List接口。
ArrayList和LinkedList是Java中最常用的List实现类。
ArrayList底层是由数组实现的,相当于动态数组。LinkedList底层相当于链表的实现方式。
下面我们开始分析源码
/** * 默认初始化的数组大小 */ 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<? extends E> 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 < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } /** * 增加ArrayList的capacity,确保elementData的容量最少能支持 * minCapacity * * @param minCapacity 需要的最小容量 */ public void ensureCapacity(int minCapacity) { // 1. 如果ArrayList不是通过默认构造方式构造的,或者 // ArrayList中已经添加过元素了,则minExpand为0, // 2. 如果ArrayList是通过默认构造方式构造的,且从未 // 添加过任何元素,那么minExpand就为默认的初始化 // 容量DEFAULT_CAPACITY(10) int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > 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 = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 对elementData进行扩容,然后将elementData原有的内容, // 复制到扩容后的数组中 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; } 复制代码
/** * 添加元素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的末尾。 * <p> * 在遍历集合c的过程中,如果对c进行了修改,那么会产生未定义的现象。 */ public boolean addAll(Collection<? extends E> 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<? extends E> 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对应 * 下标右边的元素全部向左移动一位。 * <p> * 如果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 < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /** * 快速删除index对应的元素,不需要进行范围检查,因为调用该方法时 * 已经可以保证index绝对有效 */ 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 } /** * 清空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 < size; i++) if (o.equals(elementData[i])) return i; } return -1; } /** * 返回list中最后一次出现给定元素o的下标,如果不存在元素o * 则返回-1 */ public int lastIndexOf(Object o) { // 与indexOf实现方式相同,只是把遍历的方向 // 改为从后向前遍历 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的元素 */ @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<? super E> 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<E> { 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<? super E> 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<E> { 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 < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; 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<E> extends AbstractList<E> implements List<E>, 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> 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; } /** * 检查index是否超出限制,需要检查index的原因是当list动态扩容时,会分配出 * 未使用的空间,访问时并不会报错。而size记录了当前真实使用的空间,所以 * 需要将index与size比较。 * <p> * 不检查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 < 0 的情况 if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size; } } 复制代码
// 待定 复制代码
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<Node> srcList = new ArrayList<>(); srcList.add(new Node()); srcList.add(new Node()); for (Node node : srcList) { System.out.println("srcList: " + node); } /* --------------------- 浅复制 --------------------- */ System.out.println("浅复制"); // 循环遍历 List<Node> destList1 = new ArrayList<>(); srcList.forEach(src -> destList1.add(src)); System.out.println("循环遍历"); for (Node node : destList1) { System.out.println("descList: " + node); } // 构造方法 List<Node> destList2 = new ArrayList<>(srcList); System.out.println("构造方法"); for (Node node : destList2) { System.out.println("descList: " + node); } // addAll方法 List<Node> destList3 = new ArrayList<>(); destList3.addAll(srcList); System.out.println("addAll方法"); for (Node node : destList3) { System.out.println("descList: " + node); } // clone方法 List<Node> destList4 = (List<Node>) 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<Node> destList5 = (List<Node>) srcList.clone(); System.out.println("改造后的clone方法"); for (Node node : destList5) { System.out.println("descList: " + node.clone()); } } 复制代码
返回结果
srcList: Node@71bc1ae4 srcList: Node@6ed3ef1 ---------- 浅复制 ---------- 循环遍历 descList: Node@71bc1ae4 descList: Node@6ed3ef1 构造方法 descList: Node@71bc1ae4 descList: Node@6ed3ef1 addAll方法 descList: Node@71bc1ae4 descList: Node@6ed3ef1 clone方法 descList: Node@71bc1ae4 descList: Node@6ed3ef1 System.arraycopy方法 descList: Node@71bc1ae4 descList: Node@6ed3ef1 ---------- 深复制 ---------- 改造后的clone方法 descList: Node@17d99928 descList: 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<Integer> list = new ArrayList<>(); list.add(1); list.add(1); list.add(2); list.add(2); list.add(3); list.add(3); List<Integer> 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<Integer> 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 复制代码