Java 顺序表与 ArrayList 原理及操作详解

1. 线性表基础与顺序表定义

在深入学习具体代码前，需明确几个基本概念。线性表（Linear List）是 $N$ 个具有相同特性的数据元素的有限序列。虽然在逻辑上它是一条连续的直线，但在物理内存中并不一定连续存放。

顺序表则是线性表的一种典型实现，它采用一段物理地址连续的存储单元依次存储数据元素。在大多数编程语言（包括 Java）中，这种结构通常直接使用数组作为其底层载体，因为数组天然具备连续的内存地址。

2. 顺序表的底层实现分析

为了透彻理解顺序表的运作机制，我们可以通过自定义一个简化版的 ArrList 类来模拟其核心功能。该类需要维护两个核心属性：用于存储数据的底层层级数组（arr），以及用于标记当前实际元素数量的计数器（count）。

第 1 步：初始化顺序表框架

目的：建立顺序表的基础容器结构。
入口/动作：在构造函数中分配初始空间。
关键参数：设置默认的初始容量为 5。

public class ArrList {
    public int[] arr;
    public int count;
    
    public ArrList() {
        // 初始给 5 个大小空间
        this.arr = new int[5];
    }
}

第 2 步：实现数据增加逻辑

顺序表的增加操作分为尾部追加和指定位置插入。在此过程中，必须处理容量不足的情况。

2.1 尾部增加数据

操作逻辑：首先需要检查表是否已满（即 count 等于数组长度）。若已满，则调用扩容函数将容量翻倍；随后在新尾部存入数据并将计数器加 1。

public boolean isFull() {
    return this.count == this.arr.length;
}

public void tailAdd(int data) {
    // 判断是否需要扩容
    if (isFull()) {
        // 扩大为原来的两倍
        this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);
    }
    // 直接添加数据
    this.arr[this.count] = data;
    this.count++;
}

2.2 任意位置增加数据

操作逻辑：首先校验索引合法性（范围应在 [0, count] 之间）。若位置合法但表已满，需先扩容。如果是在非末尾位置插入，需要将目标位置及之后的所有元素向后移动一位，腾出空位后再赋值。

public void add(int index, int data) {
    // 校验索引合法性
    if (index < 0 || index > this.count) {
        throw new ArrayIndexOutOfBoundsException("位置非法");
    }
    
    // 容量检测与扩容
    if (isFull()) {
        this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);
    }
    
    // 区分末尾插入与非末尾插入
    if (index == this.count) {
        this.arr[this.count] = data;
    } else {
        // 核心移动步骤：从后往前移动，避免覆盖未移动的数据
        for (int i = this.count - 1; i >= index; i--) { 
            this.arr[i + 1] = this.arr[i];
        }
        this.arr[index] = data;
    }
    this.count++;
}

第 3 步：数据查找与修改

查找：find(int data)遍历数组比对数值，找到返回下标，找不到返回 -1。返回值使用 int 而非 boolean，是为了方便后续删除和修改操作复用此逻辑获取准确位置。

public int find(int data) {
    for (int i = 0; i < this.count; i++) {
        if (this.arr[i] == data) {
            return i;
        }
    }
    return -1;
}

修改：setIndex(int index, int data)直接根据传入的索引对数组进行重写。前提依然是确保索引在有效范围内 [0, count)。

public void setIndex(int index, int data) {
    if (index < 0 || index >= this.count) {
        throw new ArrayIndexOutOfBoundsException("位置非法");
    }
    this.arr[index] = data;
}

第 4 步：数据删除与清空

删除：delData(int data)先利用 find() 定位目标元素。若找到，则将删除点之后的所有元素向前覆盖一位，最后将计数器减 1。虽然原位置的值会被旧数据覆盖，但在重置计数器后该位置即不再被访问，无需专门置零。

清空：clear()只需将计数器 count 设为 0 即可。底层数组对象不会被销毁，下次添加数据时会复用已有的空间，这是一种节省内存开销的有效做法。

3. Java 标准库中的 ArrayList

在实际开发中，我们通常直接使用 Java 集合框架提供的 ArrayList。它是一个实现了 List 接口的泛型类，底层同样是数组结构。与上述手动实现的 ArrList 相比，ArrayList 增加了线程安全性缺失（非同步）、异常处理和更灵活的泛型支持等功能。

3.1 实例化与扩容机制

ArrayList 提供了三种主要的构造方式：

• ArrayList()：无参构造。默认初始化为 0，第一次调用增删方法时会自动扩容至 10。
• ArrayList(int initialCapacity)：指定初始容量。
• ArrayList(Collection<? extends E> c)：通过另一个集合构建列表。

当集合元素数量超过当前容量时，ArrayList 会将内部数组扩容为原来的 1.5 倍，这一过程由源码内部的方法（如 grow()）完成。

3.2 核心操作方法速查

以下是 ArrayList 最常用的 API 及其对应行为总结：

注意：截取操作（subList）返回的是原列表的一个视图（View），在截取的集合上的改变通常会反映在原集合上，使用时需注意并发修改异常风险。

4. 总结

掌握顺序表的手动实现有助于理解动态数组如何平衡内存分配与时间复杂度（插入删除平均 $O(N)$，查询 $O(1)$）。而在工程实践中，ArrayList 以其成熟的 API 和良好的性能成为了首选数据结构。以上关于 Java 顺序表原理与 ArrayList 用法的详细内容，更多关于 Java 集合框架的学习资料请关注本站其它相关文章！