【数据结构】Java集合框架：List与ArrayList

发布于：2025-09-13 ⋅ 阅读:(15) ⋅ 点赞:(0)

文章目录

一、认识List接口

1.1 List的定义与继承关系

在Java集合框架里，List是一个接口，它继承自Collection接口。而Collection接口又继承自Iterable接口，这就决定了List具备了Collection接口规范的常用方法，同时也拥有了可逐个元素遍历的特性。

从数据结构角度来看，List本质上是一个线性表，即由n个具有相同类型元素组成的有限序列。在这个序列上，我们可以进行元素的增删改查以及遍历等操作，这为数据的有序管理提供了便利。

1.2 Collection接口的核心方法

Collection接口作为List的父接口，定义了一系列容器常用方法，这些方法在List中也得到了实现和扩展，具体如下：

  • size()：返回集合中元素的个数，类型为int。
  • contains(Object o)：判断集合中是否包含指定元素o，返回值为boolean类型。
  • iterator()：返回一个用于遍历集合元素的Iterator对象。
  • toArray()：将集合中的元素转换为一个Object类型的数组。
  • toArray(T[] a)：将集合中的元素转换为指定类型T的数组。
  • add(E e)：向集合中添加元素e，添加成功返回true，否则返回false。
  • remove(Object o)：从集合中删除指定元素o，删除成功返回true，否则返回false。
  • containsAll(Collection<?> c)：判断集合是否包含另一个集合c中的所有元素，返回boolean类型。
  • addAll(Collection<? extends E> c)：将另一个集合c中的所有元素添加到当前集合中，添加成功返回true。
  • removeAll(Collection<?> c)：从当前集合中删除所有存在于集合c中的元素，删除成功返回true。
  • removeIf(Predicate<? super E> filter)：根据指定的过滤条件filter，删除集合中满足条件的元素，返回boolean类型。
  • retainAll(Collection<?> c)：保留当前集合中与集合c共有的元素，删除其他元素，操作成功返回true。
  • clear()：清空集合中的所有元素。
  • equals(Object o)：判断当前集合与指定对象o是否相等，返回boolean类型。
  • hashCode()：返回当前集合的哈希值。
  • spliterator()：返回一个用于分割集合元素的Spliterator对象。
  • stream()：返回一个用于遍历集合元素的顺序流Stream。
  • parallelStream()：返回一个用于并行遍历集合元素的并行流Stream。
  • isEmpty()：判断集合是否为空，返回boolean类型。

1.3 List接口的独特方法

除了继承自Collection接口的方法外，List接口还根据线性表的特性，新增了一些独特的方法，以满足对元素进行更精细操作的需求，常用方法如下表所示：

方法 解释
boolean add(E e) 在List的末尾插入元素e
void add(int index, E element) 将元素element插入到List中指定的index位置
boolean addAll(Collection<? extends E> c) 将集合c中的所有元素添加到List的末尾
E remove(int index) 删除List中index位置的元素，并返回被删除的元素
boolean remove(Object o) 删除List中遇到的第一个指定元素o，删除成功返回true
E get(int index) 获取List中下标为index位置的元素
E set(int index, E element) 将List中下标为index位置的元素设置为element，并返回该位置原来的元素
void clear() 清空List中的所有元素
boolean contains(Object o) 判断元素o是否存在于List中，存在返回true
int indexOf(Object o) 返回元素o在List中第一次出现的下标，若不存在则返回-1
int lastIndexOf(Object o) 返回元素o在List中最后一次出现的下标，若不存在则返回-1
List<E> subList(int fromIndex, int toIndex) 截取List中从fromIndex（包含）到toIndex（不包含）的部分元素，组成一个新的List返回

需要注意的是，List是一个接口，不能直接实例化使用。如果要使用List，必须实例化它的实现类，在Java集合框架中，ArrayList和LinkedList是List接口的常用实现类，本文后续将重点介绍ArrayList。

二、线性表与顺序表基础

在深入了解ArrayList之前，我们先来回顾一下线性表和顺序表的相关概念，这是理解ArrayList底层原理的基础。

2.1 线性表

线性表（linear list）是由n个具有相同特性的数据元素组成的有限序列，它是一种在实际应用中广泛使用的数据结构。常见的线性表包括顺序表、链表、栈、队列等。

