在开发中我们经常要处理“一组有序数据”的存储问题比如学生成绩表、商品列表、任务队列。最容易想到的方式就是使用数组但数组的长度固定、增删元素麻烦用起来并不顺手。数据结构中的“顺序表”正是在数组基础上封装出来的一种线性表它既保留了数组随机访问快的优势又解决了容量固定、插入删除需要手动搬移数据的痛点。本文将以 Java 语言为例从顺序表的定义出发完整实现初始化、插入、删除、查找、扩容等核心操作并给出可直接运行的完整代码和测试用例。无论你是正在学习数据结构课程还是准备面试、复习算法基础这篇文章都能帮你把顺序表这一章彻底吃透。1. 背景与核心概念1.1 线性表是什么在系统学习顺序表之前首先要理解“线性表”这个概念。线性表是具有相同数据类型的 n 个数据元素的有限序列比如一个班级的学生名单、一串电话号码记录都可以抽象成线性表。线性表中每个元素都有唯一的前驱和后继除了第一个元素没有前驱、最后一个元素没有后继之外其他元素都“手拉手”排成一条直线这种逻辑结构非常直观。线性表的存储方式主要有两种。一种是顺序存储用一组地址连续的内存单元依次存放数据元素这种实现就是顺序表另一种是链式存储通过指针把散落在内存各处的节点串起来这种实现就是链表。在真实项目中两种方式都有大量应用但对于“按位置访问”特别频繁、很少在中间插入删除的场景顺序表的效率远高于链表。这也是为什么我们要先把顺序表吃透。1.2 顺序表解决什么问题顺序表本质上是一段连续的物理存储空间通常用“数组 当前长度”两个属性来描述。它解决的问题可以归纳成三个第一容量的动态管理。静态数组在使用前必须确定大小如果估计少了数据存不下估计多了又浪费内存。顺序表通过扩容机制解决了这个问题在空间不足时自动申请更大的数组并把原数据搬移过去。第二数据的有序组织。顺序表让元素按照逻辑顺序紧密排列通过下标可以直接访问任意位置的元素。比如要访问第 3 个元素数组下标就是 2一步到位。第三常用操作的标准化。初始化、插入、删除、查找、遍历、清空这些操作被封装成方法或函数使用时不需要关心内部细节。这样写业务代码时可以像使用工具一样操作数据集合而不用手动管理底层数组。1.3 顺序表和数组、链表的区别初学者最容易把数组和顺序表混为一谈。数组是编程语言提供的一种基本语法结构长度固定只能由程序员手动处理增删逻辑。顺序表是建立在数组之上的抽象数据结构它把数组的固定长度和增删逻辑封装起来形成一个具备“自动扩容、边界检查、标准接口”的数据容器。在学习时可以把顺序表想象成一个“升级版数组”。和链表相比顺序表的特点是“内存连续、随机访问快、插入删除慢”。链表正好相反它不要求内存连续插入删除只需要修改指针但随机访问必须从头遍历。实际项目中选型时要根据业务特点决定。如果读多写少优先考虑顺序表如果频繁在中间插入删除链表可能更合适。2. 环境准备与代码结构2.1 运行环境说明本文所有代码使用 Java 语言实现在本地开发时建议准备以下环境JDK 8 及以上版本本文代码使用了泛型和增强 for 循环等基础特性JDK 8 完全可以运行。任意 Java IDE例如 IntelliJ IDEA、Eclipse或者直接用记事本配合命令行编译运行。使用命令行时请确认java -version和javac -version能正常输出版本信息。版本需要根据你的项目实际情况调整本文示例以常见环境为例重点演示配置思路和代码实现。2.2 项目文件结构示例工程采用最简单的单类结构目的是让读者把注意力集中到数据结构本身而不是被 Maven 或 Gradle 的工程结构干扰。实际项目中使用时可以把顺序表类放到独立的datastructure包中方便统一管理。顺序表演示项目/ ├── src/ │ └── SqList.java 顺序表完整实现 │ └── SqListTest.java 测试入口类SqList是顺序表的核心类包含成员变量和所有操作方法SqListTest是测试类用于验证功能。2.3 使用到的 Java 技术点在阅读代码前先了解几个关键的 Java 技术点泛型。通过泛型可以让顺序表支持任意数据类型而不只是int。本文为了降低上手难度先用int类型演示核心逻辑最后补充泛型化的改造思路。可变参数。部分初始化方法可以使用可变参数便于一次性添加多个元素。数组拷贝。扩容时需要把原数组的数据复制到新数组可以使用循环逐位复制也可以使用System.arraycopy提高效率。代码中会尽量避免使用过于高级的语法保证基础薄弱的读者也能看懂。3. 顺序表的核心设计原理3.1 顺序表的存储结构顺序表的逻辑结构是“一对一”的线性关系物理结构是连续内存空间。它的定义可以概括为用一组地址连续的存储单元依次存放线性表中的数据元素元素之间的逻辑关系通过它们在内存中的物理位置自然表达。在 Java 中我们使用数组作为底层存储结构再加上一个size变量记录当前元素个数。这里有个容易混淆的地方数组的容量capacity和顺序表的长度size是不同的概念。容量是数组最多能放多少个元素长度是当前实际存放了多少个元素。判断顺序表是否为空看的是size是否为 0而不是容量是否为 0。private int[] data; // 底层数组 private int size; // 当前元素个数data用来存放元素size指向下一个要写入的位置同时也是当前元素个数。初始化时分配一个默认容量的数组size置为 0。3.2 为什么需要扩容机制数组一旦创建长度就不可变。如果顺序表在元素插入时发现数组已满继续写入就会导致数组下标越界。扩容机制的思路是在插入前判断是否还有剩余空间如果没有申请一个更大的新数组把原数组元素全部搬移过去然后让data指向新数组。扩容的容量策略在真实项目中很有讲究。最简单的是“每次增加一个固定大小”比如每次多分配 10 个空间更通用的是“原容量翻倍”或者“增加原容量的一半”。容量翻倍的好处是均摊下来每次插入的时间复杂度为 O(1)不会出现多次扩容的抖动问题。Java 的ArrayList在扩容时默认策略是oldCapacity (oldCapacity 1)也就是增加原来容量的一半。本文会采用这个策略作为演示。3.3 插入操作的核心思想插入操作比较容易出错的点在于元素搬移。如果要在第index个位置插入元素那么从index到size-1的所有元素都必须往后挪动一位空出第index个位置再把新元素写入。这里必须强调一个关键细节搬移元素时必须从最后一个元素开始从后向前依次移动。如果从前往后移动后面的元素还没有被搬走就直接被前一个元素覆盖导致数据丢失。这种“从后往前搬”的规则是顺序表插入操作最常见的考点。// 从后往前搬移元素 for (int i size - 1; i index; i--) { data[i 1] data[i]; }插入前还需要判断下标是否合法。合法范围是0到size。如果index等于size相当于在表尾追加元素如果超出这个范围应该抛出下标越界异常。3.4 删除操作的核心思想删除操作和插入操作方向相反。删除第index个元素后从index1到size-1的元素都必须往前挪动一位填补被删除元素留下的空位。搬移元素时必须从前往后移动。这正好和插入操作相反for (int i index; i size - 1; i) { data[i] data[i 1]; }删除完成后size减 1。这里还有一个性能优化点末尾的废弃数据可以置为默认值帮助垃圾回收。对于基本数据类型int可以置为 0对于对象类型可以置为null。删除操作的时间主要消耗在元素搬移上平均要移动n/2次所以时间复杂度是 O(n)。3.5 查找操作的设计查找可以分成两种。第一种是按位置查找给定下标返回元素顺序表支持随机访问时间复杂度是 O(1)。第二种是按值查找需要遍历整个顺序表找到第一个与目标值相等的元素并返回其下标时间复杂度是 O(n)。按值查找在真实项目中非常常见。比如在成绩表里找到 90 分以上的第一个学生或者在订单表里定位某个订单号。实现时要注意两个点第一如果找不到要有一个统一的返回值约定比如返回-1表示不存在第二在泛型场景下比较元素时要使用equals而不是否则比较的是引用地址而不是内容。4. 顺序表完整 Java 实现4.1 类的成员与构造方法先来定义顺序表类的基本结构// 文件路径src/SqList.java public class SqList { private int[] data; // 底层数组 private int size; // 当前元素个数 // 默认构造方法初始化容量为 10 public SqList() { data new int[10]; size 0; } // 指定初始容量构造方法 public SqList(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数); } data new int[capacity]; size 0; } }默认容量设置为 10这样既不会在刚创建时就占用大量内存又能满足一般的小规模数据需求。第二个构造方法允许调用者按照预估的数据量分配初始空间减少后续扩容次数。4.2 基本成员方法包括获取长度、判断是否为空、按位置访问元素、修改元素// 获取当前元素个数 public int size() { return size; } // 判断顺序表是否为空 public boolean isEmpty() { return size 0; } // 按位置获取元素 public int get(int index) { checkIndexForGet(index); return data[index]; } // 修改指定位置的元素 public void set(int index, int value) { checkIndexForGet(index); data[index] value; } // 检查按位置访问时下标是否合法 private void checkIndexForGet(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } }get和set都是 O(1) 的随机访问操作这也是顺序表相对链表最核心的优势。检查下标的代码被抽取成私有方法避免重复编写同时让外部调用时能立即得到清晰的异常信息。4.3 扩容方法扩容是顺序表内部的基础能力被插入操作调用。虽然写成public也不会报错但合理的设计应该把扩容声明为private因为扩容属于内部机制不应该暴露给调用者。// 确保数组有足够的容量 private void ensureCapacity() { if (size data.length) { return; } // 扩容策略原容量 原容量的一半 int newCapacity data.length (data.length 1); if (newCapacity data.length) { newCapacity 10; } int[] newData new int[newCapacity]; // 搬移原数组数据 for (int i 0; i size; i) { newData[i] data[i]; } data newData; }这里的data.length 1相当于data.length / 2用移位运算比除法运算效率更高。扩容后原来的数组失去引用由 JVM 垃圾回收机制自动回收。工程实践中如果知道数据量会持续增长也可以在调用插入时手动触发一次较大容量的扩容减少多次扩容带来的性能开销。4.4 插入操作实现插入操作支持在任意合法位置插入新元素。插入位置可以是表头、表中或者表尾。// 在指定位置插入元素 public void insert(int index, int value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置非法: index); } ensureCapacity(); // 从后往前搬移元素腾出位置 for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] value; size; } // 在表尾追加元素 public void add(int value) { ensureCapacity(); data[size] value; size; }在表尾追加元素是插入的一种特殊情况单独提供add方法会让调用更加简洁。每次插入完都要记得size漏掉这一步会导致后续读写错位也是最常见的低级错误。为了验证插入逻辑可以看一个简单例子。假设数组中已有元素[1, 2, 3, 4]要在下标 1 的位置插入9。首先从后往前搬移下标 3 的4移到下标 4下标 2 的3移到下标 3下标 1 的2移到下标 2然后下标 1 写入9。最终数组变为[1, 9, 2, 3, 4]完全符合预期。4.5 删除操作实现删除操作接收一个下标返回被删除的元素值。返回被删除的元素在某些业务场景中很有用比如需要记录日志或做撤销操作。// 删除指定位置的元素并返回被删除的元素 public int remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置非法: index); } int oldValue data[index]; // 从前往后搬移元素覆盖被删除位置 for (int i index; i size - 1; i) { data[i] data[i 1]; } size--; // 将末尾废弃位置置为 0帮助释放引用对基本类型是可选操作 data[size] 0; return oldValue; }从前往后搬移是删除操作的正确姿势。如果从后往前搬移前一个元素会被后一个元素覆盖导致数据混乱。4.6 查找与遍历按值查找返回第一个匹配元素的下标如果找不到返回-1。判断容器中是否包含某个元素可以基于查找方法实现// 按值查找返回第一个匹配的下标找不到返回 -1 public int indexOf(int value) { for (int i 0; i size; i) { if (data[i] value) { return i; } } return -1; } // 判断是否包含目标值 public boolean contains(int value) { return indexOf(value) ! -1; } // 遍历打印所有元素 public void print() { System.out.print([); for (int i 0; i size; i) { System.out.print(data[i]); if (i ! size - 1) { System.out.print(, ); } } System.out.println(]); }print方法方便在测试时观察顺序表的内部状态。注意打印遍历时循环条件是i size而不是i data.length。否则会把未使用的扩容空间也打印出来。4.7 清空与判空清空操作只重置size不要求立即释放数组内存。这样即使扩容后的数组被保留再次添加元素时也能避免立刻扩容空间可以复用。// 清空顺序表 public void clear() { size 0; }对于对象类型的顺序表清空时最好把数组中每个引用都置为null否则会出现“对象无法被垃圾回收”的内存隐患。基本类型数组则没有这个问题。4.8 完整代码汇总把上面的方法组合到一起形成完整的SqList.java类。// 文件路径src/SqList.java public class SqList { private int[] data; private int size; public SqList() { data new int[10]; size 0; } public SqList(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数); } data new int[capacity]; size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } return data[index]; } public void set(int index, int value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } data[index] value; } private void ensureCapacity() { if (size data.length) { return; } int newCapacity data.length (data.length 1); int[] newData new int[newCapacity]; for (int i 0; i size; i) { newData[i] data[i]; } data newData; } public void insert(int index, int value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置非法: index); } ensureCapacity(); for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] value; size; } public void add(int value) { ensureCapacity(); data[size] value; size; } public int remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置非法: index); } int oldValue data[index]; for (int i index; i size - 1; i) { data[i] data[i 1]; } size--; data[size] 0; return oldValue; } public int indexOf(int value) { for (int i 0; i size; i) { if (data[i] value) { return i; } } return -1; } public boolean contains(int value) { return indexOf(value) ! -1; } public void print() { System.out.print([); for (int i 0; i size; i) { System.out.print(data[i]); if (i ! size - 1) { System.out.print(, ); } } System.out.println(]); } public void clear() { size 0; } }5. 测试与运行验证5.1 编写测试类顺序表类写完以后需要编写测试类验证功能是否正常。测试类覆盖了插入、删除、查找、修改、遍历等核心操作每个操作之间通过打印结果来检验正确性。// 文件路径src/SqListTest.java public class SqListTest { public static void main(String[] args) { // 1. 创建一个顺序表 SqList list new SqList(); System.out.println(初始是否为空 list.isEmpty()); // 2. 尾部追加元素 list.add(10); list.add(20); list.add(30); list.add(40); System.out.print(尾部追加 10,20,30,40 后); list.print(); // 3. 指定位置插入 list.insert(1, 15); System.out.print(在下标 1 插入 15 后); list.print(); // 4. 按位置查找和修改 System.out.println(下标 2 的元素是 list.get(2)); list.set(0, 100); System.out.print(将下标 0 修改为 100 后); list.print(); // 5. 按值查找 System.out.println(元素 30 的下标是 list.indexOf(30)); System.out.println(是否包含 99 list.contains(99)); // 6. 删除操作 int removed list.remove(1); System.out.println(删除的元素是 removed); System.out.print(删除后); list.print(); // 7. 清空操作 list.clear(); System.out.println(清空后是否为空 list.isEmpty()); } }5.2 编译运行在命令行进入src目录依次执行编译和运行命令javac SqList.java SqListTest.java java SqListTest使用 IDE 开发时直接运行SqListTest类中的main方法即可。5.3 预期输出结果运行程序后控制台输出如下初始是否为空true 尾部追加 10,20,30,40 后[10, 20, 30, 40] 在下标 1 插入 15 后[10, 15, 20, 30, 40] 下标 2 的元素是20 将下标 0 修改为 100 后[100, 15, 20, 30, 40] 元素 30 的下标是3 是否包含 99false 删除的元素是15 删除后[100, 20, 30, 40] 清空后是否为空true输出结果和预期完全一致。这里需要特别说明set(0, 100)之后indexOf(30)的结果仍然是 3。因为删除操作发生在查找之后此时顺序表为[100, 15, 20, 30, 40]元素 30 位于下标 3。5.4 扩容能力测试为了验证扩容机制是否正常工作可以专门写一个循环添加大量数据的测试// 扩容测试连续添加 100 个元素 SqList bigList new SqList(5); for (int i 0; i 100; i) { bigList.add(i); } System.out.println(扩容后元素个数 bigList.size()); System.out.println(扩容后下标 99 的元素 bigList.get(99));初始容量只有 5但需要存储 100 个元素因此会触发多次扩容。只要最后能输出元素个数 100并且get(99)返回 99就证明扩容机制正常工作。6. 复杂度分析与性能边界6.1 时间复杂度分析顺序表各操作的时间复杂度如下表所示操作平均时间复杂度说明按下标访问getO(1)直接通过数组下标定位修改元素setO(1)直接通过数组下标定位尾部插入addO(1)均摊分析下扩容次数少任意位置插入insertO(n)需要移动 n/2 个元素删除removeO(n)需要移动 n/2 个元素按值查找indexOfO(n)需要遍历数组判断包含containsO(n)依赖 indexOf从表中可以看到顺序表的强项是随机访问和尾部的增删弱项是中间位置的插入删除和按值查找。6.2 空间复杂度分析顺序表的空间复杂度为 O(n)因为底层数组需要为所有元素分配连续内存。在 real-time 场景中扩容会瞬间申请一份更大的内存如果顺序表存储的是大量对象引用扩容时的内存开销会比较明显。为了避免频繁扩容创建顺序表时可以根据业务大小给出合理的初始容量例如预估 1000 条数据就初始化new SqList(1000)。6.3 顺序表适合的场景从复杂度分析可以看出顺序表最擅长处理以下场景需要频繁按下标读取元素的场景比如排行榜、缓存队列。数据量相对稳定、增长不剧烈的场景。主要在尾部添加和删除数据的场景比如程序运行日志的暂存或者栈的实现。如果业务中需要频繁在头部插入或者中间删除例如待办事项列表、消息队列等那么建议使用链表或者其他更合适的数据结构否则会产生大量元素搬移的性能损耗。7. 常见问题与排查思路7.1 插入后数据错乱问题现象插入元素后后面的数据出现重复或丢失。这个问题的根本原因通常是搬移元素的方向搞反了。插入操作必须从后向前搬移元素如果从前向后移动前一个元素会覆盖后一个元素导致后半部分数据重复。例如数组[1, 2, 3, 4]在下标 1 插入9如果从前往后搬移下标 0 的1会覆盖到下标 1原下标 1 的2被覆盖后续依次处理会得到[1, 1, 1, 1, 1]数据完全错乱。排查思路检查循环起点。插入时循环变量从size-1开始递减到index结束删除时循环变量从index开始递增到size-2结束。这是最容易出错的地方。7.2 数组下标越界异常问题现象调用insert、remove等操作时报IndexOutOfBoundsException。常见原因有三个一是传入的index是负数二是index大于当前顺序表的长度三是在遍历时错误地使用了data.length作为循环边界访问到了未使用的空间。排查思路所有公共操作入口都要先做下标检查。遍历顺序表时循环条件必须是i size。如果底层使用data.length一旦发生扩容很多未使用的数组空间也会被遍历到引发逻辑错误。问题现象常见原因解决思路插入后数据重复搬移元素方向错误从前向后移动改为从后向前搬移元素下标越界未校验传入下标或遍历越界操作前检查下标遍历使用 size 作为边界数据丢失删除后元素未正确前移从前往后搬移元素扩容后原数据丢失扩容循环边界错误使用 size 作为循环上限而不是 data.length尾部追加失败忘记调用扩容方法追加前调用 ensureCapacity7.3 扩容后原数据丢失问题现象插入大量元素后前面的数据变成 0 或者丢失了。常见原因是扩容时复制数据的循环边界写错把i size写成了i data.length。在扩容方法被调用时data还指向旧数组如果循环上限使用data.length会访问到新数组未初始化的位置同时漏掉了旧数组的部分数据。排查思路在扩容方法中打印旧数组的长度和size值确认循环边界。扩容复制的目标是把旧数组中范围内有效的元素全部搬到新数组循环边界必须使用size。7.4 删除元素后末尾残留 0问题现象删除元素后打印顺序表发现末尾出现了一个多余的 0。这个现象其实不是错误。删除元素后size--已经让末尾的“残留值”不再属于逻辑范围打印遍历时只打印到size-1所以不会看到这个 0。如果使用的是 IDE 的调试功能直接查看data数组才会发现末尾残留值。对于基本类型数组残留值没有影响对于对象类型数组为了帮助垃圾回收最好把data[size]置为null。8. 最佳实践与工程建议8.1 合理设置初始容量顺序表的扩容操作涉及数组复制数据量越大复制开销越高。如果能预估数据规模创建顺序表时应该指定初始容量尽量减少扩容次数。例如在处理一个固定数量学生的成绩时可以这样写SqList scores new SqList(50); // 预估最多 50 个学生如果业务中数据是持续增长的初始容量可以适当设置得偏大一些用少量内存换取更好的性能这在嵌入式和高性能计算环境中尤其重要。8.2 封装边界检查逻辑每次插入、删除、访问前都要做下标校验如果每个方法里都写一遍代码会显得很凌乱。建议把边界检查抽取成私有方法例如private void checkIndex(int index, int upperBound, String message) { if (index 0 || index upperBound) { throw new IndexOutOfBoundsException(message : index); } }这样既减少了重复代码也让公共方法的逻辑更清晰。8.3 使用位运算提高性能在扩容计算中使用移位运算代替除法和乘法是常见优化。例如int newCapacity oldCapacity (oldCapacity 1);这里的 1表示右移一位相当于除以 2。对于计算机来说移位运算比乘除法更快。不过这属于微优化在实际业务中影响不大更重要的是代码可读性。如果团队其他人不熟悉位运算也可以写成乘 1.5 的方式配合注释说明。8.4 接口设计优于直接暴露数组初学者喜欢直接操作底层数组虽然代码看起来简单但是很容易破坏顺序表的不变量。比如直接设置data[10] 5却没有同步修改size导致顺序表内部状态错误。更合理的做法是把顺序表封装成对外提供标准方法的类内部实现细节完全隐藏外部使用者只能通过add、insert、remove等方法操作数据。在大型项目中可以进一步抽象一个List接口将顺序表定义为接口的实现类。这样在使用时面向接口编程后续如果需要换成链表实现业务代码不需要大改。8.5 泛型化改造本文示例使用的是int类型数组。实际项目中顺序表通常需要存储任意类型的数据因此应该泛型化。泛型化改造的核心点有两个第一创建泛型数组时不能直接new T[capacity]因为 Java 无法创建泛型数组需要借助(T[]) new Object[capacity]进行强制转换。第二按值查找时不能使用比较对象要使用equals方法。public class SqListT { private Object[] data; private int size; public SqList(int capacity) { data new Object[capacity]; size 0; } SuppressWarnings(unchecked) public T get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } return (T) data[index]; } public boolean contains(T value) { for (int i 0; i size; i) { if (data[i].equals(value)) { return true; } } return false; } }泛型化之后SqListString、SqListStudent都能使用同一个类大大提升了代码复用率。8.6 与 Java 集合框架的关系看到这里很多读者会想到 Java 自带的ArrayList。实际上ArrayList就是标准库中的顺序表实现它的底层就是Object[]数组同样支持动态扩容、随机访问、按值查找。理解了本文的顺序表后再去看ArrayList的源码会轻松很多。实际生产项目中不需要自己造轮子直接使用ArrayList是更稳妥的选择。自己实现顺序表的价值更多体现在面试、考试和理解数据结构原理上。如果往深处学习可以阅读ArrayList的源码看看 Java 官方是如何处理扩容、迭代器和快速失败机制的。9. 总结与下一步学习方向本文从线性表和顺序表的概念出发解释了顺序表“数组 长度”的存储结构并完整实现了初始化、扩容、插入、删除、按位访问、按值查找、清空等核心操作。插入和删除的元素搬移方向是关键扩容的触发时机和容量策略也直接影响性能。通过测试用例和预期输出我们验证了整个实现是正确可靠的。学完顺序表之后下一步建议学习链表。顺序表和链表是线性表的两种典型实现它们在内存布局、操作效率、适用场景上形成鲜明对比只有把两者放在一起对比学习才能真正理解“数据结构的选择取决于业务需求”。可以继续尝试用 Java 实现单链表并对比两者在头部插入、尾部插入、随机访问上的效率差异。在面试中顺序表常见的进阶问题包括怎么实现动态扩容才能避免性能抖动、如何在顺序表中实现去重、如何用两个顺序表实现集合的交集和并集、如何基于顺序表实现栈和队列。这些都是在本文基础上的延伸练习。如果本文对你有帮助可以收藏备用动手把代码敲一遍。数据结构没有捷径自己实现的每个类都会成为后面学习算法和框架源码的坚实基础。 Java实现顺序表：从线性表到动态数组扩容的完整指南
在开发中我们经常要处理“一组有序数据”的存储问题比如学生成绩表、商品列表、任务队列。最容易想到的方式就是使用数组但数组的长度固定、增删元素麻烦用起来并不顺手。数据结构中的“顺序表”正是在数组基础上封装出来的一种线性表它既保留了数组随机访问快的优势又解决了容量固定、插入删除需要手动搬移数据的痛点。本文将以 Java 语言为例从顺序表的定义出发完整实现初始化、插入、删除、查找、扩容等核心操作并给出可直接运行的完整代码和测试用例。无论你是正在学习数据结构课程还是准备面试、复习算法基础这篇文章都能帮你把顺序表这一章彻底吃透。1. 背景与核心概念1.1 线性表是什么在系统学习顺序表之前首先要理解“线性表”这个概念。线性表是具有相同数据类型的 n 个数据元素的有限序列比如一个班级的学生名单、一串电话号码记录都可以抽象成线性表。线性表中每个元素都有唯一的前驱和后继除了第一个元素没有前驱、最后一个元素没有后继之外其他元素都“手拉手”排成一条直线这种逻辑结构非常直观。线性表的存储方式主要有两种。一种是顺序存储用一组地址连续的内存单元依次存放数据元素这种实现就是顺序表另一种是链式存储通过指针把散落在内存各处的节点串起来这种实现就是链表。在真实项目中两种方式都有大量应用但对于“按位置访问”特别频繁、很少在中间插入删除的场景顺序表的效率远高于链表。这也是为什么我们要先把顺序表吃透。1.2 顺序表解决什么问题顺序表本质上是一段连续的物理存储空间通常用“数组 当前长度”两个属性来描述。它解决的问题可以归纳成三个第一容量的动态管理。静态数组在使用前必须确定大小如果估计少了数据存不下估计多了又浪费内存。顺序表通过扩容机制解决了这个问题在空间不足时自动申请更大的数组并把原数据搬移过去。第二数据的有序组织。顺序表让元素按照逻辑顺序紧密排列通过下标可以直接访问任意位置的元素。比如要访问第 3 个元素数组下标就是 2一步到位。第三常用操作的标准化。初始化、插入、删除、查找、遍历、清空这些操作被封装成方法或函数使用时不需要关心内部细节。这样写业务代码时可以像使用工具一样操作数据集合而不用手动管理底层数组。1.3 顺序表和数组、链表的区别初学者最容易把数组和顺序表混为一谈。数组是编程语言提供的一种基本语法结构长度固定只能由程序员手动处理增删逻辑。顺序表是建立在数组之上的抽象数据结构它把数组的固定长度和增删逻辑封装起来形成一个具备“自动扩容、边界检查、标准接口”的数据容器。在学习时可以把顺序表想象成一个“升级版数组”。和链表相比顺序表的特点是“内存连续、随机访问快、插入删除慢”。链表正好相反它不要求内存连续插入删除只需要修改指针但随机访问必须从头遍历。实际项目中选型时要根据业务特点决定。如果读多写少优先考虑顺序表如果频繁在中间插入删除链表可能更合适。2. 环境准备与代码结构2.1 运行环境说明本文所有代码使用 Java 语言实现在本地开发时建议准备以下环境JDK 8 及以上版本本文代码使用了泛型和增强 for 循环等基础特性JDK 8 完全可以运行。任意 Java IDE例如 IntelliJ IDEA、Eclipse或者直接用记事本配合命令行编译运行。使用命令行时请确认java -version和javac -version能正常输出版本信息。版本需要根据你的项目实际情况调整本文示例以常见环境为例重点演示配置思路和代码实现。2.2 项目文件结构示例工程采用最简单的单类结构目的是让读者把注意力集中到数据结构本身而不是被 Maven 或 Gradle 的工程结构干扰。实际项目中使用时可以把顺序表类放到独立的datastructure包中方便统一管理。顺序表演示项目/ ├── src/ │ └── SqList.java 顺序表完整实现 │ └── SqListTest.java 测试入口类SqList是顺序表的核心类包含成员变量和所有操作方法SqListTest是测试类用于验证功能。2.3 使用到的 Java 技术点在阅读代码前先了解几个关键的 Java 技术点泛型。通过泛型可以让顺序表支持任意数据类型而不只是int。本文为了降低上手难度先用int类型演示核心逻辑最后补充泛型化的改造思路。可变参数。部分初始化方法可以使用可变参数便于一次性添加多个元素。数组拷贝。扩容时需要把原数组的数据复制到新数组可以使用循环逐位复制也可以使用System.arraycopy提高效率。代码中会尽量避免使用过于高级的语法保证基础薄弱的读者也能看懂。3. 顺序表的核心设计原理3.1 顺序表的存储结构顺序表的逻辑结构是“一对一”的线性关系物理结构是连续内存空间。它的定义可以概括为用一组地址连续的存储单元依次存放线性表中的数据元素元素之间的逻辑关系通过它们在内存中的物理位置自然表达。在 Java 中我们使用数组作为底层存储结构再加上一个size变量记录当前元素个数。这里有个容易混淆的地方数组的容量capacity和顺序表的长度size是不同的概念。容量是数组最多能放多少个元素长度是当前实际存放了多少个元素。判断顺序表是否为空看的是size是否为 0而不是容量是否为 0。private int[] data; // 底层数组 private int size; // 当前元素个数data用来存放元素size指向下一个要写入的位置同时也是当前元素个数。初始化时分配一个默认容量的数组size置为 0。3.2 为什么需要扩容机制数组一旦创建长度就不可变。如果顺序表在元素插入时发现数组已满继续写入就会导致数组下标越界。扩容机制的思路是在插入前判断是否还有剩余空间如果没有申请一个更大的新数组把原数组元素全部搬移过去然后让data指向新数组。扩容的容量策略在真实项目中很有讲究。最简单的是“每次增加一个固定大小”比如每次多分配 10 个空间更通用的是“原容量翻倍”或者“增加原容量的一半”。容量翻倍的好处是均摊下来每次插入的时间复杂度为 O(1)不会出现多次扩容的抖动问题。Java 的ArrayList在扩容时默认策略是oldCapacity (oldCapacity 1)也就是增加原来容量的一半。本文会采用这个策略作为演示。3.3 插入操作的核心思想插入操作比较容易出错的点在于元素搬移。如果要在第index个位置插入元素那么从index到size-1的所有元素都必须往后挪动一位空出第index个位置再把新元素写入。这里必须强调一个关键细节搬移元素时必须从最后一个元素开始从后向前依次移动。如果从前往后移动后面的元素还没有被搬走就直接被前一个元素覆盖导致数据丢失。这种“从后往前搬”的规则是顺序表插入操作最常见的考点。// 从后往前搬移元素 for (int i size - 1; i index; i--) { data[i 1] data[i]; }插入前还需要判断下标是否合法。合法范围是0到size。如果index等于size相当于在表尾追加元素如果超出这个范围应该抛出下标越界异常。3.4 删除操作的核心思想删除操作和插入操作方向相反。删除第index个元素后从index1到size-1的元素都必须往前挪动一位填补被删除元素留下的空位。搬移元素时必须从前往后移动。这正好和插入操作相反for (int i index; i size - 1; i) { data[i] data[i 1]; }删除完成后size减 1。这里还有一个性能优化点末尾的废弃数据可以置为默认值帮助垃圾回收。对于基本数据类型int可以置为 0对于对象类型可以置为null。删除操作的时间主要消耗在元素搬移上平均要移动n/2次所以时间复杂度是 O(n)。3.5 查找操作的设计查找可以分成两种。第一种是按位置查找给定下标返回元素顺序表支持随机访问时间复杂度是 O(1)。第二种是按值查找需要遍历整个顺序表找到第一个与目标值相等的元素并返回其下标时间复杂度是 O(n)。按值查找在真实项目中非常常见。比如在成绩表里找到 90 分以上的第一个学生或者在订单表里定位某个订单号。实现时要注意两个点第一如果找不到要有一个统一的返回值约定比如返回-1表示不存在第二在泛型场景下比较元素时要使用equals而不是否则比较的是引用地址而不是内容。4. 顺序表完整 Java 实现4.1 类的成员与构造方法先来定义顺序表类的基本结构// 文件路径src/SqList.java public class SqList { private int[] data; // 底层数组 private int size; // 当前元素个数 // 默认构造方法初始化容量为 10 public SqList() { data new int[10]; size 0; } // 指定初始容量构造方法 public SqList(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数); } data new int[capacity]; size 0; } }默认容量设置为 10这样既不会在刚创建时就占用大量内存又能满足一般的小规模数据需求。第二个构造方法允许调用者按照预估的数据量分配初始空间减少后续扩容次数。4.2 基本成员方法包括获取长度、判断是否为空、按位置访问元素、修改元素// 获取当前元素个数 public int size() { return size; } // 判断顺序表是否为空 public boolean isEmpty() { return size 0; } // 按位置获取元素 public int get(int index) { checkIndexForGet(index); return data[index]; } // 修改指定位置的元素 public void set(int index, int value) { checkIndexForGet(index); data[index] value; } // 检查按位置访问时下标是否合法 private void checkIndexForGet(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } }get和set都是 O(1) 的随机访问操作这也是顺序表相对链表最核心的优势。检查下标的代码被抽取成私有方法避免重复编写同时让外部调用时能立即得到清晰的异常信息。4.3 扩容方法扩容是顺序表内部的基础能力被插入操作调用。虽然写成public也不会报错但合理的设计应该把扩容声明为private因为扩容属于内部机制不应该暴露给调用者。// 确保数组有足够的容量 private void ensureCapacity() { if (size data.length) { return; } // 扩容策略原容量 原容量的一半 int newCapacity data.length (data.length 1); if (newCapacity data.length) { newCapacity 10; } int[] newData new int[newCapacity]; // 搬移原数组数据 for (int i 0; i size; i) { newData[i] data[i]; } data newData; }这里的data.length 1相当于data.length / 2用移位运算比除法运算效率更高。扩容后原来的数组失去引用由 JVM 垃圾回收机制自动回收。工程实践中如果知道数据量会持续增长也可以在调用插入时手动触发一次较大容量的扩容减少多次扩容带来的性能开销。4.4 插入操作实现插入操作支持在任意合法位置插入新元素。插入位置可以是表头、表中或者表尾。// 在指定位置插入元素 public void insert(int index, int value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置非法: index); } ensureCapacity(); // 从后往前搬移元素腾出位置 for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] value; size; } // 在表尾追加元素 public void add(int value) { ensureCapacity(); data[size] value; size; }在表尾追加元素是插入的一种特殊情况单独提供add方法会让调用更加简洁。每次插入完都要记得size漏掉这一步会导致后续读写错位也是最常见的低级错误。为了验证插入逻辑可以看一个简单例子。假设数组中已有元素[1, 2, 3, 4]要在下标 1 的位置插入9。首先从后往前搬移下标 3 的4移到下标 4下标 2 的3移到下标 3下标 1 的2移到下标 2然后下标 1 写入9。最终数组变为[1, 9, 2, 3, 4]完全符合预期。4.5 删除操作实现删除操作接收一个下标返回被删除的元素值。返回被删除的元素在某些业务场景中很有用比如需要记录日志或做撤销操作。// 删除指定位置的元素并返回被删除的元素 public int remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置非法: index); } int oldValue data[index]; // 从前往后搬移元素覆盖被删除位置 for (int i index; i size - 1; i) { data[i] data[i 1]; } size--; // 将末尾废弃位置置为 0帮助释放引用对基本类型是可选操作 data[size] 0; return oldValue; }从前往后搬移是删除操作的正确姿势。如果从后往前搬移前一个元素会被后一个元素覆盖导致数据混乱。4.6 查找与遍历按值查找返回第一个匹配元素的下标如果找不到返回-1。判断容器中是否包含某个元素可以基于查找方法实现// 按值查找返回第一个匹配的下标找不到返回 -1 public int indexOf(int value) { for (int i 0; i size; i) { if (data[i] value) { return i; } } return -1; } // 判断是否包含目标值 public boolean contains(int value) { return indexOf(value) ! -1; } // 遍历打印所有元素 public void print() { System.out.print([); for (int i 0; i size; i) { System.out.print(data[i]); if (i ! size - 1) { System.out.print(, ); } } System.out.println(]); }print方法方便在测试时观察顺序表的内部状态。注意打印遍历时循环条件是i size而不是i data.length。否则会把未使用的扩容空间也打印出来。4.7 清空与判空清空操作只重置size不要求立即释放数组内存。这样即使扩容后的数组被保留再次添加元素时也能避免立刻扩容空间可以复用。// 清空顺序表 public void clear() { size 0; }对于对象类型的顺序表清空时最好把数组中每个引用都置为null否则会出现“对象无法被垃圾回收”的内存隐患。基本类型数组则没有这个问题。4.8 完整代码汇总把上面的方法组合到一起形成完整的SqList.java类。// 文件路径src/SqList.java public class SqList { private int[] data; private int size; public SqList() { data new int[10]; size 0; } public SqList(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数); } data new int[capacity]; size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } return data[index]; } public void set(int index, int value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } data[index] value; } private void ensureCapacity() { if (size data.length) { return; } int newCapacity data.length (data.length 1); int[] newData new int[newCapacity]; for (int i 0; i size; i) { newData[i] data[i]; } data newData; } public void insert(int index, int value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置非法: index); } ensureCapacity(); for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] value; size; } public void add(int value) { ensureCapacity(); data[size] value; size; } public int remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置非法: index); } int oldValue data[index]; for (int i index; i size - 1; i) { data[i] data[i 1]; } size--; data[size] 0; return oldValue; } public int indexOf(int value) { for (int i 0; i size; i) { if (data[i] value) { return i; } } return -1; } public boolean contains(int value) { return indexOf(value) ! -1; } public void print() { System.out.print([); for (int i 0; i size; i) { System.out.print(data[i]); if (i ! size - 1) { System.out.print(, ); } } System.out.println(]); } public void clear() { size 0; } }5. 测试与运行验证5.1 编写测试类顺序表类写完以后需要编写测试类验证功能是否正常。测试类覆盖了插入、删除、查找、修改、遍历等核心操作每个操作之间通过打印结果来检验正确性。// 文件路径src/SqListTest.java public class SqListTest { public static void main(String[] args) { // 1. 创建一个顺序表 SqList list new SqList(); System.out.println(初始是否为空 list.isEmpty()); // 2. 尾部追加元素 list.add(10); list.add(20); list.add(30); list.add(40); System.out.print(尾部追加 10,20,30,40 后); list.print(); // 3. 指定位置插入 list.insert(1, 15); System.out.print(在下标 1 插入 15 后); list.print(); // 4. 按位置查找和修改 System.out.println(下标 2 的元素是 list.get(2)); list.set(0, 100); System.out.print(将下标 0 修改为 100 后); list.print(); // 5. 按值查找 System.out.println(元素 30 的下标是 list.indexOf(30)); System.out.println(是否包含 99 list.contains(99)); // 6. 删除操作 int removed list.remove(1); System.out.println(删除的元素是 removed); System.out.print(删除后); list.print(); // 7. 清空操作 list.clear(); System.out.println(清空后是否为空 list.isEmpty()); } }5.2 编译运行在命令行进入src目录依次执行编译和运行命令javac SqList.java SqListTest.java java SqListTest使用 IDE 开发时直接运行SqListTest类中的main方法即可。5.3 预期输出结果运行程序后控制台输出如下初始是否为空true 尾部追加 10,20,30,40 后[10, 20, 30, 40] 在下标 1 插入 15 后[10, 15, 20, 30, 40] 下标 2 的元素是20 将下标 0 修改为 100 后[100, 15, 20, 30, 40] 元素 30 的下标是3 是否包含 99false 删除的元素是15 删除后[100, 20, 30, 40] 清空后是否为空true输出结果和预期完全一致。这里需要特别说明set(0, 100)之后indexOf(30)的结果仍然是 3。因为删除操作发生在查找之后此时顺序表为[100, 15, 20, 30, 40]元素 30 位于下标 3。5.4 扩容能力测试为了验证扩容机制是否正常工作可以专门写一个循环添加大量数据的测试// 扩容测试连续添加 100 个元素 SqList bigList new SqList(5); for (int i 0; i 100; i) { bigList.add(i); } System.out.println(扩容后元素个数 bigList.size()); System.out.println(扩容后下标 99 的元素 bigList.get(99));初始容量只有 5但需要存储 100 个元素因此会触发多次扩容。只要最后能输出元素个数 100并且get(99)返回 99就证明扩容机制正常工作。6. 复杂度分析与性能边界6.1 时间复杂度分析顺序表各操作的时间复杂度如下表所示操作平均时间复杂度说明按下标访问getO(1)直接通过数组下标定位修改元素setO(1)直接通过数组下标定位尾部插入addO(1)均摊分析下扩容次数少任意位置插入insertO(n)需要移动 n/2 个元素删除removeO(n)需要移动 n/2 个元素按值查找indexOfO(n)需要遍历数组判断包含containsO(n)依赖 indexOf从表中可以看到顺序表的强项是随机访问和尾部的增删弱项是中间位置的插入删除和按值查找。6.2 空间复杂度分析顺序表的空间复杂度为 O(n)因为底层数组需要为所有元素分配连续内存。在 real-time 场景中扩容会瞬间申请一份更大的内存如果顺序表存储的是大量对象引用扩容时的内存开销会比较明显。为了避免频繁扩容创建顺序表时可以根据业务大小给出合理的初始容量例如预估 1000 条数据就初始化new SqList(1000)。6.3 顺序表适合的场景从复杂度分析可以看出顺序表最擅长处理以下场景需要频繁按下标读取元素的场景比如排行榜、缓存队列。数据量相对稳定、增长不剧烈的场景。主要在尾部添加和删除数据的场景比如程序运行日志的暂存或者栈的实现。如果业务中需要频繁在头部插入或者中间删除例如待办事项列表、消息队列等那么建议使用链表或者其他更合适的数据结构否则会产生大量元素搬移的性能损耗。7. 常见问题与排查思路7.1 插入后数据错乱问题现象插入元素后后面的数据出现重复或丢失。这个问题的根本原因通常是搬移元素的方向搞反了。插入操作必须从后向前搬移元素如果从前向后移动前一个元素会覆盖后一个元素导致后半部分数据重复。例如数组[1, 2, 3, 4]在下标 1 插入9如果从前往后搬移下标 0 的1会覆盖到下标 1原下标 1 的2被覆盖后续依次处理会得到[1, 1, 1, 1, 1]数据完全错乱。排查思路检查循环起点。插入时循环变量从size-1开始递减到index结束删除时循环变量从index开始递增到size-2结束。这是最容易出错的地方。7.2 数组下标越界异常问题现象调用insert、remove等操作时报IndexOutOfBoundsException。常见原因有三个一是传入的index是负数二是index大于当前顺序表的长度三是在遍历时错误地使用了data.length作为循环边界访问到了未使用的空间。排查思路所有公共操作入口都要先做下标检查。遍历顺序表时循环条件必须是i size。如果底层使用data.length一旦发生扩容很多未使用的数组空间也会被遍历到引发逻辑错误。问题现象常见原因解决思路插入后数据重复搬移元素方向错误从前向后移动改为从后向前搬移元素下标越界未校验传入下标或遍历越界操作前检查下标遍历使用 size 作为边界数据丢失删除后元素未正确前移从前往后搬移元素扩容后原数据丢失扩容循环边界错误使用 size 作为循环上限而不是 data.length尾部追加失败忘记调用扩容方法追加前调用 ensureCapacity7.3 扩容后原数据丢失问题现象插入大量元素后前面的数据变成 0 或者丢失了。常见原因是扩容时复制数据的循环边界写错把i size写成了i data.length。在扩容方法被调用时data还指向旧数组如果循环上限使用data.length会访问到新数组未初始化的位置同时漏掉了旧数组的部分数据。排查思路在扩容方法中打印旧数组的长度和size值确认循环边界。扩容复制的目标是把旧数组中范围内有效的元素全部搬到新数组循环边界必须使用size。7.4 删除元素后末尾残留 0问题现象删除元素后打印顺序表发现末尾出现了一个多余的 0。这个现象其实不是错误。删除元素后size--已经让末尾的“残留值”不再属于逻辑范围打印遍历时只打印到size-1所以不会看到这个 0。如果使用的是 IDE 的调试功能直接查看data数组才会发现末尾残留值。对于基本类型数组残留值没有影响对于对象类型数组为了帮助垃圾回收最好把data[size]置为null。8. 最佳实践与工程建议8.1 合理设置初始容量顺序表的扩容操作涉及数组复制数据量越大复制开销越高。如果能预估数据规模创建顺序表时应该指定初始容量尽量减少扩容次数。例如在处理一个固定数量学生的成绩时可以这样写SqList scores new SqList(50); // 预估最多 50 个学生如果业务中数据是持续增长的初始容量可以适当设置得偏大一些用少量内存换取更好的性能这在嵌入式和高性能计算环境中尤其重要。8.2 封装边界检查逻辑每次插入、删除、访问前都要做下标校验如果每个方法里都写一遍代码会显得很凌乱。建议把边界检查抽取成私有方法例如private void checkIndex(int index, int upperBound, String message) { if (index 0 || index upperBound) { throw new IndexOutOfBoundsException(message : index); } }这样既减少了重复代码也让公共方法的逻辑更清晰。8.3 使用位运算提高性能在扩容计算中使用移位运算代替除法和乘法是常见优化。例如int newCapacity oldCapacity (oldCapacity 1);这里的 1表示右移一位相当于除以 2。对于计算机来说移位运算比乘除法更快。不过这属于微优化在实际业务中影响不大更重要的是代码可读性。如果团队其他人不熟悉位运算也可以写成乘 1.5 的方式配合注释说明。8.4 接口设计优于直接暴露数组初学者喜欢直接操作底层数组虽然代码看起来简单但是很容易破坏顺序表的不变量。比如直接设置data[10] 5却没有同步修改size导致顺序表内部状态错误。更合理的做法是把顺序表封装成对外提供标准方法的类内部实现细节完全隐藏外部使用者只能通过add、insert、remove等方法操作数据。在大型项目中可以进一步抽象一个List接口将顺序表定义为接口的实现类。这样在使用时面向接口编程后续如果需要换成链表实现业务代码不需要大改。8.5 泛型化改造本文示例使用的是int类型数组。实际项目中顺序表通常需要存储任意类型的数据因此应该泛型化。泛型化改造的核心点有两个第一创建泛型数组时不能直接new T[capacity]因为 Java 无法创建泛型数组需要借助(T[]) new Object[capacity]进行强制转换。第二按值查找时不能使用比较对象要使用equals方法。public class SqListT { private Object[] data; private int size; public SqList(int capacity) { data new Object[capacity]; size 0; } SuppressWarnings(unchecked) public T get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } return (T) data[index]; } public boolean contains(T value) { for (int i 0; i size; i) { if (data[i].equals(value)) { return true; } } return false; } }泛型化之后SqListString、SqListStudent都能使用同一个类大大提升了代码复用率。8.6 与 Java 集合框架的关系看到这里很多读者会想到 Java 自带的ArrayList。实际上ArrayList就是标准库中的顺序表实现它的底层就是Object[]数组同样支持动态扩容、随机访问、按值查找。理解了本文的顺序表后再去看ArrayList的源码会轻松很多。实际生产项目中不需要自己造轮子直接使用ArrayList是更稳妥的选择。自己实现顺序表的价值更多体现在面试、考试和理解数据结构原理上。如果往深处学习可以阅读ArrayList的源码看看 Java 官方是如何处理扩容、迭代器和快速失败机制的。9. 总结与下一步学习方向本文从线性表和顺序表的概念出发解释了顺序表“数组 长度”的存储结构并完整实现了初始化、扩容、插入、删除、按位访问、按值查找、清空等核心操作。插入和删除的元素搬移方向是关键扩容的触发时机和容量策略也直接影响性能。通过测试用例和预期输出我们验证了整个实现是正确可靠的。学完顺序表之后下一步建议学习链表。顺序表和链表是线性表的两种典型实现它们在内存布局、操作效率、适用场景上形成鲜明对比只有把两者放在一起对比学习才能真正理解“数据结构的选择取决于业务需求”。可以继续尝试用 Java 实现单链表并对比两者在头部插入、尾部插入、随机访问上的效率差异。在面试中顺序表常见的进阶问题包括怎么实现动态扩容才能避免性能抖动、如何在顺序表中实现去重、如何用两个顺序表实现集合的交集和并集、如何基于顺序表实现栈和队列。这些都是在本文基础上的延伸练习。如果本文对你有帮助可以收藏备用动手把代码敲一遍。数据结构没有捷径自己实现的每个类都会成为后面学习算法和框架源码的坚实基础。