什么是顺序表？
- 顺序表 是一种线性表 的数据结构。
- 顺序表通过一组连续地址 的存储单元依次存储 线性表中的数据元素。
顺序表的主要特点：
- 逻辑上相邻的元素在物理位置上也相邻。
- 可以随机访问表中的任意元素，通过元素的位置序号可以在
O(1)的时间复杂度内直接获取对应元素。 - 插入和删除操作的效率相对较低。例如，在顺序表的中间位置插入一个元素，需要移动大量后续元素，时间复杂度为
O(n)；删除操作同理。
顺序表的优点：
- 随机访问速度快，能够快速获取指定位置的元素。
- 存储密度高，不需要额外的指针来链接元素。
顺序表的缺点：
- 长度固定，不易扩展。
- 插入和删除操作可能涉及大量元素的移动，效率较低。
举个例子，如果有一个顺序表存储了学生的成绩 [85, 90, 78, 95, 88] ，如果要获取第三个学生的成绩，直接通过索引 2 就能快速得到 78 。但如果要在第二个位置插入一个新成绩 80 ，就需要将后面的元素 90, 78, 95, 88 依次向后移动一位，然后再插入 80 。
顺序表在很多程序设计中都有应用，比如简单的数组实现、一些对随机访问要求较高而插入删除操作较少的场景等，今天我们用java来简单实现一下顺序表。
构造方法：
首先，构造一个顺序表，需要int capacity 表示顺序表的内存大小(这里先传入一个值作为参数，后面内存不够用我们会有专门申请内存的方法)、int size表示表里面元素的个数、Object [] array 来命名这个顺序表，这时候一个最基本的顺序表就被构造出来了，以下是代码实现：
public class LinearList {
private int capacity = 10;
private int size = 0;
private Object[] array = new Object[capacity];
添加方法：
要对顺序表array进行添加操作，需要传入两个参数 泛型 element 以及 int index，代表在index下标插入 泛型 element。
注意：这里需要判断 index 和 size 的大小，如果index <0 || index>size,则理应抛出错误。
在index位置插入元素，只需要将原来index以及index后面的元素往后移一位，空出来的位置给element即可。下面是添加方法的代码实现：
public void add(E element, int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index out of bounds");
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = element;
size++;
}
但是当顺序表中存储的元素数量达到当前分配的存储空间上限时，就需要进行扩容 。具体来说，常见的情况有：
- 持续向顺序表中添加元素，导致已分配的存储空间被填满。
例如，最初分配的顺序表空间能存储 10 个整数，当已经存储了 10 个整数后，如果还需要继续添加新的整数，就需要扩容。
- 事先无法准确预估元素数量，且实际存储的元素数量超出了初始的预计。
假设一个用于存储用户订单信息的顺序表，由于促销活动导致订单数量大幅增加，超出了初始分配的空间。
- 业务需求发生变化，导致需要存储更多的元素。
比如原本的系统只需要存储一个月内的交易记录，但业务调整后需要存储半年甚至更长时间的交易记录，原有的顺序表空间可能就不够了。
在进行扩容时，通常会重新分配一块更大的连续存储空间 ，并将原有的元素复制到新的空间中。扩容的策略可以是按照一定的比例增加空间，例如每次扩容为原来的两倍；也可以是增加固定的大小，如每次增加一定数量的存储单元，原来的那块空间也并不会造成空间浪费，通常会被JVM的垃圾回收机制自动回收。
通常把扩容操作放在添加方法内部 ，因为在添加元素时才会有可能需要用到扩容操作，以下是添加了扩容操作的添加方法的代码实现：
```java
public void add(E element, int index) {
// 如果索引不在有效范围内，抛出异常
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index out of bounds");
// 如果当前元素数量达到容量，进行扩容
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/4609.html