线性表在逻辑上呈现为线性结构，就像一条连续的直线，元素之间存在着一对一的相邻关系。但在物理存储结构上，线性表并不一定是连续的，它通常以数组和链式结构这两种形式进行存储。

2.2 顺序表

顺序表是线性表的一种常见实现方式，它使用一段物理地址连续的存储单元来依次存储数据元素，一般情况下是通过数组来实现的。在顺序表中，我们可以基于数组完成数据的增删查改等操作。

自定义顺序表（MyArrayList）实现

1. 前期准备：自定义异常类

为了更清晰地处理“空表操作”和“非法索引”这两类错误，我们定义两个运行时异常（继承自RuntimeException）：

  • 空表异常：当操作空表时抛出
public class EmptyException extends RuntimeException {
    public EmptyException(String message) {
        super(message);
    }
}
  • 索引非法异常：当索引超出有效范围时抛出

public class PosIllegalException extends RuntimeException {
    public PosIllegalException(String message) {
        super(message);
    }
}

2. MyArrayList核心结构

首先定义顺序表的成员变量和构造方法，完成初始初始化：

import java.util.Arrays;

public class MyArrayList {
    // 1. 成员变量
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量（10）
    private int[] array; // 底层数组：存储数据
    private int size = 0; // 有效元素个数：初始为0（空表）

    // 2. 构造方法：默认初始化（容量10）
    public MyArrayList() {
        this.array = new int[DEFAULT_CAPACITY];
    }
}

3. 工具方法：简化重复逻辑

先实现两个通用工具方法，避免后续操作中重复编写边界校验代码：

（1）判断空表与容量满
  • 判断是否为空表
public boolean isEmpty() {
    return size == 0;
}
  • 判断容量是否已满
public boolean isFull() {
    return size == array.length;
}
（2）边界校验
  • 校验索引合法性：pos必须在 [0, size) 范围内
public void checkPos(int pos) throws PosIllegalException {
    if (pos < 0 || pos >= size) {
        throw new PosIllegalException("索引非法！当前有效元素个数：" + size + "，传入索引：" + pos);
    }
}
  • 校验是否为空表：空表不允许执行“获取元素”“删除元素”等操作
public void checkEmpty() throws EmptyException {
    if (isEmpty()) {
        throw new EmptyException("操作失败！当前顺序表为空");
    }
}
（3）动态扩容

当容量满（isFull() == true）时，通过Arrays.copyOf()将数组容量扩大为原来的2倍，实现“动态增长”：

public void grow() {
    // 扩容逻辑：新数组容量 = 原容量 * 2
    this.array = Arrays.copyOf(this.array, this.array.length * 2);
    System.out.println("扩容成功！新容量：" + this.array.length);
}

4. 核心功能实现：增删改查

（1）添加元素

添加元素分为两种场景：尾插（默认添加到表尾）和指定位置插入（插入到索引pos处）。

① 尾插 add(int e)

先判断是否满容量，满则扩容；再将元素放入array[size]，最后size++（有效元素个数+1）。

public void add(int e) {
    if (isFull()) {
        grow(); 
    }
    array[size] = e; 
    size++; 
}
② 指定位置插入 add(int pos, int e)

先校验索引合法性，再判断是否扩容；然后将[pos, size-1]的元素向后移动1位，最后在pos处放入元素并size++。

public void add(int pos, int e) {
    try {
        checkPos(pos); 
        if (isFull()) {
            grow(); 
        }
        // 元素后移：从最后一个元素（size-1）开始，到pos结束，依次向后移1位
        for (int i = size - 1; i >= pos; i--) {
            array[i + 1] = array[i];
        }
        array[pos] = e; 
        size++; 
    } catch (PosIllegalException e) {
        e.printStackTrace(); 
    }
}
（2）查询元素

查询分为两种场景：根据索引查元素（getElement(int pos)）和根据元素查索引（indexOf(int e)），以及判断元素是否存在（contains(int toFind)）。

① 根据索引查元素

先校验空表和索引合法性，再直接返回array[pos]（随机访问，O(1)）。

