部分方法没有解释，有疑问或错误的地方，欢迎评论指出
package java.util;import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;/*** E - Element (在集合中使用，因为集合中存放的是元素)** T - Type（Java 类）** K - Key（键）** V - Value（值）** N - Number（数值类型）** ? - 表示不确定的java类型** @param <E>*/
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{private static final long serialVersionUID = 8683452581122892189L;/*** 默认初始化容量*/private static final int DEFAULT_CAPACITY = 10;/*** 空集合*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** 用于默认大小的空实例的共享空数组实例。* 我们将此与EMPTY_ELEMENTDATA区分开用来了解第一个元素被添加时扩容多少*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 存储ArrayList元素的数组缓冲区.* ArrayList的容量是此数组缓冲区的长度。* 添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。*/transient Object[] elementData; // 非私有，以简化嵌套类访问/*** ArrayList的大小（它包含的元素个数）*/private int size;/*** 构造具有指定初始容量的空列表。* @param initialCapacity 列表的初始容量* @throws IllegalArgumentException 如果指定的初始容量为负数*/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);}}/*** 构造一个初始容量为10的空列表.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** 按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表.** @param c 要将其元素放入此列表的集合* @throws NullPointerException 如果指定的集合为null*/public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// toArray可能（错误地）不返回Object []if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// 替换为空数组.this.elementData = EMPTY_ELEMENTDATA;}}/*** 将此 ArrayList 实例的容量调整为列表的当前大小。* 应用程序可以使用此操作来最小化 ArrayList 实例的存储。*/public void trimToSize() {modCount++;//此列表已被 结构修改 的次数。if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}/*** 如有必要，增加此 ArrayList 实例的容量，* 以确保它至少可以容纳由 minCapacity 参数指定的元素数。*/public void ensureCapacity(int minCapacity) {int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// any size if not default element table? 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++;// 防止溢出的代码if (minCapacity - elementData.length > 0)grow(minCapacity);}/*** 要分配的最大数组大小。* 某些VM在数组中保留一些标题字。* 尝试分配更大的数组可能会导致OutOfMemoryError：请求的数组大小超过VM限制*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** 增加容量以确保它至少可以容纳由 minCapacity 参数指定的元素数。* @param minCapacity 所需的最小容量*/private void grow(int minCapacity) {// overflow-conscious codeint 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) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}/*** 元素个数*/public int size() {return size;}/*** 判断list是否为空*/public boolean isEmpty() {return size == 0;}/*** 是否包含元素 o*/public boolean contains(Object o) {return indexOf(o) >= 0;}/*** 判断元素第一次出现的位置下标，没有则返回-1*/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*/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 Object clone() {try {ArrayList<?> v = (ArrayList<?>) super.clone();v.elementData = Arrays.copyOf(elementData, size);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// 这不应该发生，因为我们是克隆的throw new InternalError(e);}}/*** 转Array*/public Object[] toArray() {return Arrays.copyOf(elementData, size);}//转数组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;}//获取指定位置的元素E elementData(int index) {return (E) elementData[index];}//获取指定位置的元素public E get(int index) {rangeCheck(index);return elementData(index);}//在指定位置 替换元素 返回替换前的元素public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);//替换elementData[index] = element;//返回之前的元素return oldValue;}//添加元素public boolean add(E e) {//扩容ensureCapacityInternal(size + 1); // Increments modCount!!//添加elementData[size++] = e;return true;}/*** 指定位置 添加指定元素*/public void add(int index, E element) {rangeCheckForAdd(index);//判断是否越界ensureCapacityInternal(size + 1); // 扩容 确保容量//重新给数组赋值System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}/*** 移除指定位置的元素*/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 workreturn oldValue;}/*** 删除指定元素* 如果有且删除成功 返回true* 不存在或删除失败 返回false*/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;}/** 私有删除方法，它跳过边界检查并且不返回删除的值。*/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; // 明确让GC做它的工作}/*** 从此列表中删除所有元素。 此调用返回后，列表将为空。*/public void clear() {modCount++;// clear to let GC do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}/*** 将指定集合中的所有元素追加到此列表末尾* 按照指定集合的迭代器返回的顺序。*/public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);System.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}/*** 将指定集合中的所有元素追加到指定位置*/public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew); // Increments modCountint numMoved = size - index;if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);System.arraycopy(a, 0, elementData, index, numNew);size += numNew;return numNew != 0;}/*** 从此列表中删除索引在 fromIndex - toIndex之间的所有元素，* 包括 fromIndex , 不包括 toIndex。*/protected void removeRange(int fromIndex, int toIndex) {modCount++;int numMoved = size - toIndex;System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);// clear to let GC do its workint newSize = size - (toIndex-fromIndex);for (int i = newSize; i < size; i++) {elementData[i] = null;}size = newSize;}/*** 越界校验*/private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/*** 判断index是否越界*/private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/*** 越界提示信息*/private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}/*** 删除该列表中指定的集合*/public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, false);}/*** 从该列表中删除未包含在指定集合中的所有元素。*/public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}//c -- 指定集合//complement -- （true 未包含）、（false 包含）private boolean batchRemove(Collection<?> c, boolean complement) {//值传递final Object[] elementData = this.elementData;//r = 0 , w = 新数组下标int r = 0, w = 0;boolean modified = false;try {//循环遍历for (; r < size; r++)//存在此元素 && complement == true//不存在此元素 && complement == falseif (c.contains(elementData[r]) == complement)//将此元素从0开始保存在此列表中elementData[w++] = elementData[r];} finally {// 最后 elementData.length - w = 1if (r != size) {System.arraycopy(elementData, r,elementData, w,size - r);w += size - r;//若c.contains()没有抛异常 ==> w += 1;}//如果删除完成后，w == size 则说明没有元素被移除 返回falseif (w != size) {for (int i = w; i < size; i++)elementData[i] = null;//gcmodCount += size - w;size = w; //最后列表的大小modified = true;}}return modified;}/*** 迭代器*/public Iterator<E> iterator() {return new Itr();}/*** 迭代器 - 内部类*/private class Itr implements Iterator<E> {int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint 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 = i + 1;return (E) elementData[lastRet = i];}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.remove(lastRet);cursor = lastRet;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 trafficcursor = i;lastRet = i - 1;checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}//截取listpublic List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList(this, 0, fromIndex, toIndex);}//截取时判断数组是否越界static void subListRangeCheck(int fromIndex, int toIndex, int size) {if (fromIndex < 0)throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);if (toIndex > size)throw new IndexOutOfBoundsException("toIndex = " + toIndex);if (fromIndex > toIndex)throw new IllegalArgumentException("fromIndex(" + fromIndex +") > toIndex(" + toIndex + ")");}private class SubList extends AbstractList<E> implements RandomAccess {private final AbstractList<E> parent;private final int parentOffset;private final int offset;int size;SubList(AbstractList<E> parent,int offset, int fromIndex, int toIndex) {this.parent = parent;this.parentOffset = fromIndex;this.offset = offset + fromIndex;this.size = toIndex - fromIndex;this.modCount = ArrayList.this.modCount;}public E set(int index, E e) {rangeCheck(index);checkForComodification();E oldValue = ArrayList.this.elementData(offset + index);ArrayList.this.elementData[offset + index] = e;return oldValue;}//通过下标 获取元素public E get(int index) {rangeCheck(index);checkForComodification();return ArrayList.this.elementData(offset + index);}public int size() {checkForComodification();return this.size;}public void add(int index, E e) {rangeCheckForAdd(index);checkForComodification();parent.add(parentOffset + index, e);this.modCount = parent.modCount;this.size++;}public E remove(int index) {rangeCheck(index);checkForComodification();E result = parent.remove(parentOffset + index);this.modCount = parent.modCount;this.size--;return result;}protected void removeRange(int fromIndex, int toIndex) {checkForComodification();parent.removeRange(parentOffset + fromIndex,parentOffset + toIndex);this.modCount = parent.modCount;this.size -= toIndex - fromIndex;}public boolean addAll(Collection<? extends E> c) {return addAll(this.size, c);}public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);int cSize = c.size();if (cSize==0)return false;checkForComodification();parent.addAll(parentOffset + index, c);this.modCount = parent.modCount;this.size += cSize;return true;}public Iterator<E> iterator() {return listIterator();}public ListIterator<E> listIterator(final int index) {checkForComodification();rangeCheckForAdd(index);final int offset = this.offset;return new ListIterator<E>() {int cursor = index;int lastRet = -1;int expectedModCount = ArrayList.this.modCount;public boolean hasNext() {return cursor != SubList.this.size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();int i = cursor;if (i >= SubList.this.size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (offset + i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[offset + (lastRet = i)];}public boolean hasPrevious() {return cursor != 0;}@SuppressWarnings("unchecked")public E previous() {checkForComodification();int i = cursor - 1;if (i < 0)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (offset + i >= elementData.length)throw new ConcurrentModificationException();cursor = i;return (E) elementData[offset + (lastRet = i)];}@SuppressWarnings("unchecked")public void forEachRemaining(Consumer<? super E> consumer) {Objects.requireNonNull(consumer);final int size = SubList.this.size;int i = cursor;if (i >= size) {return;}final Object[] elementData = ArrayList.this.elementData;if (offset + i >= elementData.length) {throw new ConcurrentModificationException();}while (i != size && modCount == expectedModCount) {consumer.accept((E) elementData[offset + (i++)]);}// update once at end of iteration to reduce heap write trafficlastRet = cursor = i;checkForComodification();}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {SubList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = ArrayList.this.modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}public void set(E e) {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(offset + lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}public void add(E e) {checkForComodification();try {int i = cursor;SubList.this.add(i, e);cursor = i + 1;lastRet = -1;expectedModCount = ArrayList.this.modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (expectedModCount != ArrayList.this.modCount)throw new ConcurrentModificationException();}};}public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList(this, offset, fromIndex, toIndex);}private void rangeCheck(int index) {if (index < 0 || index >= this.size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private void rangeCheckForAdd(int index) {if (index < 0 || index > this.size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+this.size;}private void checkForComodification() {if (ArrayList.this.modCount != this.modCount)throw new ConcurrentModificationException();}public Spliterator<E> spliterator() {checkForComodification();return new ArrayListSpliterator<E>(ArrayList.this, offset,offset + this.size, this.modCount);}}@Overridepublic 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;for (int i=0; modCount == expectedModCount && i < size; i++) {action.accept(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}}@Override@SuppressWarnings("unchecked")public void sort(Comparator<? super E> c) {final int expectedModCount = modCount;Arrays.sort((E[]) elementData, 0, size, c);if (modCount != expectedModCount) {throw new ConcurrentModificationException();}modCount++;}
}