1、List集合

1.1、List简介

List接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。List 接口存储一组可重复，有序（插入顺序）的对象。

1.2、其主要派生类

• Arraylist： Object[] 数组
• Vector：Object[] 数组
• LinkedList：双向链表

2、ArrayList集合源码

2.1、ArrayList的继承关系

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承关系说明

1. extends AbstractList：说明了ArrayList具备AbstractList的一些属性和方法。
2. RandomAccess：实现了该接口，表明的ArrayList是支持快速随机访问的（我们可以通过元素序号进行对元素的访问）。
3. Cloneable：实现了该接口，覆盖clone()函数，说明能被克隆。
4. java.io.Serializable：说明ArrayList支持序列化。

2.2、相关属性

// 序列化id
private static final long serialVersionUID = 8683452581122892189L;

/** * Default initial capacity. 默认的初始化容量 */
private static final int DEFAULT_CAPACITY = 10;

/** * Shared empty array instance used for empty instances. * 指定该ArrayList容量为0时，返回该空数组。 */
private static final Object[] 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. * 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。 * 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而EMPTY_ELEMENTDATA是在用户指定容量为0时返回。 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * 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. * 保存添加到ArrayList中的元素。 * ArrayList的容量就是该数组的长度。 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，数组将扩容值DEFAULT_CAPACITY。 * 被标记为transient，在对象被序列化的时候不会被序列化。 */
transient Object[] elementData; // non-private to simplify nested class access

/** * The size of the ArrayList (the number of elements it contains). * ArrayList的实际大小（数组包含的元素个数/实际数据的数量）默认为0 * @serial */
private int size;
  
/** * 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 */
/** * 分派给arrays的最大容量 * 为什么要减去8呢？ * 因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量大于VM的limit，最终导致OutOfMemoryError。 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//备注：MAX.VALUE为0x7fffffff，转换成十进制就是2147483647，也就是数组的最大长度是2147483639；

属性说明

1. serialVersionUID：序列化id
2. DEFAULT_CAPACITY：默认的初始容量为10
3. EMPTY_ELEMENTDATA：指定该ArrayList容量为0时，返回该空数组。
4. DEFAULTCAPACITY_EMPTY_ELEMENTDATA：当调用无参构造方法，返回的是该数组。 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而EMPTY_ELEMENTDATA是在用户指定容量为0时返回。
5. elementData：保存添加到ArrayList中的元素。ArrayList的容量就是该数组的长度。被标记为transient，在对象被序列化的时候不会被序列化。

2.3、构造方法

ArrayList()空参构造

/** * Constructs an empty list with an initial capacity of ten. * 构造一个初始容量为10的空数组 * * 不传初始容量，初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组， * 会在添加第一个元素的时候扩容为默认的大小，即10。 */
 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

如果是无参构造的话，就使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA进行初始化。

ArrayList(int initialCapacity)有参构造方法

/** * 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 * * 传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组， * 如果小于0抛出异常。 */
// ArrayList(int initialCapacity)构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("不合理的初识容量: " +
                initialCapacity);
    }
}

执行逻辑

1. 判断所传入的参数是否大于0，大于0，就新创建一个长度特定的数组。
2. 长度等于0，就使用EMPTY_ELEMENTDATA替代
3. 长度小于0抛出异常。

ArrayList(Collection<? extends E> c)有参构造

/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * 把传入集合的元素初始化到ArrayList中 * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */
public ArrayList(Collection<? extends E> c) {
    // 将构造方法中的集合参数转换成数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 检查c.toArray()返回的是不是Object[]类型，如果不是，重新拷贝成Object[].class类型
        if (elementData.getClass() != Object[].class)
        	// 数组的创建与拷贝
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 如果c是空的集合，则初始化为空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

执行逻辑

1. 先将传入的集合转化为数组。
2. 如果数组的长度不为0，就判断转换后的数组的Class是否为Object。如果不是还要将其转换为Object
3. 如果数组长度为0，就使用EMPTY_ELEMENTDATA进行初始化。

2.4、相关操作方法

2.4.1、add()

在列表的末尾进行添加，时间复杂度为O(1)。

/** * Appends the specified element to the end of this list. * 将指定的元素追加到此列表的末尾 * @param e element to be appended to this list 被添加到list的元素 * @return <tt>true</tt> (as specified by {@link Collection#add}) */
    public boolean add(E e) {
		//确认list容量，如果不够，容量加1。注意：只加1，保证资源不被浪费
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将元素e放在size的位置上,并且size++
        elementData[size++] = e;
        return true;
    }
	//数组容量检查，不够时则进行扩容，只供类内部使用 
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
		// 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值。DEFAULT_CAPACITY在此之前已经定义为默认的初始化容量是10。
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
	//数组容量检查，不够时则进行扩容，只供类内部使用 
	// minCapacity 想要的最小容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
		//最小容量>数组缓冲区当前长度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//扩容
    }

容量和大小说明

所以说在每一次进行添加元素的时候，我们都需要进行确认list容量，如果不够，进行扩容。

1. elementData中的元素是空的情况

