Java的List集合

一、ArrayList

1.插入

/** 在元素序列尾部插入 */
public boolean add(E e) {
    // 1. 检测是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将新元素插入序列尾部
    elementData[size++] = e;
    return true;
}

/** 在元素序列 index 位置处插入 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // 1. 检测是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将 index 及其之后的所有元素都向后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 3. 将新元素插入至 index 处
    elementData[index] = element;
    size++;
}

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

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

1.2 扩容

/** 计算最小容量 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/** 扩容的入口方法 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/** 扩容的核心方法 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果最小容量超过 MAX_ARRAY_SIZE，则将数组容量扩容至 Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

1.3 删除

/** 删除指定位置的元素 */
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    // 返回被删除的元素值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将 index + 1 及之后的元素向前移动一位，覆盖被删除值
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最后一个元素置空，并将 size 值减1                
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

E elementData(int index) {
    return (E) elementData[index];
}

/** 删除指定元素，若元素重复，则只删除下标最小的元素 */
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; // clear to let GC do its work
}

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

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

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

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

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

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

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

  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;
    }

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

   /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    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; // clear to let GC do its work
    }

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

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

很显然，此处的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集合