List集合

BichonCode
• 阅读 1611

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

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
2年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“Java进阶架构师”,点击右上角,将我们设为★“星标”!这样才不会错过每日进阶架构文章呀。  !(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)  2
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
BichonCode
BichonCode
Lv1
不断充实自己
文章
9
粉丝
4
获赞
0