public int getElement(int pos) {
    try {
        checkEmpty(); 
        checkPos(pos);
        return array[pos]; 
    } catch (EmptyException | PosIllegalException e) {
        e.printStackTrace();
    }
    return -1; // 异常时返回默认值}
② 根据元素查索引

遍历[0, size-1]的元素，找到第一个匹配的元素并返回其索引；未找到则返回-1。

public int indexOf(int e) {
    for (int i = 0; i < size; i++) {
        if (array[i] == e) {
            return i;
        }
    }
    return -1;
}
③ 判断元素是否存在

复用indexOf()方法，若返回值 != -1则表示元素存在。

// 判断元素toFind是否在顺序表中
public boolean contains(int toFind) {
    return indexOf(toFind) != -1;
}
（3）修改元素（set(int pos, int e)）

先校验索引合法性，再直接将array[pos]赋值为新元素（O(1)操作）。

// 将索引pos处的元素修改为e
public void set(int pos, int e) {
    checkPos(pos); // 校验索引合法性
    array[pos] = e; // 直接修改
}
（4）删除元素（remove(int e)）

先校验空表，再通过indexOf()找到元素索引；若存在，将[pos+1, size-1]的元素向前移动1位，最后size--（有效元素个数-1）。

public void remove(int e) {
    try {
        checkEmpty(); 
        int pos = indexOf(e);
        if (pos == -1) {
            System.out.println("删除失败！元素" + e + "不存在");
            return;
        }
        // 元素前移：从pos+1开始，到size-1结束，依次向前移1位
        for (int i = pos; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--; 
    } catch (EmptyException e) {
        e.printStackTrace();
    }
}
（5）其他辅助功能
  • 清空顺序表：只需将size置为0（无需清空数组，后续添加会覆盖）
public void clear() {
    size = 0;
}
  • 打印顺序表所有元素
public void display() {
    try {
        checkEmpty(); // 校验是否空表
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println(); // 换行
    } catch (EmptyException e) {
        e.printStackTrace();
    }
}
  • 获取有效元素个数
public int getSize() {
    return size;
}

三、ArrayList详解

3.1 ArrayList的简介

ArrayList是Java集合框架中的一个普通类，它实现了List接口，同时还实现了RandomAccess、Cloneable和Serializable接口，这使得ArrayList具备了多种特性：

  1. 泛型实现：ArrayList是以泛型方式实现的，在使用时必须先进行实例化，指定要存储的元素类型，这样可以保证类型安全，避免在运行时出现类型转换异常。
  2. 支持随机访问：由于实现了RandomAccess接口，ArrayList支持通过下标快速访问元素，这也是ArrayList相较于LinkedList的一个重要优势。
  3. 可克隆：实现Cloneable接口表明ArrayList是可以被克隆的，我们可以通过调用clone()方法来创建一个ArrayList对象的副本。
  4. 可序列化：实现Serializable接口意味着ArrayList支持序列化操作，能够将对象转换为字节流进行传输或持久化存储，在需要的时候再将字节流恢复为对象。
  5. 线程不安全：与Vector不同，ArrayList不是线程安全的。在单线程环境下可以放心使用，而在多线程环境中，如果需要保证线程安全，可以选择使用Vector或者CopyOnWriteArrayList。
  6. 动态顺序表：ArrayList的底层是一段连续的存储空间，并且能够根据元素的添加情况进行动态扩容，本质上是一个动态类型的顺序表。

3.2 ArrayList的构造方法

ArrayList提供了三种常用的构造方法，以满足不同的创建需求，具体如下表所示：

方法 解释
ArrayList() 无参构造方法，创建一个初始容量为空的ArrayList对象，在后续添加元素时会进行动态扩容
ArrayList(Collection<? extends E> c) 利用其他实现了Collection接口的集合c来构建ArrayList，将集合c中的所有元素添加到新创建的ArrayList中
ArrayList(int initialCapacity) 指定ArrayList的初始容量initialCapacity，创建一个具有指定初始容量的ArrayList对象，这种方式可以在已知大致元素数量的情况下，减少后续扩容的次数，提高性能

下面通过代码示例来展示ArrayList的创建方式：

public static void main(String[] args) {
    // 构造一个空的ArrayList，推荐写法，指定存储Integer类型元素
    List<Integer> list1 = new ArrayList<>();

    // 构造一个初始容量为10的ArrayList
    List<Integer> list2 = new ArrayList<>(10);
    list2.add(1);
    list2.add(2);
    list2.add(3);
    // list2.add("hello"); // 编译失败，因为List<Integer>已限定只能存储Integer类型元素

    // 利用已有的list2构造list3，构造好之后list3与list2中的元素一致
    ArrayList<Integer> list3 = new ArrayList<>(list2);

    // 不推荐的写法，省略了元素类型，这样list4可以存储任意类型的元素，使用时容易出现问题
    List list4 = new ArrayList();
    list4.add("111");
    list4.add(100);
}

3.3 ArrayList的常见操作

ArrayList的常用操作方法与List接口中定义的方法基本一致，下面通过代码示例来演示这些方法的具体使用：

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    // 向list中添加元素
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add("测试课程");
    System.out.println(list); // 输出：[JavaSE, JavaWeb, JavaEE, JVM, 测试课程]

    // 获取list中有效元素的个数
    System.out.println(list.size()); // 输出：5

    // 获取和设置指定下标位置的元素，注意下标必须在[0, size)范围内
    System.out.println(list.get(1)); // 输出：JavaWeb
    list.set(1, "JavaWEB");
    System.out.println(list.get(1)); // 输出：JavaWEB

    // 在指定下标位置插入元素，该位置及后续元素会统一向后搬移一个位置
    list.add(1, "Java数据结构");
    System.out.println(list); // 输出：[JavaSE, Java数据结构, JavaWEB, JavaEE, JVM, 测试课程]

    // 删除指定元素，找到后删除，该元素之后的元素会统一向前搬移一个位置
    list.remove("JVM");
    System.out.println(list); // 输出：[JavaSE, Java数据结构, JavaWEB, JavaEE, 测试课程]

    // 删除指定下标位置的元素，注意下标不要超过有效元素个数，否则会抛出下标越界异常
    list.remove(list.size() - 1);
    System.out.println(list); // 输出：[JavaSE, Java数据结构, JavaWEB, JavaEE]

    // 检测list中是否包含指定元素，包含返回true，否则返回false
    if (list.contains("测试课程")) {
        list.add("测试课程");
    }
    System.out.println(list); // 输出：[JavaSE, Java数据结构, JavaWEB, JavaEE]（因为list中不包含"测试课程"，所以未添加）

    // 查找指定元素第一次和最后一次出现的位置
    list.add("JavaSE");
    System.out.println(list.indexOf("JavaSE")); // 输出：0（从前往后找）
    System.out.println(list.lastIndexOf("JavaSE")); // 输出：4（从后往前找）

    // 截取list中[0, 4)之间的元素，构成一个新的SubList返回，注意新列表与原列表共用同一个存储数组
    List<String> ret = list.subList(0, 4);
    System.out.println(ret); // 输出：[JavaSE, Java数据结构, JavaWEB, JavaEE]

    // 清空list中的所有元素
    list.clear();
    System.out.println(list.size()); // 输出：0
}

注意：

  1. remove方法可以通过传入元素或下标删除，构成重载。如果顺序表中存放的是整形，要通过元素进行移除，就要传入对象而非整形。
    例如：移除元素1
list.remove(new Integer(1));
  1. subList()只是拿到了列表的下标，返回的列表与原列表共用同一个存储数组。因此对返回的列表修改，也会改变原列表。
//list1={1,2,3,4,5}
List<Integer> list2 = list.subList(1,3);
list2.set(0,99);
System.out.println(list1);//输出{1,99,3,4,5}

3.4 ArrayList的遍历方式

ArrayList提供了三种常用的遍历方式，分别是for循环+下标、foreach循环以及使用迭代器，下面通过代码示例进行展示：

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
  • 方式一：使用下标+for循环遍历
    for (int i = 0; i < list.size(); i++) {
        System.out.print(list.get(i) + " ");
    }
    System.out.println(); // 输出：1 2 3 4 5
  • 方式二：借助foreach循环遍历
    for (Integer integer : list) {
        System.out.print(integer + " ");
    }
    System.out.println(); // 输出：1 2 3 4 5
  • 方式三：使用迭代器遍历
    Iterator<Integer> it = list.listIterator();//获取迭代器
    while (it.hasNext()){ //如果有下一个元素就向后移动，并打印
        System.out.print(it.next() + " ");
    }
    System.out.println(); // 输出：1 2 3 4 5 
}

