🐵本篇文章将对顺序表中的方法进行模拟实现
一、线性表
线性表是指在逻辑结构上呈连续的线性结构，而在物理结构上不一定是连续的结构，常见的线性表有：顺序表、链表、栈、队列等
二、顺序表
顺序表一般采用数组来存储数据，因此它是一种逻辑结构上连续，在物理结构上也连续的数据结构，下面对顺序表的增删查改等操作用Java进行具体实现
先实现一个接口，在这个接口写上要实现的方法：
public interface IList {
void add(int data); // 新增元素,默认在数组最后新增
void add(int pos, int data); // 在 pos 位置插入元素
boolean contains(int toFind); // 判定是否包含某个元素
int indexOf(int toFind); // 查找某个元素对应的位置
int get(int pos); // 获取 pos 位置的元素
void set(int pos, int value); // 给 pos 位置的元素设为 value
void remove(int toRemove); //删除第一次出现的关键字toRemove
int size(); // 获取顺序表长度
void clear(); // 清空顺序表
void display(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
}
之后再创建一个MyArrayList类实现上述接口并重写接口中所有的方法
public class MyArrayList implements IList{
public int[] elem; //存储数据
public int usedSize; //已经放入顺序表中数据的个数
public static final int DEFAULT_CAPACITY = 5; //顺序表中默认容量的大小为5
public MyArrayList() {
elem = new int[DEFAULT_CAPACITY];
}
/*以下是要重写IList接口中的方法*/
...
}
2.1 方法的实现
void add(int data); // 新增元素,默认在数组尾部新增在数组的尾部新增一个元素，之前的ArrayList类中有一个变量为usedSize，用于记录顺序表中已存数据的个数，刚开始存入数据的时候usedSize为0，那么每次向数组中存入一个数据，usedSize就加1
public void add(int data) {
elem[usedSize] = data;
usedSize++;
}
写到这里还要考虑一个问题：如果数组满了怎么办，我们前面定义了数组的默认大小为5，如果已经向数组中存入了5个数据在存数据的话，就会抛出数组越界异常，所以在向数组中新增元素时要先判断一下数组满没满，如果满了则要扩容，然后再新增元素
public void add(int data) {
if (usedSize == elem.length) {
elem = Arrays.copyOf(elem, elem.length * 2);
}
elem[usedSize] = data;
usedSize++;
}
Arrays.copyOf的方法定义如下：
public static int[] copyOf(int[] original, int newLength)int[] original为源数组，newLength为该数组的新长度
void add(int pos, int data); // 在 pos 位置插入元素
那么接下来有一个问题，这些元素怎么移动？是从后往前移动还是从前往后移动，答案是从后往前移动，因为如果从前往后移动的话，先将2放在了3的位置处，如果再要将3移动到4位置时发现3已经被2覆盖了，所以要从5开始倒着依次向后移动
public void add(int pos, int data) {
for (int i = usedSize; i >= pos; i--) {
//循环条件为i >= pos，因为pos位置处的元素也要往后移动
elem[i] = elem[i - 1];
}
elem[pos] = data; //移动完后，直接再pos位置处插入新增元素
}
写到这里后还要考虑两点：1.pos位置是否合法；2. 此时数组有没有满
先来看第一个：pos位置是否合法，这个很简单，我们可以在第一句加上一个判断pos的方法，如果pos不合法则抛出一个异常使程序终止
public class EmptyException extends RuntimeException{
public EmptyException(String message) {
super(message);
}
}
========================================================
private void checkPosAdd(int pos) {
if (pos < 0 || pos >= usedSize + 1) {
//数组的下标不能为0；在一个位置插入后，必须是连续的因为前面说过顺序表在物理结构上也是连续的
throw new PosException("下标错误");
}
}
判断数组满没满跟之前一样，以下是该方法的最终实现：
public void add(int pos, int data) {
checkPosAdd(pos);
if (usedSize == elem.length) {
elem = Arrays.copyOf(elem, 2 * elem.length);
}
for (int i = usedSize; i >= pos; i--) {
elem[i] = elem[i - 1];
}
elem[pos] = data;
usedSize++;
}boolean contains(int toFind); // 判定数组中是否包含某个元素实现这个方法很简单，只需要遍历一遍数组即可
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (elem[i] == toFind) {
return true;
}
}
return false;
}
int indexOf(int toFind); // 查找某个元素对应的位置同样，这个方法也遍历一遍数组即可
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (elem[i] == toFind) {
return i;
}
}
return -1; //如果没有这个元素，返回-1
}
int get(int pos); // 获取 pos 位置的元素
要先判断一下pos位置是否合法
private void checkPosGet(int pos) {
if (pos < 0 || pos >= usedSize) {
//这里pos >= usedSize 的原因是usedSize代表当前已存数据的个数，该位置还没有放元素
throw new PosException("下标错误");
}
}get方法的最终实现：
public int get(int pos) {
checkPosGet(pos);
return elem[pos];
}
void set(int pos, int value); // 给 pos 位置的元素设为 value
该方法的实现和get方法几乎一致
public void set(int pos, int value) {
checkPosGet(pos);
elem[pos] = value
}
void remove(int toRemove); //删除第一次出现的关键字toRemove
在移动元素之前，要先得到toRemove的下标，可以直接利用刚刚实现的indexOf方法，得到下标后开始移动元素，移动完元素就相当于已经将toRemove删除了，那么让usedSize减1
public void remove(int toRemove) {
int pos = indexOf(toRemove);
for (int i = pos; i < usedSize - 1; i++) {
elem[i] = elem[i + 1];
}
usedSize--;
}在方法的开始还要判断一下数组是否为空，如果为空则不能删除，可以抛出一个异常
public class EmptyException extends RuntimeException{
public EmptyException(String message) {
super(message);
}
}
=======================================================
public void remove(int toRemove) {
if (usedSize == elem.length) {
throw new EmptyException("顺序表为空");
}
int pos = indexOf(toRemove);
for (int i = pos; i < usedSize - 1; i++) {
elem[i] = elem[i + 1];
}
usedSize--;
}
int size(); // 获取顺序表长度
直接返回usedSize即可
int size() {
return usedSize;
}
void clear(); // 清空顺序表
具体实现：
public void clear() {
usedSize = 0; //这里的顺序表中放的都是int类型而非引用类型，所以，不用将每个元素置空
//如果顺序表中的元素都是引用类型则应遍历数组，将每个元素置空，再将usedSize置为0
}
void display(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
遍历数组并打印即可：
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] +" ");
}
System.out.println();
}
🙉本篇文章到此结束，下一篇文章将对ArrayList进行讲解
