List集合

BichonCode 63 0 0

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++;
}
  1. 对于在元素序列尾部插入,这种情况比较简单,只需两个步骤即可: 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
}

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

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

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)方法和遍历删除的方法,因此,当数据量不就是特别大的时候,两者的速率差别不大。

预览图
收藏
评论区
守株待兔
最新文章
数据库系统概论 2021-01-23 11:49
ConcurrentHashMap 2021-01-23 11:46
计算机网络 2021-01-23 11:45
Java的其他Map 2021-01-23 11:43
双指针问题 2021-01-23 11:40
软件工程 2021-01-23 11:38
大数据排序 2021-01-23 11:37
操作系统 2021-01-23 11:29

导读