前言
在之前对顺序表使用C语言进行了简单的实现：线性表的顺序表示和实现（C语言）
当时使用C语言进行实现是因为学校的教材使用的是C语言来进行实现，在后来的学习中，Java成为了我的主语言，使用不同的语言对顺序表来进行实现也可以加深我对语言的理解和应用。
一、什么是顺序表？
【百度百科】顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
资料链接：顺序表_百度百科
二、顺序表的实现
在顺序表的定义中可以看到，顺序表是一组地址连续的存储单元，本质上是一种增加了一些基本操作功能的数组
在本文中要实现的功能有：
- 获取顺序表中的元素个数
- 获取顺序表当前的容量
- 顺序表是否为空
- 在指定索引位置添加元素
- 在顺序表末尾添加元素
- 在顺序表头部添加元素
- 获取指定索引位置的元素
- 获取顺序表第一个元素
- 获取顺序表最后一个元素
- 修改指定索引位置的元素
- 判断顺序表中是否包含指定元素
- 获取顺序表中指定元素的索引
- 删除指定索引位置的元素
- 删除并返回顺序表第一个元素
- 删除并返回顺序表最后一个元素
- 删除顺序表中的指定元素
- 对顺序表进行动态的扩容和缩容
1. 准备工作
| 实现工具 | 版本 |
| IntelliJ IDEA | 2021.3 |
| JDK | 1.8 |
在 IntelliJ IDEA 中新建普通的Java项目即可
在新建好Java工程后，我们创建自己的顺序表类，在这里我对当前类命名为Array，在这里实现泛型，同时Array类中需要有两个成员属性：
- 存放数据的数组：
data，类型为泛型数组 - 当前顺序表中元素的数量：
size，类型为int
两个成员属性的访问权限都应该为private，用户不能够直接进行修改，只能通过对应的getter方法进行获取。在成员属性中我们将存放数据的数组和顺序表中的元素数量只是进行了声明，但是并未进行初始化，因此初始化的过程就需要在构造方法中进行
- 有参构造：在进行有参构造时，我们只需要指定传入的参数为一个
int类型的数据capacity，代表顺序表的初始容量，因此对data进行初始化泛型数组即可。同时当前顺序表中是没有元素的，代表顺序表中的元素个数size的初始值为0。 - 无参构造：在用户没有指定了顺序表的初始容量时我们可以自定义初始容量为10，仅需要通过
this(10)进行有参构造的调用即可。
注意： 在Java中不能直接初始化泛型数组，需要先声明Object类型的数组后通过强制类型转换的方式将Object类型的数组转换为泛型数组
package net.csdn.array; /** * @author zhangrongkang * @date 2022/6/26 */ public class Array<E> { /** * 存放数据的数组 */ private E[] data; /** * 数组中元素的数量 */ private int size; /** * 构造函数，传入数组的容量capacity构造数组 * * @param capacity 初始数组大小 */ public Array(int capacity) { data = (E[]) new Object[capacity]; size = 0; } /** * 无参构造函数，默认数组大小为0 */ public Array() { this(10); } }
使用泛型的原因：使用泛型后可以将当前顺序表中存储对象，如果不使用泛型的话只能使用自己指定类型的数据，扩展性不强。因此使用泛型后可以将当前顺序表的使用扩展到所有类对象，只需要在创建时指定相应的对象即可。
2. 获取顺序表的元素个数
/** * 获取数组中的元素个数 * * @return 数组当前的元素个数 */ public int getSize() { return size; }
在对顺序表进行声明的时候，就已经将用户传来的或者默认的初始容量capacity作为数组的大小对data泛型数组进行了初始化，因此当前data的length属性就是传来的capacity，（或者在后面进行动态扩容或缩容时，data.length是一直不会改变的，改变的只有size）
因此获取顺序表当前的容量将data.length返回即可
4. 顺序表是否为空
/** * 判断数组是否为空 * * @return 数组是否为空 */ public boolean isEmpty() { return size == 0; }
我们知道size代表的是顺序表中的元素个数，因此要判断当前顺序表是否为空仅需要将size是否等于0进行返回即可
5. 在指定索引位置添加元素
/** * 向数组中索引为index位置添加元素e * * @param index 索引位置 * @param e 元素e */ public void add(int index, E e) { // 判断数组空间是否已满 if (size == data.length) { // 对数组进行扩容 resize(2 * data.length); } // 越界判断 if (index < 0 || index > size) { throw new ArrayIndexOutOfBoundsException(); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; }
当向顺序表中指定索引位置添加元素时要考虑以下几个问题：
- 当前顺序表中是否还有容量？
- 添加的元素索引值是否越界？
对于第一个问题来说，当顺序表已满没有容量时，再进行添加元素时需要进行动态的扩容，resize方法的作用就是对数组进行动态的扩容以及缩容，对于resize方法的实现我们放到后面进行具体的讲解，在这里我们知道如果当前顺序表容量已满，将顺序表容量扩大为当前顺序表容量的二倍
第二个问题的出现情况只有两种，索引小于0或索引超过了当前顺序表中的元素个数时，抛出运行时异常即可
在索引没有问题后，添加元素的过程如下图所示：
要先将要添加的索引位置后的所有元素依次向后移动一位，在移动完成后将当前索引位置的元素使用要进行添加的元素对当前位置的元素进行覆盖即可，同时添加完元素后将size++，维护指针变量
6. 在顺序表末尾添加元素
/** * 在数组末尾添加一个元素 * * @param e 要添加的元素 */ public void addLast(E e) { add(size, e); }
在末尾添加元素可以对之前写好的向指定索引位置添加元素的代码进行复用，同时在add方法中进行了校验，因此对于扩容以及索引都问题都无需我们进行考虑，将 索引位置的参数赋值为当前最后一个元素的下一个位置size 后直接调用即可。
7. 在顺序表头部添加元素
/** * 在数组的头部添加元素e * * @param e 要添加的元素 */ public void addFirst(E e) { add(0, e); }
在顺序表的头部添加元素也是同样的道理，对指定索引位置插入元素进行复用即可，在此不进行赘述。
8. 获取指定索引位置的元素
/** * 获取索引为index位置的元素 * * @param index 索引位置 * @return 索引为index位置的元素 */ public E get(int index) { if (index < 0 || index >= size) { throw new ArrayIndexOutOfBoundsException(); } return data[index]; }
获取指定索引位置的元素与之前在指定索引位置插入元素的思路大体一致，但是要更简单一些，无需考虑顺序表扩容以及缩容的问题，仅需要考虑传入的索引值是否合法，如果传入的索引值合法则直接将对应位置的元素进行返回即可。
