/** * 元素数组。 * * 当添加新的元素时，如果该数组不够，会创建新数组，并将原数组的元素拷贝到新数组。之后，将该变量指向新数组。 * * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access 不使用 private 修饰，方便内嵌类的访问。
/** * 已使用的数组大小 * * The size of the ArrayList (the number of elements it contains). * * @serial */ privateint size;
/** * 共享的空数组对象，用于 {@link #ArrayList()} 构造方法。 * * 通过使用该静态变量，和 {@link #EMPTY_ELEMENTDATA} 区分开来，在第一次添加元素时。 * * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ privatestaticfinal Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * Constructs an empty list with an initial capacity of ten. */ publicArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
publicbooleanaddAll(int index, Collection<? extends E> c) { // 校验位置是否在数组范围内 rangeCheckForAdd(index);
// 转成 a 数组 Object[] a = c.toArray(); // 增加数组修改次数 modCount++; // 如果 a 数组大小为 0 ，返回 ArrayList 数组无变化 intnumNew= a.length; if (numNew == 0) returnfalse; // 如果 elementData 剩余的空间不够，则进行扩容。要求扩容的大小，至于能够装下 a 数组。 Object[] elementData; finalint s; if (numNew > (elementData = this.elementData).length - (s = size)) elementData = grow(s + numNew);
// 【差异点】如果 index 开始的位置已经被占用，将它们后移 intnumMoved= s - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
// 将 a 复制到 elementData 从 s 开始位置 System.arraycopy(a, 0, elementData, index, numNew); // 数组大小加 numNew size = s + numNew; returntrue; }
<X> 处，调用 #shiftTailOverGap(Object[] es, int lo, int hi) 方法，移除 [fromIndex, toIndex) 的多个元素。代码如下：
1 2 3 4 5 6 7 8 9
// ArrayList.java
privatevoidshiftTailOverGap(Object[] es, int lo, int hi) { // 将 es 从 hi 位置开始的元素，移到 lo 位置开始。 System.arraycopy(es, hi, es, lo, size - hi); // 将从 [size - hi + lo, size) 的元素置空，因为已经被挪到前面了。 for (intto= size, i = (size -= hi - lo); i < to; i++) es[i] = null; }
和 #fastRemove(Object[] es, int i) 方法一样的套路，先挪后置 null 。
有一点要注意，ArrayList 特别喜欢把多行代码写成一行。所以，可能疑惑，貌似这里没有修改数组的大小 size 啊？答案在 i = (size -= hi - lo) ，简直到精简到难懂。
#removeAll(Collection<?> c) 方法，批量移除指定的多个元素。简单来说，通过两个变量 w（写入位置）和 r（读取位置），按照 r 顺序遍历数组(elementData)，如果不存在于指定的多个元素中，则写入到 elementData 的 w 位置，然后 w 位置 + 1 ，跳到下一个写入位置。通过这样的方式，实现将不存在 elementData 覆盖写到 w 位置。代码如下：
1 2 3 4 5
// ArrayList.java
publicbooleanremoveAll(Collection<?> c) { return batchRemove(c, false, 0, size); }
调用 #batchRemove(Collection<?> c, boolean complement, final int from, final int end) 方法，批量移除指定的多个元素。代码如下：
intindexOfRange(Object o, int start, int end) { Object[] es = elementData; // o 为 null 的情况 if (o == null) { for (inti= start; i < end; i++) { if (es[i] == null) { return i; } } // o 非 null 的情况 } else { for (inti= start; i < end; i++) { if (o.equals(es[i])) { return i; } } } // 找不到，返回 -1 return -1; }
intlastIndexOfRange(Object o, int start, int end) { Object[] es = elementData; // o 为 null 的情况 if (o == null) { for (inti= end - 1; i >= start; i--) { // 倒序 if (es[i] == null) { return i; } } // o 非 null 的情况 } else { for (inti= end - 1; i >= start; i--) { // 倒序 if (o.equals(es[i])) { return i; } } }
// 找不到，返回 -1 return -1; }
11.获得指定位置的元素
#get(int index) 方法，获得指定位置的元素。代码如下：
1 2 3 4 5 6 7 8 9 10 11 12
// ArrayList.java
public E get(int index) { // 校验 index 不要超过 size Objects.checkIndex(index, size); // 获得 index 位置的元素 return elementData(index); }
E elementData(int index) { return (E) elementData[index]; }
随机访问 index 位置的元素，时间复杂度为 O(1) 。
12. 设置指定位置的元素
#set(int index, E element) 方法，设置指定位置的元素。代码如下：
1 2 3 4 5 6 7 8 9 10 11 12
// ArrayList.java
public E set(int index, E element) { // 校验 index 不要超过 size Objects.checkIndex(index, size); // 获得 index 位置的原元素 EoldValue= elementData(index); // 修改 index 位置为新元素 elementData[index] = element; // 返回 index 位置的原元素 return oldValue; }
13.转换成数组
#toArray() 方法，将 ArrayList 转换成 [] 数组。代码如下：
1 2 3 4 5 6 7 8 9 10 11
// ArrayList.java
public Object[] toArray() { return Arrays.copyOf(elementData, size); }
publicbooleanequals(Object o) { // 如果是自己，直接返回相等 if (o == this) { returntrue; }
// 如果不为 List 类型，直接不相等 if (!(o instanceof List)) { returnfalse; }
// 获得当前的数组修改次数 finalintexpectedModCount= modCount; // ArrayList can be subclassed and given arbitrary behavior, but we can // still deal with the common case where o is ArrayList precisely // <X> 根据不同类型，调用不同比对的方法。主要考虑 ArrayList 可以直接使用其 elementData 属性，性能更优。 booleanequal= (o.getClass() == ArrayList.class) ? equalsArrayList((ArrayList<?>) o) : equalsRange((List<?>) o, 0, size);
@java.io.Serial privatevoidwriteObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out element count, and any hidden stuff // 获得当前的数组修改次数 intexpectedModCount= modCount;
if (size > 0) { // like clone(), allocate array based upon size not capacity SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); // 不知道作甚，哈哈哈。 // 创建 elements 数组 Object[] elements = newObject[size];
// Read in all elements in the proper order. // 逐个读取 for (inti=0; i < size; i++) { elements[i] = s.readObject(); }
/** * 下一个访问元素的位置，从下标 0 开始。 */ int cursor; // index of next element to return /** * 上一次访问元素的位置。 * * 1. 初始化为 -1 ，表示无上一个访问的元素 * 2. 遍历到下一个元素时，lastRet 会指向当前元素，而 cursor 会指向下一个元素。这样，如果我们要实现 remove 方法，移除当前元素，就可以实现了。 * 3. 移除元素时，设置为 -1 ，表示最后访问的元素不存在了，都被移除咧。 */ intlastRet= -1; // index of last element returned; -1 if no such /** * 创建迭代器时，数组修改次数。 * * 在迭代过程中，如果数组发生了变化，会抛出 ConcurrentModificationException 异常。 */ intexpectedModCount= modCount;
// prevent creating a synthetic constructor Itr() {}
staticfinalclassArrayListSpliterator<E> implementsSpliterator<E> { privatefinal ArrayList<E> list; privateint index; // current index, modified on advance/split 存储起始下标; privateint fence; // -1 until used; then one past last index 结束下标; privateint expectedModCount; // initialized when fence set 修改次数modCount;
/** Create new spliterator covering the given range */ ArrayListSpliterator(ArrayList<E> list, int origin, int fence, int expectedModCount) { this.list = list; // OK if null unless traversed this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; } .....省略方法
getFence方法
获取fence结束下标。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
privateintgetFence() { // initialize fence to size on first use int hi; // (a specialized variant appears in method forEach) ArrayList<E> lst; //小于0，说明赋值过了，直接返回 if ((hi = fence) < 0) { //空集合，直接赋值0 if ((lst = list) == null) hi = fence = 0; else { //记录修改次数 expectedModCount = lst.modCount; //将集合大小赋值给结束下标 hi = fence = lst.size; } } //返回 return hi; }
trySplit方法
分割list,返回一个新分割的Spilterator实例；相当于二分法，该方法会递归。
>>>: 无符号右移运算符，num >>> 1，相当于num除以2
1 2 3 4 5 6 7 8 9
public ArrayListSpliterator<E> trySplit() { //hi结束下标，lo开始下标，mid：中间位置 inthi= getFence(), lo = index, mid = (lo + hi) >>> 1; //lo >= mid时，表示不能再分割，返回null //lo < mid时，表示可以分割，切割（lo,mid）出去，相当于取list前半部分返回，同时更新index=mid return (lo >= mid) ? null : // divide range in half unless too small newArrayListSpliterator<E>(list, lo, index = mid, expectedModCount); }
publicbooleanremoveIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); // figure out which elements are to be removed // any exception thrown from the filter predicate at this stage // will leave the collection unmodified intremoveCount=0; //记录被删除元素的下标 finalBitSetremoveSet=newBitSet(size); //修改次数 finalintexpectedModCount= modCount; //集合大小 finalintsize=this.size; //遍历把符合条件的待删除的元素下标设置到BitSet中，即BitSet中对应的下标设为true. for (int i=0; modCount == expectedModCount && i < size; i++) { @SuppressWarnings("unchecked") finalEelement= (E) elementData[i]; if (filter.test(element)) { removeSet.set(i); removeCount++; } } //检查是否有其他线程并发修改该ArrayList if (modCount != expectedModCount) { thrownewConcurrentModificationException(); }
// shift surviving elements left over the spaces left by removed elements finalbooleananyToRemove= removeCount > 0; //符合条件的元素>0 if (anyToRemove) { //新的集合大小 finalintnewSize= size - removeCount; //移除相应元素 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { //通过nextClearBit(i) 为返回下一个false位置,即表示下标i是无需移除的元素 i = removeSet.nextClearBit(i); elementData[j] = elementData[i]; } //newSize之后的元素置空 for (int k=newSize; k < size; k++) { elementData[k] = null; // Let gc do its work } this.size = newSize; if (modCount != expectedModCount) { thrownewConcurrentModificationException(); } modCount++; }
// 如果 index 小于 size 的一半，就正序遍历，获得第 index 个节点 if (index < (size >> 1)) { Node<E> x = first; for (inti=0; i < index; i++) x = x.next; return x; // 如果 index 大于 size 的一半，就倒序遍历，获得第 index 个节点 } else { Node<E> x = last; for (inti= size - 1; i > index; i--) x = x.prev; return x; } }
#linkBefore(E e, Node<E> succ) 方法，添加元素 e 到 succ 节点的前面。代码如下：
privatevoidlinkFirst(E e) { // 记录原 first 节点 final Node<E> f = first; // 创建新节点 final Node<E> newNode = newNode<>(null, e, f); // first 指向新节点 first = newNode; // 如果原 first 为空，说明 last 也为空，则 last 也指向新节点 if (f == null) last = newNode; // 如果原 first 非空，说明 last 也非空，则原 first 的 next 指向新节点。 else f.prev = newNode; // 增加链表大小 size++; // 增加数组修改次数 modCount++; }
publicbooleanaddAll(Collection<? extends E> c) { return addAll(size, c); }
publicbooleanaddAll(int index, Collection<? extends E> c) { checkPositionIndex(index);
// <1> 将 c 转成 a 数组 Object[] a = c.toArray(); intnumNew= a.length; if (numNew == 0) // 如果无添加元素，直接返回 false 数组未变更 returnfalse;
// <2> 获得第 index 位置的节点 succ ，和其前一个节点 pred Node<E> pred, succ; if (index == size) { // 如果 index 就是链表大小，那说明插入队尾，所以 succ 为 null ，pred 为 last 。 succ = null; pred = last; } else { // 如果 index 小于链表大小，则 succ 是第 index 个节点，prev 是 succ 的前一个二节点。 succ = node(index); pred = succ.prev; }
// <3> 遍历 a 数组，添加到 pred 的后面 for (Object o : a) { // 创建新节点 @SuppressWarnings("unchecked")Ee= (E) o; Node<E> newNode = newNode<>(pred, e, null); // 如果 pred 为 null ，说明 first 也为 null ，则直接将 first 指向新节点 if (pred == null) first = newNode; // pred 下一个指向新节点 else pred.next = newNode; // 修改 pred 指向新节点 pred = newNode; }
// <4> 修改 succ 和 pred 的指向 if (succ == null) { // 如果 succ 为 null ，说明插入队尾，则直接修改 last 指向最后一个 pred last = pred; } else { // 如果 succ 非 null ，说明插入到 succ 的前面 pred.next = succ; // prev 下一个指向 succ succ.prev = pred; // succes 前一个指向 pred }
E unlink(Node<E> x) { // assert x != null; // <1> 获得 x 的前后节点 prev、next finalEelement= x.item; final Node<E> next = x.next; final Node<E> prev = x.prev;
// <2> 将 prev 的 next 指向下一个节点 if (prev == null) { // <2.1> 如果 prev 为空，说明 first 被移除，则直接将 first 指向 next first = next; } else { // <2.2> 如果 prev 非空 prev.next = next; // prev 的 next 指向 next x.prev = null; // x 的 pre 指向 null }
// <3> 将 next 的 prev 指向上一个节点 if (next == null) { // <3.1> 如果 next 为空，说明 last 被移除，则直接将 last 指向 prev last = prev; } else { // <3.2> 如果 next 非空 next.prev = prev; // next 的 prev 指向 prev x.next = null; // x 的 next 指向 null }
publicbooleanremove(Object o) { if (o == null) { // o 为 null 的情况 // 顺序遍历，找到 null 的元素后，进行移除 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); returntrue; } } } else { // 顺序遍历，找到等于 o 的元素后，进行移除 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); returntrue; } } } returnfalse; }
相比 #remove(int index) 方法来说，需要去寻找首个等于 o 的节点进行移除。当然，最终还是调用 #unlink(Node<E> x) 方法，移除该节点。
publicbooleanremoveLastOccurrence(Object o) { if (o == null) { // o 为 null 的情况 // 倒序遍历，找到 null 的元素后，进行移除 for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); returntrue; } } } else { // 倒序遍历，找到等于 o 的元素后，进行移除 for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); returntrue; } } } returnfalse; }
public E removeFirst() { final Node<E> f = first; // <1> 如果链表为空，抛出 NoSuchElementException 异常 if (f == null) thrownewNoSuchElementException(); // <2> 移除链表时首个元素 return unlinkFirst(f); }
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; finalEelement= f.item; // 获得 f 的下一个节点 final Node<E> next = f.next; // 设置 f 的 item 为 null ，帮助 GC f.item = null; // 设置 f 的 next 为 null ，帮助 GC f.next = null; // help GC // 修改 fisrt 指向 next first = next; // 修改 next 节点的 prev 指向 null if (next == null) // 如果链表只有一个元素，说明被移除后，队列就是空的，则 last 设置为 null last = null; else next.prev = null; // 链表大小减一 size--; // 增加数组修改次数 modCount++; return element; }
<1> 处，如果链表为空，抛出 NoSuchElementException 异常。
<2> 处，移除链表时首个元素。因为 LinkedList 有 first 和 last 头尾节点，所以添加和删除操作，都可能需要小心处理。
public E removeLast() { final Node<E> l = last; // 如果链表为空，则抛出 NoSuchElementException 移除 if (l == null) thrownewNoSuchElementException(); // 移除链表的最后一个元素 return unlinkLast(l); }
private E unlinkLast(Node<E> l) { // assert l == last && l != null; finalEelement= l.item; // 获得 f 的上一个节点 final Node<E> prev = l.prev; // 设置 l 的 item 为 null ，帮助 GC l.item = null; // 设置 l 的 prev 为 null ，帮助 GC l.prev = null; // help GC // 修改 last 指向 prev last = prev; // 修改 prev 节点的 next 指向 null if (prev == null) // 如果链表只有一个元素，说明被移除后，队列就是空的，则 first 设置为 null first = null; else prev.next = null; // 链表大小减一 size--; // 增加数组修改次数 modCount++; return element; }
public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }
public E element() { // 如果链表为空识，抛出 NoSuchElementException 异常 return getFirst(); } public E getFirst() { final Node<E> f = first; if (f == null) // 如果链表为空识，抛出 NoSuchElementException 异常 thrownewNoSuchElementException(); return f.item; }
11.设置指定位置的元素
#set(int index, E element) 方法，设置指定位置的元素。代码如下：
1 2 3 4 5 6 7 8 9 10 11
// LinkedList.java
public E set(int index, E element) { checkElementIndex(index); // 获得第 index 位置的节点 Node<E> x = node(index); EoldVal= x.item; // 修改对应的值 x.item = element; return oldVal; }
12.转换成数组
1.object类型数组
#toArray() 方法，将LinkedList 转换成 [] 数组。代码如下：
1 2 3 4 5 6 7 8 9 10 11
// LinkedList.java
public Object[] toArray() { // 创建 Object 数组 Object[] result = newObject[size]; // 顺序遍历节点，设置到 Object 数组中 inti=0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }
2.指定类型数组
实际场景下，我们可能想要指定 T 泛型的数组，那么我们就需要使用到 #toArray(T[] a) 方法。代码如下：
public <T> T[] toArray(T[] a) { // <1> 如果传入的数组小于 size 大小，则直接复制一个新数组返回 if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); // <2> 顺序遍历链表，复制到 a 中 inti=0; Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item;
publicvoidclear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator // 顺序遍历链表，设置每个节点前后指向为 null // 通过这样的方式，帮助 GC for (Node<E> x = first; x != null; ) { // 获得下一个节点 Node<E> next = x.next; // 设置 x 的 item、next、prev 为空。 x.item = null; x.next = null; x.prev = null; // 设置 x 为下一个节点 x = next; } // 清空 first 和 last 指向 first = last = null; // 设置链表大小为 0 size = 0; // 增加数组修改次数 modCount++; }
public E previous() { // 校验是否数组发生了变化 checkForComodification(); // 如果已经遍历到结尾，抛出 NoSuchElementException 异常 if (!hasPrevious()) thrownewNoSuchElementException();
// 修改 lastReturned 和 next 的指向。此时，lastReturned 和 next 是相等的。 lastReturned = next = (next == null) ? last : next.prev; // 下一个节点的位置 - 1 nextIndex--; // 返回 lastReturned return lastReturned.item; }
