云计算百科
云计算领域专业知识百科平台

牢大带你学java数据结构--之list

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后,紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

一、引言:List 提供的是下标,坑也长在下标上

写购物车的时候,我一直以为自己理解 List。直到有一次要 "删掉数量为 2 的那件商品",写了这一行:

cart.remove(2);

运行完发现,数量为 2 的那件还在,第 3 条记录没了。

原因不复杂:List 里有两个 remove,remove(int) 删的是下标,remove(Object) 删的是对象。2 是 int 字面量,编译器选了前者。我脑子里想的是 "值 2",代码执行的是 "第 2 个位置"。

同样的事后来又犯了一次:想取 "前两件" 做满减,用了 cart.subList(0, 2),改完价格发现原列表的价格也变了—— 因为 subList 返回的是视图,不是拷贝。

这两个 bug 有一个共同点:都出在 "下标" 上。

List 相对 Collection 多出来的能力,说到底只有一件事:能按位置访问。有序、可重复、有下标,三个性质绑在一起。而一旦有了下标,就有了三种歧义:

  • 删的是位置还是对象——remove 的重载;
  • 拿到的是视图还是拷贝——subList;
  • 结构改了之后,旧引用还能不能用—— 遍历中增删会抛 ConcurrentModificationException。
  • 这篇按这三条走。

    环境说明:JDK 21 + IntelliJ IDEA,全部在 java.util 包下,示例单文件可运行。文中输出是按代码逻辑能推准的确定值,但代码没有在本机编译运行过(写文章这台机器没装 JDK)。

    二、List 在集合框架里的位置

    2.1 三层接口,各管一段

    Iterable -> Collection -> List

    • Iterable:只承诺一件事 —— 能用 for-each 遍历。它提供 iterator(),for-each 就是靠这个方法工作的;
    • Collection:单个元素的集合,管 "一共有几个、有没有某个元素、加一个、删一个、清空"。size()、contains()、add()、remove()、clear()、toArray() 都是它定的;
    • List:在 Collection 基础上加 "下标"——get(int)、set(int, E)、add(int, E)、remove(int)、indexOf()、lastIndexOf()、subList()、listIterator()。

    所以判断一个方法属于哪一层,有个简单的办法:跟位置有关的,都是 List 加的;跟 "有没有、有几个" 有关的,是 Collection 的。

    2.2 List 的三条性质

    性质

    含义

    和 Set 的差别

    有序

    按插入顺序排列,位置从 0 开始

    HashSet 不保证顺序

    可重复

    同一个值可以出现多次

    Set 不允许重复

    有下标

    能 get(i) / set(i, x)

    Set 没有下标访问

    还有一条容易忽略的:多数 List 实现允许存 null(ArrayList 可以),但 List.of(…) 不允许,传 null 直接 NullPointerException。接口本身没禁止,是实现决定的。

    2.3 接口不能 new

    List<String> cart = new List<>(); // 编译错误:List 是接口

    List<String> cart = new ArrayList<>(); // 正确:接口引用 + 实现类对象

    这么写不是绕远路,好处很实在:换实现类只改这一行,后面的方法调用一行都不用动。今天用 ArrayList,哪天发现 "头部频繁插入" 成了瓶颈,换成 LinkedList,调用方完全无感。

    实现 List 的类不止两个(还有 Vector、CopyOnWriteArrayList 等),日常用得多的是 ArrayList 和 LinkedList,它们的差别放在第六节。

    三、常用方法:按动作分类

    3.1 增:两个 add 返回值不一样

    list.add("苹果"); // 尾插,返回 boolean

    list.add(1, "西瓜"); // 插到下标 1,返回 void

    • add(E e) 返回 boolean。对可变 List 来说它恒为 true—— 接口这么设计是为了兼容 Set(Set.add 遇到重复会返回 false);
    • add(int index, E element) 返回 void,因为它一定会成功(除非下标越界,那会抛 IndexOutOfBoundsException)。

    下标可以取 0 到 size()(注意:插入时允许等于 size(),等于尾插;get / set 只允许到 size()-1)。

    3.2 删:remove 的重载是个真坑

    // 文件:RemoveTrapDemo.java
    import java.util.ArrayList;
    import java.util.List;

    public class RemoveTrapDemo {
    public static void main(String[] args) {
    // 场景一:按下标删
    List<Integer> numbers = new ArrayList<>();
    numbers.add(10);
    numbers.add(20);
    numbers.add(30);
    Integer removed = numbers.remove(1); // 选中的是 remove(int index)
    System.out.println("按下标删,返回被删元素:" + removed + ",剩余:" + numbers);

    // 场景二:按对象删
    List<Integer> numbers2 = new ArrayList<>();
    numbers2.add(10);
    numbers2.add(20);
    numbers2.add(30);
    boolean ok = numbers2.remove(Integer.valueOf(20)); // 选中的是 remove(Object)
    System.out.println("按对象删,返回是否删掉:" + ok + ",剩余:" + numbers2);

    // 场景三:直接写 remove(20),会被当成下标
    List<Integer> numbers3 = new ArrayList<>();
    numbers3.add(10);
    numbers3.add(20);
    numbers3.add(30);
    try {
    numbers3.remove(20); // 20 当下标用,越界
    } catch (IndexOutOfBoundsException ex) {
    System.out.println("remove(20) 报错:" + ex.getClass().getSimpleName());
    }
    }
    }

    运行结果:

    按下标删,返回被删元素:20,剩余:[10, 30]
    按对象删,返回是否删掉:true,剩余:[10, 30]
    remove(20) 报错:IndexOutOfBoundsException

    关键在编译器怎么选重载,规则是按参数的静态类型,不按你脑子里的意图:

    写法

    参数类型

    选中方法

    效果

    list.remove(1)

    int 字面量

    remove(int)

    删下标 1,返回元素

    list.remove(Integer.valueOf(1))

    Integer

    remove(Object)

    删第一个等于 1 的元素,返回布尔

    list.remove((Object) 1)

    Object

    remove(Object)

    同上

    list.remove(null)

    null

    remove(Object)

    删第一个 null

    所以 List<Integer> 里想 "按值删",必须显式装箱(remove(Integer.valueOf(x)))。List<String>、List<Item> 这类不会有这个问题,因为元素不是 int,remove(o) 只会匹配 remove(Object)。

    顺带记一下返回值:remove(int) 返回被删掉的那个元素,remove(Object) 返回有没有删成功。这两个返回值类型不同,是重载设计留下的历史痕迹。

    3.3 查与改:set 会返回旧值

    // 文件:ListBasicsDemo.java
    import java.util.ArrayList;
    import java.util.List;

    public class ListBasicsDemo {
    public static void main(String[] args) {
    List<String> cart = new ArrayList<>();
    cart.add("苹果"); // 尾插
    cart.add("香蕉");
    cart.add("橙子");
    System.out.println("插入前:" + cart);

    cart.add(1, "西瓜"); // 插到下标 1,后面的元素整体后移
    System.out.println("插到下标 1 后:" + cart + ",大小:" + cart.size());

    System.out.println("get(1):" + cart.get(1));

    String old = cart.set(0, "葡萄"); // 覆盖下标 0,返回被覆盖的旧值
    System.out.println("set 返回旧值:" + old + ",改完:" + cart);

    cart.add("葡萄"); // 再来一个同名元素
    System.out.println("加一个同名元素后:" + cart);
    System.out.println("indexOf(葡萄):" + cart.indexOf("葡萄"));
    System.out.println("lastIndexOf(葡萄):" + cart.lastIndexOf("葡萄"));
    System.out.println("contains(橙子):" + cart.contains("橙子"));

    List<String> firstTwo = cart.subList(0, 2); // 左闭右开:[0, 2)
    System.out.println("subList(0, 2):" + firstTwo);
    }
    }

    运行结果:

    插入前:[苹果, 香蕉, 橙子]
    插到下标 1 后:[苹果, 西瓜, 香蕉, 橙子],大小:4
    get(1):西瓜
    set 返回旧值:苹果,改完:[葡萄, 西瓜, 香蕉, 橙子]
    加一个同名元素后:[葡萄, 西瓜, 香蕉, 橙子, 葡萄]
    indexOf(葡萄):0
    lastIndexOf(葡萄):4
    contains(橙子):true
    subList(0, 2):[葡萄, 西瓜]

    三点值得记:

    • set 返回旧值,这个返回值不是没用的:做撤销时正好拿它回滚;
    • indexOf 从前往后找第一个,lastIndexOf 从后往前找,找不到都返回 -1;
    • subList(from, to) 是左闭右开,subList(0, 2) 取下标 0、1 两个元素,不包含 2。

    add(int, E) 有一个代价:后面的元素要整体后移一位。这是数组结构的必然结果,插入位置越靠前,代价越大。

    3.4 遍历中删除:for-each 会炸

    // 文件:IteratorRemoveDemo.java
    import java.util.ArrayList;
    import java.util.ConcurrentModificationException;
    import java.util.Iterator;
    import java.util.List;

    public class IteratorRemoveDemo {
    public static void main(String[] args) {
    // 错误示范:for-each 里直接删
    List<String> names = new ArrayList<>(List.of("张三", "李四", "王五", "赵六"));
    try {
    for (String name : names) {
    if (name.equals("李四")) {
    names.remove(name);
    }
    }
    } catch (ConcurrentModificationException ex) {
    System.out.println("for-each 里删除:" + ex.getClass().getSimpleName());
    }
    System.out.println("异常后列表:" + names);

    // 正确示范一:迭代器自己的 remove
    List<String> names2 = new ArrayList<>(List.of("张三", "李四", "王五", "赵六"));
    Iterator<String> it = names2.iterator();
    while (it.hasNext()) {
    String name = it.next();
    if (name.equals("李四")) {
    it.remove();
    }
    }
    System.out.println("迭代器删除后:" + names2);

    // 正确示范二:removeIf(JDK 8 起)
    names2.removeIf(name -> name.startsWith("赵"));
    System.out.println("removeIf 之后:" + names2);
    }
    }

    运行结果:

    for-each 里删除:ConcurrentModificationException
    异常后列表:[张三, 王五, 赵六]
    迭代器删除后:[张三, 王五, 赵六]
    removeIf 之后:[张三, 王五]

    两个细节:

  • 抛异常之前,删除其实已经生效了。所以 异常后列表 里已经没有 "李四",但迭代器已经废了,剩下的元素没遍历到 —— 这类 "一半成功一半失败" 的状态最难查。
  • Iterator.remove() 是唯一允许的 "边遍历边删" 的方式,因为它会同步迭代器内部的计数。removeIf 更省事,内部就是按这个思路做的。
  • 机制上,ArrayList 内部有个 modCount,每次结构性修改(增、删、清空)就 +1;迭代器创建时记下当前值,每次 next() 前对比,不一致就抛 ConcurrentModificationException。这叫 fail-fast,是 "尽力而为" 的检查,不是线程安全保证。

    3.5 常用方法速查

    方法

    作用

    返回值

    add(E e)

    尾插

    boolean(可变 List 恒 true)

    add(int index, E e)

    插到指定位置

    void

    addAll(Collection<? extends E> c)

    尾插一批

    boolean

    remove(int index)

    删指定下标

    E(被删元素)

    remove(Object o)

    删第一个匹配对象

    boolean

    get(int index)

    取指定下标

    E

    set(int index, E e)

    覆盖指定下标

    E(旧值)

    clear()

    清空

    void

    contains(Object o)

    是否包含

    boolean

    indexOf(Object o)

    第一个匹配的下标

    int(无则 -1)

    lastIndexOf(Object o)

    最后一个匹配的下标

    int(无则 -1)

    subList(int from, int to)

    截取子列表(左闭右开)

    List<E>(视图)

    四、subList 是视图,不是拷贝

    4.1 改子列表会回写原列表

    // 文件:SubListDemo.java
    import java.util.ArrayList;
    import java.util.ConcurrentModificationException;
    import java.util.List;

    public class SubListDemo {
    public static void main(String[] args) {
    List<String> cart = new ArrayList<>();
    cart.add("苹果");
    cart.add("香蕉");
    cart.add("橙子");
    cart.add("西瓜");

    // subList 返回的是"视图",不是新列表
    List<String> firstTwo = cart.subList(0, 2);
    System.out.println("视图内容:" + firstTwo);

    firstTwo.set(0, "葡萄"); // 改视图
    System.out.println("改视图后,原列表:" + cart);

    firstTwo.clear(); // 清空视图
    System.out.println("清空视图后,原列表:" + cart);

    // 原列表结构一变,之前拿到的视图就失效了
    List<String> view = cart.subList(0, cart.size());
    cart.add("柠檬"); // 结构性修改
    try {
    System.out.println(view.get(0));
    } catch (ConcurrentModificationException ex) {
    System.out.println("旧视图失效:" + ex.getClass().getSimpleName());
    }
    }
    }

    运行结果:

    视图内容:[苹果, 香蕉]
    改视图后,原列表:[葡萄, 香蕉, 橙子, 西瓜]
    清空视图后,原列表:[橙子, 西瓜]
    旧视图失效:ConcurrentModificationException

    subList 返回的对象内部记着 "原列表 + 偏移量 + 长度",它的 get、set、clear 都是在原列表上操作。所以:

    • set 改的是原列表对应位置;
    • clear 删的是原列表对应那一段;
    • 它不占额外内存,但也不给你数据隔离。

    这个设计有它的用途 ——list.subList(0, 5).clear() 是 "删掉前 5 个" 的标准写法,比循环删快得多。但要当独立副本用的时候,必须自己复制一份:

    List<String> copy = new ArrayList<>(cart.subList(0, 2));

    4.2 视图的 "有效期"

    视图本身不检查原列表有没有变,直到你调用它的方法 —— 那时它会对比 modCount,发现被改过就抛 ConcurrentModificationException。也就是说,视图的失效是延迟发现的,错误会出现在离原因很远的地方。

    实际写代码时的处理原则很简单:

    • 只读、临时看几眼,直接用 subList;
    • 要传出去、要存起来、要被别人改,一律 new ArrayList<>(…) 复制。

    五、不可变列表与 equals 语义

    5.1 三种 "看起来是 List,其实不能随便改" 的东西

    // 文件:ImmutableListDemo.java
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;

    public class ImmutableListDemo {
    public static void main(String[] args) {
    // Arrays.asList:固定长度,能改元素,不能增删
    List<String> fixed = Arrays.asList("苹果", "香蕉", "橙子");
    fixed.set(0, "葡萄");
    System.out.println("改元素后:" + fixed);
    try {
    fixed.add("西瓜");
    } catch (UnsupportedOperationException ex) {
    System.out.println("asList 加元素:" + ex.getClass().getSimpleName());
    }

    // 它背后是原数组,改视图会改到数组
    String[] arr = {"A", "B"};
    List<String> arrView = Arrays.asList(arr);
    arrView.set(0, "X");
    System.out.println("原数组第一个元素:" + arr[0]);

    // List.of:完全不可变,连 set 都不行
    List<String> immutable = List.of("苹果", "香蕉", "橙子");
    try {
    immutable.set(0, "葡萄");
    } catch (UnsupportedOperationException ex) {
    System.out.println("List.of 改元素:" + ex.getClass().getSimpleName());
    }

    // 要可变,复制一份
    List<String> mutable = new ArrayList<>(List.of("苹果", "香蕉", "橙子"));
    mutable.add("西瓜");
    System.out.println("复制出来可以改:" + mutable);
    }
    }

    运行结果:

    改元素后:[葡萄, 香蕉, 橙子]
    原数组第一个元素:X
    asList 加元素:UnsupportedOperationException
    List.of 改元素:UnsupportedOperationException
    复制出来可以改:[苹果, 香蕉, 橙子, 西瓜]

    三者的区别:

    来源

    能否 set

    能否 add / remove

    备注

    Arrays.asList(…)

    能

    不能

    背后是原数组,set 会回写数组

    List.of(…)

    不能

    不能

    JDK 9 起,且不接受 null

    new ArrayList<>(…)

    能

    能

    真正的可变副本

    Arrays.asList 那个 "固定长度" 不是 bug,它返回的是数组的包装视图,长度由数组决定,所以不能增删。这个类在把数组转成集合传给方法时很常见,踩坑率也高。

    5.2 indexOf / contains / remove(Object) 全靠 equals

    // 文件:EqualsTrapDemo.java
    import java.util.ArrayList;
    import java.util.List;

    class Item {
    String name;

    Item(String name) {
    this.name = name;
    }

    @Override
    public String toString() {
    return name;
    }
    }

    class ItemWithEquals {
    String name;

    ItemWithEquals(String name) {
    this.name = name;
    }

    @Override
    public boolean equals(Object o) {
    if (this == o) {
    return true;
    }
    if (!(o instanceof ItemWithEquals)) {
    return false;
    }
    return name.equals(((ItemWithEquals) o).name);
    }

    @Override
    public int hashCode() {
    return name.hashCode();
    }

    @Override
    public String toString() {
    return name;
    }
    }

    public class EqualsTrapDemo {
    public static void main(String[] args) {
    // 没重写 equals:两个"同名"对象被当成不同对象
    List<Item> a = new ArrayList<>();
    a.add(new Item("苹果"));
    System.out.println("未重写 equals contains:" + a.contains(new Item("苹果")));
    System.out.println("未重写 equals indexOf:" + a.indexOf(new Item("苹果")));

    // 重写 equals 之后
    List<ItemWithEquals> b = new ArrayList<>();
    b.add(new ItemWithEquals("苹果"));
    System.out.println("重写后 contains:" + b.contains(new ItemWithEquals("苹果")));
    System.out.println("重写后 indexOf:" + b.indexOf(new ItemWithEquals("苹果")));
    System.out.println("重写后 remove:" + b.remove(new ItemWithEquals("苹果")) + ",剩余:" + b);
    }
    }

    运行结果:

    未重写 equals contains:false
    未重写 equals indexOf:-1
    重写后 contains:true
    重写后 indexOf:0
    重写后 remove:true,剩余:[]

    List 里所有 "按对象" 的操作 ——contains、indexOf、lastIndexOf、remove(Object)—— 内部都是逐个调用 equals 比较。没重写 equals 时,用的是 Object 的默认实现,比的是 "是不是同一个对象",所以两个内容相同的新对象永远不相等。

    这也解释了一个常见困惑:从数据库查出来两条内容一样的记录,list.remove(另一条) 删不掉,因为那是两个不同对象。

    重写 equals 时必须连带重写 hashCode。List 只用 equals,但同一个对象放进 HashSet 或当 HashMap 的 key 时,hashCode 不对会导致 "明明相等却找不到"。这是另一个坑,这里先记一句。

    六、ArrayList 与 LinkedList 怎么选

    两者都实现 List,接口行为一致,差别在底层:

    操作

    ArrayList

    LinkedList

    get(i) / set(i, x)

    O (1)(数组下标直接定位)

    O (n)(要从头 / 尾走过去)

    尾部 add

    均摊 O (1),扩容时要整体拷贝

    O(1)

    头部 add(0, x)

    O (n),所有元素后移

    O(1)

    remove(0)

    O(n)

    O(1)

    额外内存

    数组 + 预留容量

    每个元素一个节点对象(前后指针)

    选法很简单:

    • 绝大多数场景用 ArrayList。真实业务里 "按下标取、尾部追加" 占九成,ArrayList 在这两件事上都不差;LinkedList 的 get(i) 是 O (n),一不小心在循环里写 get(i),复杂度直接从 O (n) 变成 O (n²)。
    • 只有频繁在头尾增删、几乎不按下标访问的场景(比如拿它当队列用),才轮到 LinkedList。

    记住一句就够:LinkedList 快的是 "改链表结构",慢的是 "找第 i 个"。

    七、总结

    • List 比 Collection 多的就是下标:有序、可重复、能按位置读写。
    • remove 有两个重载:remove(int) 删下标、返回元素;remove(Object) 删对象、返回布尔。List<Integer> 按值删要写 remove(Integer.valueOf(x))。
    • set 返回旧值;indexOf 从左找、lastIndexOf 从右找,找不到返回 -1;subList(from, to) 左闭右开。
    • 遍历中删除必须用 Iterator.remove() 或 removeIf,for-each 直接删会抛 ConcurrentModificationException,而且删除往往已经生效了一半。
    • subList 是视图:改它会回写原列表,原列表结构一变它就失效。要独立副本就 new ArrayList<>(…)。
    • Arrays.asList 固定长度(能 set 不能增删)、List.of 完全不可变、要可变就复制一份。
    • contains / indexOf / remove(Object) 全靠 equals,自定义类不重写就找不到。

    自测题

  • List<Integer> list = new ArrayList<>(List.of(10, 20, 30)); 执行 list.remove(1) 之后,list 的内容是:
  • A. [10, 20]

    B. [10, 30]

    C. [20, 30]

    D. 抛异常

  • list.subList(0, 2) 返回的是什么?对它的修改会影响原列表吗?
  • 下面这段代码为什么会抛异常?
  • for (String s : list) {

    if (s.equals("x")) {

    list.remove(s);

    }

    }

  • 判断对错:
  • ① List.of("a", "b").add("c") 会抛 UnsupportedOperationException

    ② Arrays.asList(…) 返回的列表可以 add 元素

    ③ 自定义类没重写 equals 时,list.contains(同内容的新对象) 返回 false

    答案

  • B
  • 返回的是视图,修改会回写到原列表
  • for-each 用的是迭代器,遍历中修改列表结构会触发 fail-fast 检查
  • ① true ② false ③ true
  • 赞(0)
    未经允许不得转载:网硕互联帮助中心 » 牢大带你学java数据结构--之list
    分享到: 更多 (0)

    评论 抢沙发

    评论前必须登录!