Java的List集合

一、ArrayList

1.插入

1/** 在元素序列尾部插入 */
2public boolean add(E e) {
3    // 1. 检测是否需要扩容
4    ensureCapacityInternal(size + 1);  // Increments modCount!!
5    // 2. 将新元素插入序列尾部
6    elementData[size++] = e;
7    return true;
8}
9
10/** 在元素序列 index 位置处插入 */
11public void add(int index, E element) {
12    rangeCheckForAdd(index);
13
14    // 1. 检测是否需要扩容
15    ensureCapacityInternal(size + 1);  // Increments modCount!!
16    // 2. 将 index 及其之后的所有元素都向后移一位
17    System.arraycopy(elementData, index, elementData, index + 1,
18                     size - index);
19    // 3. 将新元素插入至 index 处
20    elementData[index] = element;
21    size++;
22}

对于在元素序列尾部插入，这种情况比较简单，只需两个步骤即可： a. 检测数组是否有足够的空间插入 b. 将新元素插入至序列尾部

2 如果是在元素序列指定位置（假设该位置合理）插入，则情况稍微复杂一点，需要三个步骤： a. 检测数组是否有足够的空间 b. 将 index 及其之后的所有元素向后移一位 c. 将新元素插入至 index 处

1.2 扩容

1/** 计算最小容量 */
2private static int calculateCapacity(Object[] elementData, int minCapacity) {
3    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
4        return Math.max(DEFAULT_CAPACITY, minCapacity);
5    }
6    return minCapacity;
7}
8
9/** 扩容的入口方法 */
10private void ensureCapacityInternal(int minCapacity) {
11    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
12}
13
14private void ensureExplicitCapacity(int minCapacity) {
15    modCount++;
16
17    // overflow-conscious code
18    if (minCapacity - elementData.length > 0)
19        grow(minCapacity);
20}
21
22/** 扩容的核心方法 */
23private void grow(int minCapacity) {
24    // overflow-conscious code
25    int oldCapacity = elementData.length;
26    // newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
27    int newCapacity = oldCapacity + (oldCapacity >> 1);
28    if (newCapacity - minCapacity < 0)
29        newCapacity = minCapacity;
30    if (newCapacity - MAX_ARRAY_SIZE > 0)
31        newCapacity = hugeCapacity(minCapacity);
32    // 扩容
33    elementData = Arrays.copyOf(elementData, newCapacity);
34}
35
36private static int hugeCapacity(int minCapacity) {
37    if (minCapacity < 0) // overflow
38        throw new OutOfMemoryError();
39    // 如果最小容量超过 MAX_ARRAY_SIZE，则将数组容量扩容至 Integer.MAX_VALUE
40    return (minCapacity > MAX_ARRAY_SIZE) ?
41        Integer.MAX_VALUE :
42        MAX_ARRAY_SIZE;
43}

1.3 删除

1/** 删除指定位置的元素 */
2public E remove(int index) {
3    rangeCheck(index);
4
5    modCount++;
6    // 返回被删除的元素值
7    E oldValue = elementData(index);
8
9    int numMoved = size - index - 1;
10    if (numMoved > 0)
11        // 将 index + 1 及之后的元素向前移动一位，覆盖被删除值
12        System.arraycopy(elementData, index+1, elementData, index,
13                         numMoved);
14    // 将最后一个元素置空，并将 size 值减1                
15    elementData[--size] = null; // clear to let GC do its work
16
17    return oldValue;
18}
19
20E elementData(int index) {
21    return (E) elementData[index];
22}
23
24/** 删除指定元素，若元素重复，则只删除下标最小的元素 */
25public boolean remove(Object o) {
26    if (o == null) {
27        for (int index = 0; index < size; index++)
28            if (elementData[index] == null) {
29                fastRemove(index);
30                return true;
31            }
32    } else {
33        // 遍历数组，查找要删除元素的位置
34        for (int index = 0; index < size; index++)
35            if (o.equals(elementData[index])) {
36                fastRemove(index);
37                return true;
38            }
39    }
40    return false;
41}
42
43/** 快速删除，不做边界检查，也不返回删除的元素值 */
44private void fastRemove(int index) {
45    modCount++;
46    int numMoved = size - index - 1;
47    if (numMoved > 0)
48        System.arraycopy(elementData, index+1, elementData, index,
49                         numMoved);
50    elementData[--size] = null; // clear to let GC do its work
51}

上面的删除方法并不复杂，这里以第一个删除方法为例，删除一个元素步骤如下：

获取指定位置 index 处的元素值
将 index + 1 及之后的元素向前移动一位
将最后一个元素置空，并将 size 值减 1
返回被删除值，完成删除操作

**1.4【强制】**不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。 为什么？

1        List<String> list = new ArrayList<String>();
2        list.add("1");
3        list.add("2");
4        list.add("3");
5        list.add("4");
6        list.add("5");
7        for (String temp : list) {
8            if ("4".equals(temp)) {
9                list.remove(temp);
10            }
11        }
12        System.out.println(list);