此时也就是 第一次添加元素 的时候。calculateCapacity返回的minCapacity = 10。

2. elementData中的元素不是空的情况

此时也就不是 第一次添加元素 的时候。calculateCapacity返回的minCapacity = size + 1。

3. 执行流程

1. ensureCapacityInternal：数组容量检查
2. calculateCapacity：DEFAULT_CAPACITY和minCapacity之中最大的一个作为minCapacity。
3. ensureExplicitCapacity：判断是否需要进行扩容，如果需要扩容，就调用grow方法进行扩容；。如果minCapacity = 10(也就是elementData中的元素是空的情况下第一次进行添加元素)，那么newCapacity = 10;否则就是新的容量=当前容量+当前容量/2。

4.grow()方法的源码

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. *扩容，保证ArrayList至少能存储minCapacity个元素 * 第一次扩容，逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。 * @param minCapacity the desired minimum capacity */
    private void grow(int minCapacity) {
        // overflow-conscious code
		// 获取当前数组的容量
        int oldCapacity = elementData.length;
		// 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一半（当前容量增加1.5倍）。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
		//如果扩容后的容量还是小于想要的最小容量
        if (newCapacity - minCapacity < 0)
			//将扩容后的容量再次扩容为想要的最小容量
            newCapacity = minCapacity;
//elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，在这里就是真正的初始化elementData的大小了，就是为10.
		//如果扩容后的容量大于临界值，则进行大容量分配
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //新的容量大小已经确定好了，就copy数组，改变容量大小。
        //copyof(原数组，新的数组长度)
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
	//进行大容量分配
    private static int hugeCapacity(int minCapacity) {
		//如果minCapacity<0，抛出异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
		//如果想要的容量大于MAX_ARRAY_SIZE，则分配Integer.MAX_VALUE，否则分配MAX_ARRAY_SIZE 
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

2.4.2、add(int index, E element)

在特定位置进行元素的添加，需要将相应位置的元素往后挪动一位，所以时间复杂度为O(n)。

/** * 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). * 添加元素到指定位置，平均时间复杂度为O(n)。 * * @param index 指定元素要插入的索引 * @param element 要插入的元素 * @throws IndexOutOfBoundsException {@inheritDoc} */
public void add(int index, E element) {
    // 检查是否越界
    rangeCheckForAdd(index);
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将inex及其之后的元素往后挪一位，则index位置处就空出来了
    // **进行了size-索引index次操作**
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    // 将元素插入到index的位置
    elementData[index] = element;
    // 元素数量增1
    size++;
}
/** * A version of rangeCheck used by add and addAll. * add和addAll方法使用的rangeCheck版本 */
// 检查是否越界
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

执行流程

1. 检查是否越界
2. 检查是否进行扩容
3. 将相应位置之后的元素相后挪动一位
4. 将相应元素插入
5. size ++

2.4.3、addAll(Collection c)

将集合c的元素追加到相应的集合中。

/** * 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.) * 将集合c中所有元素添加到当前ArrayList中 * * @param c collection containing elements to be added to this list * @return <tt>true</tt> if this list changed as a result of the call * @throws NullPointerException if the specified collection is null */
public boolean addAll(Collection<? extends E> c) {
    // 将集合c转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 检查是否需要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将c中元素全部拷贝到数组的最后
    System.arraycopy(a, 0, elementData, size, numNew);
    // 集合中元素的大小增加c的大小
    size += numNew;
    // 如果c不为空就返回true，否则返回false
    return numNew != 0;
}

执行流程

1. 将集合c转为数组
2. 检查是否需要扩容
3. 将c中元素全部拷贝到数组的最后
4. 集合中元素的大小增加c的大小
5. 如果c不为空就返回true，否则返回false

2.4.4、get()

由于ArrayList实现了RandomAccess接口，所以ArrayList支持快速随机访问。所以该方法的时间复杂度为O(1)所以该方法的时间复杂度为O(1)。

/** * Returns the element at the specified position in this list. * 返回list中指定位置的元素 * @param index index of the element to return 要返回的元素的索引 * @return the element at the specified position in this list 位于list中指定位置的元素 * @throws IndexOutOfBoundsException {@inheritDoc} */
    public E get(int index) {
        rangeCheck(index);//越界检查
        return elementData(index);//返回索引为index的元素
    }
    /** * 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. 检查指定索引是否在范围内。如果不在，抛出一个运行时异常。 这个方法不检查索引是否为负数，它总是在数组访问之前立即优先使用， 如果给出的索引index>=size，抛出一个越界异常 */
    private void rangeCheck(int index) {
        if (index >= size)
            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;
    }

    // Positional Access Operations 位置访问操作
	// 返回索引为index的元素
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

执行流程

• 但是在每一次的获取元素时，我们都需要进行越界检查。如果越界就抛出相应的异常。
• 返回相应索引位置的元素

2.4.5 set()

由于ArrayList支持快速随机访问，所以该方法时间复杂度为O(1)。

/** * 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} 如果参数指定索引index>=size，抛出一个越界异常 */
    public E set(int index, E element) {
		//检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
        rangeCheck(index);
		//记录被替换的元素（旧值）
        E oldValue = elementData(index);
		//替换元素（新值）
        elementData[index] = element;
		//返回被替换的元素
        return oldValue;
    }

执行流程

1. 检查索引是否越界
2. 记录要被替换的元素
3. 使用新值替换旧值
4. 返回被替换的元素

2.4.6、remove(int index)

根据索引值进行移除元素，时间复杂度为O(n)。因为需要进行元素挪动。

/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). *删除list中位置为指定索引index的元素 * 索引之后的元素向左移一位 * @param index the index of the element to be removed 被删除元素的索引 * @return the element that was removed from the list 被删除的元素 * @throws IndexOutOfBoundsException {@inheritDoc} 如果参数指定索引index>=size，抛出一个越界异常 */
    public E remove(int index) {
		//检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
        rangeCheck(index);
		//结构性修改次数+1
        modCount++;
		//记录索引处的元素
        E oldValue = elementData(index);
		// 删除指定元素后，需要左移的元素个数
        int numMoved = size - index - 1;
		//如果有需要左移的元素，就移动（移动后，该删除的元素就已经被覆盖了）
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
	 	// size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
	 	elementData[--size] = null; // clear to let GC do its work
		//返回被删除的元素
        return oldValue;
    }

执行流程

1. 进行越界检查
2. 记录修改次数（modCount 可以用来检测快速失败的一种标志。）
3. 通过索引找到要删除的元素
4. 计算要移动的位数
5. 移动元素（其实是覆盖掉要删除的元素）
6. 将–size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
7. 返回被删除的元素

2.4.7 remove(Object o)

根据对象进行移除。时间复杂度为O(n)。因为需要寻找相应的元素以及元素挪动。

/** * 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 * <tt>i</tt> such that * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> 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 <tt>true</tt> 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. 私有的remove方法，该方法跳过边界检查，并且不返回已删除的值。 */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
	//arraycopy(原数组，源数组中的起始位置，目标数组，目标数据中的起始位置，要复制的数组元素的数量)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

执行流程

1. 循环遍历寻找对应的元素。
2. 找到后进行删除（包含了元素挪动）
3. elementData[--size] = null，让gc(垃圾回收机制)更快的回收它

2.4.8、removeRange(int fromIndex, int toIndex)

删除一个区间范围内的元素，时间复杂度为O(size - toIndex)。

/** * Removes from this list all of the elements whose index is between * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. * Shifts any succeeding elements to the left (reduces their index). * This call shortens the list by {@code (toIndex - fromIndex)} elements. * (If {@code toIndex==fromIndex}, this operation has no effect.) * 从该列表中删除索引位于两者之间的所有元素，包含fromIndex，但是不包含toIndex， * 将任何后续元素向左移动(减少它们的索引) * 这个调用通过{@code (toIndex - fromIndex)}元素缩短列表。 *(如果{@code toIndex==fromIndex}，此操作无效。) * @throws IndexOutOfBoundsException if {@code fromIndex} or * {@code toIndex} is out of range * ({@code fromIndex < 0 || * fromIndex >= size() || * toIndex > size() || * toIndex < fromIndex}) */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;//被删除的索引后面的个数
        //arraycopy(原数组，源数组中的起始位置，目标数组，目标数据中的起始位置，要复制的数组元素的数量)
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);//新数组的长度
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