在实际开发中，ArrayList最常用的遍历方式是for循环+下标和foreach循环。迭代器是一种设计模式，它提供了一种统一的遍历集合元素的方式，在后续接触更多容器时，会对迭代器有更深入的了解。

3.5 ArrayList的扩容机制

ArrayList是一个动态类型的顺序表，这意味着在向其中添加元素的过程中，如果底层的存储空间不足，它会自动进行扩容。下面我们通过分析ArrayList的源码来深入了解其扩容机制。

首先来看ArrayList中的一些关键成员变量：

// 用于存储元素的数组
Object[] elementData; 
// 默认的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 
// 默认的初始容量大小
private static final int DEFAULT_CAPACITY = 10;

当我们调用add(E e)方法向ArrayList中添加元素时，会首先调用ensureCapacityInternal(size + 1)方法来确保底层数组有足够的空间存储新元素，具体代码如下：

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保数组容量足够，size为当前元素个数
    elementData[size++] = e; // 将新元素添加到数组中，并将元素个数加1
    return true;
}

ensureCapacityInternal方法又会调用ensureExplicitCapacity方法，而ensureExplicitCapacity方法会先判断是否需要扩容，如果需要则调用grow方法进行扩容，代码如下：

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果当前数组是默认的空数组，返回默认初始容量（10）和minCapacity中的较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 记录集合结构修改的次数

    // 如果所需的最小容量大于当前数组的长度，说明需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow方法是ArrayList扩容的核心方法，它会根据当前数组的长度计算新的容量，并进行扩容操作，具体代码如下：