这里有两个变量需要注意：一个是modCount：这个外部的变量，也就是ArrayList下的变量：

1 /**
2     * The number of times this list has been <i>structurally modified</i>.
3     * Structural modifications are those that change the size of the
4     * list, or otherwise perturb it in such a fashion that iterations in
5     * progress may yield incorrect results.
6     *
7    ….
8     */
9    protected transient int modCount = 0;

只贴前面一部分注释，注释说这个变量来记录ArrayList集合的修改次数，也说明了可能会和迭代器内部的期望值不一致；另外一个是Itr的变量expectedModCount; 能过上面的代码可以看到在Itr创建时默认定义了 int expectedModCount = modCount; 我们先只看remove的操作: 通过在if条件成立时remove(“3”)操作的断点，我们进入到ArrayList下的remove方法，注意这里并没有进入内部迭代器Itr的remove()方法【这里是产生异常的关键点】

1  public boolean remove(Object o) {
2        if (o == null) {
3            for (int index = 0; index < size; index++)
4                if (elementData[index] == null) {
5                    fastRemove(index);
6                    return true;
7                }
8        } else {
9            for (int index = 0; index < size; index++)
10                if (o.equals(elementData[index])) {
11                    fastRemove(index);
12                    return true;
13                }
14        }
15        return false;
16    }

很显然，这里应该正常的走到了fastRemove()方法中：

1   /*
2     * Private remove method that skips bounds checking and does not
3     * return the value removed.
4     */
5    private void fastRemove(int index) {
6        modCount++;
7        int numMoved = size - index - 1;
8        if (numMoved > 0)
9            System.arraycopy(elementData, index+1, elementData, index,
10                             numMoved);
11        elementData[--size] = null; // clear to let GC do its work
12    }

这里可以看到在fastRemove()方法中通过modCount++ 自增了一次，而此时并没有改变内部迭代器Itr中的expectedModCount 的值；我们再往下走，此会再迭代到下一个元素；先会通过hasNext(){return cursor != size;}来判断是否还有元素，很显然，若删除前面的元素，此处一定会为true（注意：若之前删除的是倒数第二个元素，此处的cursor就是最后一个索引值size()-1,而由于已成功删除一个元素，此处的siz也是原size()-1,两者相等，此处会返回false，本质是错错得对，提前跳出了循环而已）而在调用next()方面来获取下一个元素时，可以看到在next()方法中先调用了checkForComodification()方法：

1 final void checkForComodification() {
2            if (modCount != expectedModCount)
3                throw new ConcurrentModificationException();
4 }

很显然，此处的modCount已经比expectedModCount大1了，肯定不一样，if条件成立，抛出一个ConcurrentModificationException异常。致此，我们大概理清了为什么在foreach快速遍历中删除元素会崩溃的原因。总结一下：（1）在使用For-Each快速遍历时，ArrayList内部创建了一个内部迭代器iterator，使用的是hasNext和next()方法来判断和取下一个元素。（2）ArrayList里还保存了一个变量modCount，用来记录List修改的次数，而iterator保存了一个expectedModCount来表示期望的修改次数，在每个操作前都会判断两者值是否一样，不一样则会抛出异常；（3））在foreach循环中调用remove()方法后，会走到fastRemove()方法，该方法不是iterator中的方法，而是ArrayList中的方法，在该方法中modCount++; 而iterator中的expectedModCount并没有改变；（4）再次遍历时，会先调用内部类iteator中的hasNext(),再调用next(),在调用next()方法时，会对modCount和expectedModCount进行比较，此时两者不一致，就抛出了ConcurrentModificationException异常。而为什么只有在删除倒数第二个元素时程序没有报错呢？因为在删除倒数第二个位置的元素后，开始遍历最后一个元素时，先会走到内部类iterator的hasNext()方法时，里面返回的是 return cursor != size; 此时cursor是最后一个索引值，即原size()-1,而由于已经删除了一个元素，该方法内的size也是原size()-1,故 return cursor != size；会返回false,直接退出for循环，程序便不会报错。最后，通过源代码的判断，要在循环中删除元素，最好的方式还是直接拿到ArrayList对象下的迭代器list.iterator()，通过源码可以看到，该方法也就是直接把内部的迭代器返回出来

二、LinkedList

1. 特点

LinkedList底层数据结构为双向链表，非同步。
LinkedList允许null值。
由于双向链表，顺序访问效率高，而随机访问效率较低，常用遍历时用LinkedList
注意源码中的相关操作，主要是构建双向链表。

常见面试题

1. LinkedList的删除速率一定比ArrayList快吗？

对于remove（Object o）方法来说不一定，ArrayList耗时在移动数组元素，而LinkedList耗时在遍历查找object的过程，比如说node（int index）方法和遍历删除的方法，因此，当数据量不就是特别大的时候，两者的速率差别不大。

List集合