List集合

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

收藏
评论区

相关推荐

List集合
Java的List集合 一、ArrayList 1.插入 java / 在元素序列尾部插入 / public boolean add(E e) { // 1. 检测是否需要扩容 ensureCapacityInternal(size 1); // Increments modCount // 2. 将新元素插入序列尾
Java 中初始化 List 集合的 6 种方式!
![](https://oscimg.oschina.net/oscnet/0db5449d0736e22cb92ba0cf9daad91990a.jpg)   List 是 Java 开发中经常会使用的集合,你们知道有哪些方式可以初始化一个 List 吗?这其中不缺乏一些坑,今天栈长我给大家一一普及一下。   1、常规方式   ListString
Java 中初始化 List 集合的 6 种方式!
![](https://oscimg.oschina.net/oscnet/26618d87-ed40-4f14-b290-16a3e22e57fe.png) List 是 Java 开发中经常会使用的集合,你们知道有哪些方式可以初始化一个 List 吗?这其中不缺乏一些坑,今天栈长我给大家一一普及一下。 1、常规方式 ------ Lis
Java 删除List元素的正确方式
**方式一:使用Iterator的remove()方法** public class Test { public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("aa"
Java 并发数据结构
\[TOCM\] 因为Java提供了一些非线程安全的数据结构如HashMap,ArrayList,HashSet等。所有在多线程环境中需要使用支持并发访问操作的数据结构。 #### 并发List Vector,CopyOnWriteArrayList 是线程安全的List。ArrayList是线程不安全的。如果一定要使用,需要: `Collection
Java 笔记
*  动态数组 ArrayList<String> List = new ArrayList<String>(); //定义动态数组 List.add(temp); //添加字符串 List<Integer> ret = new ArrayList<Integer>(); ret.add(i+1);
Java入门第五篇:Java集合框架的Collection、List、Set、Map接口
【java的集合框架】  Collection:       1.List         ①ArrayList         ②LinkedList       2.set         ①HashSet         ②LinkedHashSet         ③TreeSet Map:        1.HashMap  
Java开发者容易犯的十个错误
![](https://oscimg.oschina.net/oscnet/c9f00cc9-1868-4fbe-8a86-5119d104090b.gif) Top1. 数组转换为数组列表 将数组转换为数组列表,开发者经常会这样做: > \[java\] > List<String> list = Arrays.asList(arr); Arr
Java集合面试题
**Collection** Set和hashCode以及equals方法的联系 Set内存放的元素为什么不可以重复,内部是如何保证和实现的? List 和 Set 区别 List 和 Map 区别 Arraylist 与 LinkedList 区别 ArrayList 与 Vector 区别 Arraylist与LinkedList默认空间是
Java面试之容器
#### 18\. Java 容器都有哪些? Java 容器分为 Collection 和 Map 两大类,其下又有很多子类,如下所示: * Collection * List * ArrayList * LinkedList * Vector * Stack * Set * Has
java 容器
![](https://oscimg.oschina.net/oscnet/fb346547b9d6695817a2fcac24bb4e6b576.png) ### 概述 List接口、Queue接口、Set接口均继承了Collection接口,而Collection接口又继承了Iterable接口。 public interface
BAT面试笔试33题:JavaList、Java Map等经典面试题!
JavaList面试题汇总 ============= 1、List集合:ArrayList、LinkedList、Vector等。 2、Vector是List接口下线程安全的集合。 3、List是有序的。 4、ArrayList和LinkedList数据结构不一样,前者用在查询较多的场合,后者适用于插入较多的场合。 5、ArrayList使用的是
Hibernate的批量处理和分页技术、投影技术
投影查询——过滤部分字段 返回的List集合元素为Object\[\] Query query = session.createQuery("select c.cname, c.csex from Customer c"); List list = query.list(); Iterator iter = list.itera
Iterator to list的三种方法
Iterator to list的三种方法 简介 == 集合的变量少不了使用Iterator,从集合Iterator非常简单,直接调用Iterator方法就可以了。 那么如何从Iterator反过来生成List呢?今天教大家三个方法。 使用while ======= 最简单最基本的逻辑就是使用while来遍历这个Iterator,在遍历的过程中将I
List接口(动态数组)
List接口(动态数组) ============ List集合类中元素_**有序且可重复**_ ArrayList(重要) ------------- * 作为List接口的主要实现类 * 线程不安全的,效率高 * 底层使用Object\[\] elementData数组存储 ### ArrayList的源码分析 #### jdk7

热门文章

ConcurrentHashMap数据库系统概论计算机网络操作系统双指针问题

最新文章

数据库系统概论ConcurrentHashMap计算机网络Java的其他Map双指针问题