// 数组的最大容量，为Integer.MAX_VALUE - 8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // 获取当前数组的长度（旧容量）
    int oldCapacity = elementData.length;
    // 预计按照1.5倍的方式扩容（通过右移一位实现，相当于oldCapacity * 0.5）
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 如果计算出的新容量小于所需的最小容量，就将新容量设置为所需的最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 如果新容量超过了数组的最大容量，需要重新计算新容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // 调用Arrays.copyOf方法创建一个新的数组，并将原数组中的元素拷贝到新数组中，完成扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    // 如果所需的最小容量小于0，说明发生了内存溢出，抛出OutOfMemoryError异常
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 如果所需的最小容量大于数组的最大容量，返回Integer.MAX_VALUE，否则返回数组的最大容量
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

综合以上源码分析，我们可以将ArrayList的扩容机制总结为以下几个步骤：

  1. 检测扩容需求：在添加元素时，首先计算所需的最小容量，然后判断当前数组的容量是否能够满足该需求，如果不能则触发扩容操作。
  2. 计算新容量：
    • 初步预估新容量为当前容量的1.5倍（通过oldCapacity + (oldCapacity >> 1)计算）。
    • 如果预估的新容量小于所需的最小容量，就将新容量设置为所需的最小容量。
    • 在确定最终新容量之前，还会检测新容量是否超过了数组的最大容量（Integer.MAX_VALUE - 8），如果超过则根据所需最小容量的大小，将新容量设置为Integer.MAX_VALUE或数组的最大容量。
  3. 执行扩容：调用Arrays.copyOf方法创建一个具有新容量的数组，并将原数组中的元素拷贝到新数组中，从而完成扩容操作。

3.6 ArrayList的问题与思考

虽然ArrayList在很多场景下都非常实用，但它也存在一些问题：

  1. 插入删除效率低：由于ArrayList底层使用连续的存储空间，当在任意位置插入或删除元素时，需要将该位置后续的元素整体往前或往后搬移，这会导致插入和删除操作的时间复杂度为O(N)，在元素数量较多时，效率较低。
  2. 扩容消耗：当ArrayList需要扩容时，需要申请新的存储空间，将原数组中的元素拷贝到新数组中，然后释放旧的存储空间，这个过程会产生一定的系统开销。
  3. 空间浪费：ArrayList的扩容通常是按照当前容量的1.5倍进行的，这就可能导致一定的空间浪费。例如，当前容量为100，当元素填满后会扩容到200，如果之后只再插入5个元素，那么就会浪费95个元素的存储空间。

那么，如何解决这些问题呢？这就需要我们根据具体的业务场景选择合适的数据结构。例如，如果需要频繁进行插入和删除操作，可以考虑使用LinkedList，它通过链式存储结构，避免了元素的整体搬移，插入和删除操作的效率更高，但随机访问效率较低。在实际开发中，我们需要根据数据的操作特点，权衡各种数据结构的优缺点，选择最适合的方案。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布