/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ publicbooleanadd(E e){ //添加元素之前,先调用ensureCapacityInternal方法 ensureCapacityInternal(size + 1); // Increments modCount!! //这里看到ArrayList添加元素的实质就相当于为数组赋值 elementData[size++] = e; returntrue; }
/** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ publicvoidadd(int index, E element){ rangeCheckForAdd(index);
/** * The maximum size of array to allocate. * 要分配的最大数组大小 * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ privatestaticfinalint MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ privatevoidgrow(int minCapacity){ // oldCapacity为旧容量,newCapacity为新容量 int oldCapacity = elementData.length; // 将oldCapacity 右移一位,其效果相当于oldCapacity /2, // 我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍, int newCapacity = oldCapacity + (oldCapacity >> 1); // 然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量, if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE, // 如果minCapacity大于最大容量,则新容量则为`Integer.MAX_VALUE`,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。 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); }
/** * Copies an array from the specified source array, beginning at the * specified position, to the specified position of the destination array. * A subsequence of array components are copied from the source * array referenced by <code>src</code> to the destination array * referenced by <code>dest</code>. * * @param src the source array. * @param srcPos starting position in the source array. * @param dest the destination array. * @param destPos starting position in the destination data. * @param length the number of array elements to be copied. */ publicstaticnativevoidarraycopy(Object src, int srcPos, Object dest, int destPos, int length);
/** * Copies the specified array, truncating or padding with nulls (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain <tt>null</tt>. * Such indices will exist if and only if the specified length * is greater than that of the original array. * The resulting array is of the class <tt>newType</tt>. * * @param <U> the class of the objects in the original array * @param <T> the class of the objects in the returned array * @param original the array to be copied * @param newLength the length of the copy to be returned * @param newType the class of the copy to be returned * @return a copy of the original array, truncated or padded with nulls * to obtain the specified length */ publicstatic <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index){ 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
/** * Removes the first occurrence of the specified element from this list, * if it is present. */ publicbooleanremove(Object o){ if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); returntrue; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); returntrue; } } returnfalse; }
私有移除方法
1 2 3 4 5 6 7 8 9 10 11 12
/* * Private remove method that skips bounds checking and does not * return the value removed. */ privatevoidfastRemove(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 }
查找
查找指定元素所在位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. */ publicintindexOf(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; }
/** * Save the state of the <tt>ArrayList</tt> instance to a stream (that * is, serialize it). */ privatevoidwriteObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone() s.writeInt(size);
// Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); }
if (modCount != expectedModCount) { thrownew ConcurrentModificationException(); } }
/** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */ privatevoidreadObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff s.defaultReadObject();
// Read in capacity s.readInt(); // ignored
if (size > 0) { // be like clone(), allocate array based upon size not capacity int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size);
Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); } } }
/** * Returns a view of the portion of this list between the specified * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If * {@code fromIndex} and {@code toIndex} are equal, the returned list is * empty.) The returned list is backed by this list, so non-structural * changes in the returned list are reflected in this list, and vice-versa. * The returned list supports all of the optional list operations. */ public List<E> subList(int fromIndex, int toIndex){ subListRangeCheck(fromIndex, toIndex, size); returnnew SubList(this, 0, fromIndex, toIndex); }
privateclassItrimplementsIterator<E> { int cursor; // 下一个要返回的元素的下标 int lastRet = -1; // 最后一个要返回元素的下标 没有元素返回 -1 int expectedModCount = modCount;
Itr() {}
publicbooleanhasNext(){ return cursor != size; }
public E next(){ // 会校验modCount是否等于expectedModCount,不等于就会抛出ConcurrentModificationException checkForComodification(); int i = cursor; if (i >= size) thrownew NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) thrownew ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; }
publicvoidremove(){ if (lastRet < 0) thrownew IllegalStateException(); checkForComodification();
@Override publicvoidforEachRemaining(Consumer<? super E> consumer){ Objects.requireNonNull(consumer); finalint size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { thrownew 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(); }
finalvoidcheckForComodification(){ if (modCount != expectedModCount) thrownew ConcurrentModificationException(); } }
其他
ensureCapacity(int minCapacity)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
/** * 如有必要,增加此 ArrayList 实例的容量,以确保它至少可以容纳由minCapacity参数指定的元素数 */ publicvoidensureCapacity(int minCapacity){ int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY;
if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }