一、简介
ArrayList是可以动态增长和缩减的索引序列，它是基于数组实现的List类。
该类封装了一个动态再分配的Object[]数组，每一个类对象都有一个capacity属性，表示它们所封装的Object[]数组的长度，当向ArrayList中添加元素时，该属性值会自动增加。如果想ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capacity，可以减少增加重分配的次数提高性能。
ArrayList的用法和Vector类似，但是Vector是一个较老的集合，具有很多缺点，不建议使用。
ArrayList是线程不安全的，当多条线程访问同一个ArrayList集合时，程序需要手动保证该集合的同步性，而Vector则是线程安全的
二、签名
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
三、自定义实现
package com;import java.util.Arrays;import java.util.Collection;/*** @Description:*/public class ArrayList{ /** * 默认大小为10 * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * 共享空数组实例用于空集合实例 * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 用于缺省大小的空实例的共享空数组实例。当添加第一个元素,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. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 分配数组的最大大小. * 分配更大数组,可能会导致产生OutOfMeimyError错误：请求的数组大小超过VM限制. * 因此此处在Integer.MAX_VALUE上减去8 * * 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 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 存储数组列表元素的数组缓冲区.数组的容量是这个数组缓冲器的长度. * 使用elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空数组, * 当添加第一个元素时都将扩展到默认容量10。 * 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. */ Object[] elementData; /** * 当前arraylist中的数据量 * The size of the ArrayList (the number of elements it contains). * @serial */ private int size; /** * 无参构造器 * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//DEFAULTCAPACITY_EMPTY_ELEMENTDATA的大小也是0,在第一次调用add的时候才会进行默认数组大小的初始化操作 } /** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */ 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); } } /** * 创建一个存放Collection的数组对象 * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection c) { elementData = c.toArray();//将Collection转换为数组元素,并存放到数组中 if ((size = elementData.length) != 0) {//若数组长度不为0，则将数组大小进行扩容至collection转化的数组对象大小 // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else {//数组长度为0，则初始化一个空的共享数组实例 // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } /** * 计算数组容量大小 * @param elementData * @param minCapacity * @return */ private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//如果此时为第一次add return Math.max(DEFAULT_CAPACITY, minCapacity);//返回在默认容量大小和传递的最小容量大小中最大的那一个数 } return minCapacity;//返回传递的最小容量值 } /** * 得到(Integer.MAX_VALUE-8)和最小容量minCapacity的比较大小 * @param minCapacity * @return */ private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // 若minCapacity小于0，则抛出一个OutOfMemoryError异常 throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;//若当前最小容量大于(Integer.MAX_VALUE-8)，则扩容至Integer.MAX_VALUE,否则扩容至(Integer.MAX_VALUE-8) } /** * 判断数组是否达到最小容量,达到最小容量则执行扩容操作 * @param minCapacity */ private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } /** * 将当前数组的最小容量和数组分配的大小进行比较 * 若最小容量大于数组分配的大小,则对数组的容量进行扩容 * @param minCapacity */ private void ensureExplicitCapacity(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 针对当前数组容量和最小容量进行计算,重新分配数组的空间 * 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 */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length;//当前数组容量大小 int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量=当前数组容量大小*1.5 if (newCapacity - minCapacity < 0)//新的容量小于最小容量，则将新的容量设置为最小容量 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0)//新的容量大小了最大数组大小时，则将新的容量设置为Integer.MAX_VALUE newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);//对elementData扩容到newCapacity大小 } /** * 返回数组的长度大小 * Returns the number of elements in this list. * * @return the number of elements in this list */ public int size() { return size; } /** * 判断数组是否为空.为空则返回true,反之false * Returns true if this list contains no elements. * * @return true if this list contains no elements */ public boolean isEmpty() { return size == 0; } /** * 判断数组是否存在对象o,返回indexOf的查找结果 * Returns true if this list contains the specified element. * More formally, returns true if and only if this list contains * at least one element e such that * (o==null ? e==null : o.equals(e)). * * @param o element whose presence in this list is to be tested * @return true if this list contains the specified element */ public boolean contains(Object o) { return indexOf(o) >= 0; } /** * 返回对象o在数组中第一次出现的索引值,未出现则返回-1 * 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 i such that * (o==null ? get(i)==null : o.equals(get(i))), * or -1 if there is no such index. */ public int indexOf(Object o) { if (o == null) {//对象o为null,则返回数组中第一个null对象的索引值 for (int i = 0; i < size; i++)//正向遍历 if (elementData[i] == null) return i; } else {//对象o不为null,则根据equals()比对结果,返回数组中第一次出现的索引值 for (int i = 0; i < size; i++)//正向遍历 if (o.equals(elementData[i])) return i; } return -1;//返回-1 } /** * 返回对象o在数组中最后一次出现的索引值,未出现则返回-1 * Returns the index of the last occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the highest index i such that * (o==null ? get(i)==null : o.equals(get(i))), * or -1 if there is no such index. */ public int lastIndexOf(Object o) { if (o == null) {//对象o为null,则返回数组中最后一个null对象的索引值 for (int i = size - 1; i >= 0; i--)//反向遍历 if (elementData[i] == null) return i; } else {//对象o不为null,则根据equals()比对结果,返回数组中最后一次出现的索引值 for (int i = size - 1; i >= 0; i--)//反向遍历 if (o.equals(elementData[i])) return i; } return -1; } /** * 返回 * Returns an array containing all of the elements in this list * in proper sequence (from first to last element). * * The returned array will be "safe" in that no references to it are * maintained by this list. (In other words, this method must allocate * a new array). The caller is thus free to modify the returned array. * *
This method acts as bridge between array-based and collection-based * APIs. * * @return an array containing all of the elements in this list in * proper sequence */ public Object[] toArray() { return Arrays.copyOf(elementData, size); } /** * Returns an array containing all of the elements in this list in proper * sequence (from first to last element); the runtime type of the returned * array is that of the specified array. If the list fits in the * specified array, it is returned therein. Otherwise, a new array is * allocated with the runtime type of the specified array and the size of * this list. * *
If the list fits in the specified array with room to spare * (i.e., the array has more elements than the list), the element in * the array immediately following the end of the collection is set to * null. (This is useful in determining the length of the * list only if the caller knows that the list does not contain * any null elements.) * * @param a the array into which the elements of the list are to * be stored, if it is big enough; otherwise, a new array of the * same runtime type is allocated for this purpose. * @return an array containing the elements of the list * @throws ArrayStoreException if the runtime type of the specified array * is not a supertype of the runtime type of every element in * this list * @throws NullPointerException if the specified array is null */ @SuppressWarnings("unchecked") public
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; } // Positional Access Operations @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } /** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { rangeCheck(index); return elementData(index); } /** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } /** * 添加一个元素e到数组,并返回true * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return true (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e;//将元素e添加到数组末尾 return true; } /** * 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} */ 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++; } /** * 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); 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 return oldValue; } /** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * i such that * (o==null ? get(i)==null : o.equals(get(i))) * (if such an element exists). Returns true if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return true if this list contained the specified element */ 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 remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int 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 all of the elements from this list. The list will * be empty after this call returns. */ public void clear() { // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } /** * Appends all of the elements in the specified collection to the end of * this list, in the order that they are returned by the * specified collection's Iterator. The behavior of this operation is * undefined if the specified collection is modified while the operation * is in progress. (This implies that the behavior of this call is * undefined if the specified collection is this list, and this * list is nonempty.) * * @param c collection containing elements to be added to this list * @return true if this list changed as a result of the call * @throws NullPointerException if the specified collection is null */ public boolean addAll(Collection c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } /** * Inserts all of the elements in the specified collection into this * list, starting at the specified position. Shifts the element * currently at that position (if any) and any subsequent elements to * the right (increases their indices). The new elements will appear * in the list in the order that they are returned by the * specified collection's iterator. * * @param index index at which to insert the first element from the * specified collection * @param c collection containing elements to be added to this list * @return true if this list changed as a result of the call * @throws IndexOutOfBoundsException {@inheritDoc} * @throws NullPointerException if the specified collection is null */ public boolean addAll(int index, Collection c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); int 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; } /** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * A version of rangeCheck used by add and addAll. */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * Constructs an IndexOutOfBoundsException detail message. * Of the many possible refactorings of the error handling code, * this "outlining" performs best with both server and client VMs. */ private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size; }}