执行流程

1. 此方法删除fromIndex到toIndex之间的全部元素，把toIndex以后的元素移动（size-toIndex）位
2. 把左移后空的元素置为null好让垃圾回收机制回收内存。
3. 最后把新数组的大小赋值给size。

2.4.9、 indexOf()和lastIndexOf()方法

//返回此列表中指定元素的第一个出现项的索引，如果该列表不包含该元素，则返回-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;
    }

1. indexOf()：正向查找，返回第一个我们需要查找的元素下标，如果没有找到返回-1。
2. lastIndexOf()：反向查找，返回第一个我们需要查找的元素下标，如果没有找到返回-1。

3、Arraylist 和 Vector 的区别?

1. ArrayList： 底层使用Object[ ]存储，适用于频繁的查找工作，线程不安全
2. Vector ： 底层使用Object[ ]存储，线程安全的。

4、Arraylist 与 LinkedList 区别?

1. 线程安全：Arraylist和LinkedList都是线程不安全的。
2. 底层数据结构：Arraylist底层使用Object[ ]存储，LinkedList底层使用双向链表。
3. 插入删除元素：Arraylist：底层采用的是数组进行存储，所以当添加元素的时候（add()）是在列表的末尾进行添加，所以时间复杂度为O(1)。在特定i位置进行元素的添加(add(int index, E element))和删除时，需要将相应位置的元素进行挪动，所以时间复杂度为O(n - i)。LinkedList :采用链表存储，当进行元素头部尾部的添加和删除时，时间复杂度为O(1)。而在特定位置进行添加删除时，时间复杂度为近似O(n)。
4. 是否支持快速随机访问：Arraylist底层使用Object[ ]存储，所以我们可以通过元素索引进行快速随机访问。LinkedList :采用链表存储，所以不支持高效的元素随机访问。