在之前的博客中，我们大部分都在学习数据结构相关的理论知识，而今天我们要学到的ArrayList便有所不同了，ArrayList这部分算是重要的知识，所以大家打起精神，让我们一起学习~
在学习ArrayList之前，我们需要先认识一下List：
一、认识 List 接口
① List 的定义
在Java中，List是一个接口，它继承自 Collection 接口。List 接口代表一个有序的元素序列，允许元素重复。也就是说我们可以按照添加顺序存储一组元素，并且同一元素可以多次出现。List 接口为我们提供了许多方法来控制列表中的元素。
我们可以通过这张关系图看出来，List在其中所处的位置，以及它继承什么，它的子类都有什么。
② List 的基本方法
List 接口包括 Collection 接口的所有方法，因为Collection是List的超级接口。
③ List 的使用
首先我们由刚刚的图能够知道，List 是一个接口，它不能直接用来实例化！
而想要具体使用 List 就需要我们实例化 List 的实现类~所以就引出我们本篇博客的主要内容：ArrayList。
二、认识 ArrayList
① 线性表
📚 线性表的定义：
线性表是由n个具有相同数据类型的元素构成的有限序列，其中元素之间存在一对一的前后关系。常见的线性表有：顺序表、链表、栈、队列...
📕 元素类型：线性表中的元素具有相同的数据类型，可以是基本数据类型（如整数、浮点数等）或者自定义的对象类型。
📕 元素的数量：线性表中的元素个数是有限的，通过计数器或者链式结构进行统计。
📕 元素顺序：线性表中元素的顺序是有序的，每个元素都唯一对应一个前驱元素和一个后继元素（除了第一个元素没有前驱，最后一个元素没有后继）。
（注：线性表在逻辑上是线性结构，也就是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。）
② 顺序表
📚 顺序表的定义：
顺序表使用数组或者类似数组的存储结构，元素在内存中连续存储，通过数组下标访问元素。顺序表的插入和删除操作需要移动大量元素，但是随机访问效率较高。
③ ArrayList 的定义
在上图中，我们可以知道 ArrayList 就是 List 的实现类，而 ArrayList 同时也是顺序表的一种。
ArrayList 与我们之前所学习过的"数组"很像，在逻辑上基本是一致的，但是 ArrayList 由于是 List 接口的实现，所以也就理所应当的拥有很多的方法，比如 ArrayList 相比于"数组"，则会更为灵活，因为当我们创建"数组"时，必须声明"数组"的大小才能够使用它，一旦声明了数组的大小就很难去更改它。而 ArrayList 中所拥有的方法就能够解决这个问题，ArrayList 允许我们创建可调整大小的数组，并会自动扩容~所以 ArrayList 也被称为 "动态数组"。
（注：ArrayList 的自动扩容为原来的1.5倍，就是旧容量加上旧容量值右移一位得到的）
所以在学习 ArrayList 之后，我们以后无论是做题还是工作，大部分时候都是优先选择 ArrayList 的~
④ ArrayList 的创建
📚 在Java中创建数组列表的方法：
//向上转型 利用多态使用 List 创建一个 ArrayList
List<Integer> list = new ArrayList<>();
//直接创建 ArrayList
ArrayList<Integer> arrayList = new ArrayList<>();（注：Integer 也可以换成其他的"基本数据类型对应包装类"或其他自定义类~）
三、ArrayList 的方法
接下来我将边为大家讲解示范 ArrayList 的各种方法，同时模拟实现一个 MyArrayList 以便大家更好的理解~
① ArrayList 基本框架
上面我们提到了，ArrayList 其实就是"动态数组"，所以我们可以用数组来作为 MyArrayList 中存储数据的载体，并且为了后续能够使 MyArrayList 拥有自动扩容的能力，我们还需要创建出一个"有效大小 usedSize" 和 "默认容量 DEFAULT_SIZE"以协助我们后续编写方法。
public class MyArrayList {//创建数组作为顺序表public int[] elem;//数组的有效大小public int usedSize;//初始容量private static final int DEFAULT_SIZE = 10;public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}
}② ArrayList.add(int data)
这个很好理解，就是往顺序表中添加新的元素，但是，这与数组的" arr[0] = in.nextInt() "不太一样，因为数组元素未初始化时，本身就有默认值 0 ，这样的操作只是将新的数据把 0 替换掉了而已，并不是添加进去。而 ArrayList 在逻辑上就是添加了新的元素，而并不是替换~
📚 那么我们再尝试一下，在刚刚创建的 MyArrayList 中也实现一个 add() 方法：
📌 为防止越界访问，该方法需要做到能够识别顺序表是否已满
📌 若此时已满，该方法则发生自动扩容
public void add(int data) {if(isFull()){//1.5倍扩容elem = Arrays.copyOf(elem,elem.length + (elem.length >> 1));}elem[usedSize] = data;usedSize++;} public boolean isFull() {if(usedSize >= elem.length) {return true;}return false;}我们的顺序表初始大小是10，那么我们多输入几个数据试试，看看有没有自动扩容：
是不是觉得有些晕晕的？不要忘了，ArrayList 是可以直接打印的，但我们的 MyArrayList 以数组作为载体，直接打印的话当然出现的是地址啦~所以我们接下来还得再实现一下 toString() 的重写才行~
③ ArrayList 的打印
打印数组各个元素时，我们需要将数组遍历一遍，但是 ArrayList 是能够直接打印其中元素的，其打印格式为：
于是我们也按照该格式重写 toString() 就好了：
@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("[");for(int i = 0;i < usedSize;i++){sb.append(elem[i]);if(i != usedSize - 1){sb.append(", ");}}sb.append("]");return sb.toString();}📚 借此我们也顺便测试一下上面的 add() 方法编写的是否有误：
看来格式是没有问题的，并且"检查顺序表是否已满"和"自动扩容"的功能目前看来也没有问题~
④ ArrayList.add(int pos,int data)
上面我们了解到了 ArrayList 的 add(int data) 方法，作用是直接在顺序表的末尾添加一个新元素，而还有另一个带下标参数的 add(int pos,int data) 方法，它的作用就是在顺序表的指定位置(pos)添加一个元素~
（注：并不是在 pos 之后插入数据，而是将数据放在 pos 的位置上，其余位置向后移动）
就像赛跑的时候，你超越了第二名，但你并不是第一名，只是第二名~
📚 还是让我们看看这个功能在 MyArrayList 中是如何实现的：
📌 该方法需要判断 pos 的合法性
📌 该方法需要将位于 pos 以及之后的元素后移一位
📌 该方法仍需要判断顺序表是否已满，并自动扩容
首先为了判断 pos 的合法性，我们需要自定义一个异常类，用于在 pos 访问不合法时报错并给予提示：
public class PosIllegal extends RuntimeException{public PosIllegal(){}public PosIllegal(String message){super(message);}
}
随后我们还需要判断 pos 是否合法：
private boolean checkPosInAdd(int pos) {if(pos > usedSize + 1 || pos < 0){throw new PosIllegal("pos的位置不合法");}return true;//合法}（注：pos 是可以等于 usedSize 的，当 pos = usedSize 时，此时为尾插）
// 在 pos 位置新增元素public void add(int pos, int data) {if(checkPosInAdd(pos)){usedSize++;if(isFull()) {elem = Arrays.copyOf(elem, elem.length << 1);}for (int i = usedSize - 2; i >= pos; i--) {elem[i + 1] = elem[i];}elem[pos] = data;}}📚 让我们检验一下：
📕 pos 不合法：
📕 pos 合法：
⑤ ArrayList.contains(int toFind)
ArrayList 的 contains 方法的作用：用于判断ArrayList中是否包含指定的元素。
📕 能查找到则返回 true
📕 查找不到则返回 false
📚 接下来我们模拟实现 contains(int toFind) 方法：
只需要拥有查找指定元素的功能就行了~想查找到一个元素的方法很多，最简单的方式就是遍历数组，但既然是自己实现，就多写写自己不熟悉的代码嘛~不然怎么能起到练习的作用呢，所以我打算使用二分来实现 contains 方法。
二分就需要我们先定义一个 left 和一个 right 表示起始点和终点(查找范围)，并且每一步都求出两者的中间值 mid ，通过判断"顺序表 mid 位置的元素大小" 和 "toFind" 的大小，从而移动 left 和 right 的位置，以此慢慢缩短距离，找到 toFind ：
// 判定是否包含某个元素public boolean contains(int toFind) {int l = 0;int r = usedSize - 1;while(l < r){int mid = l + r >> 1;if(toFind <= elem[mid]){r = mid;}else {l = mid + 1;}}if(elem[l] == toFind){return true;}return false;}
⑥ ArrayList.indexOf(int toFind)
ArrayList 的 indexOf 方法的作用是：用于返回指定元素在ArrayList中首次出现的索引位置。如果ArrayList中不包含该元素，则返回-1。
上面我所写的二分代码，就是能够遇到重复数字时，只查到第一次出现的，所以我们只需要稍微改动即可：
// 查找某个元素对应的位置public int indexOf(int toFind) {int l = 0;int r = usedSize - 1;while(l < r){int mid = l + r >> 1;if(toFind <= elem[mid]){r = mid;}else {l = mid + 1;}}if(elem[l] == toFind){return l;}return -1;}
⑦ ArrayList.get(int pos)
ArrayList的get方法用于返回指定索引位置上的元素。
这样用起来看着没什么问题，也很好实现，但不妨让我们在写两行代码呢：
📚 那么让我们试着实现一下 get(int pos) 方法：
📌 判断是否为空表
📌 判断 pos 是否合法
public class PosIllegal extends RuntimeException{public PosIllegal(){}public PosIllegal(String message){super(message);}
}
//判断是否为空表public boolean isEmpty() {if(usedSize == 0) {return true;}return false;} public int get(int pos) {if(isEmpty()){throw new ListIsEmpty("顺序表为空!");}if(pos > usedSize - 1 || pos < 0){throw new PosIllegal("pos的位置不合法!");}return elem[pos];}让我们再测试一下：
⑧ ArrayList.set(int pos,int value)
ArrayList的set方法用于将指定索引位置上的元素替换为新的元素。
该方法与上面的 add(int pos,int data) 方法类似，就不过多介绍了，大家一定能看懂的~
// 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, int value) {if(checkPosInAdd(pos)){elem[pos] = value;}}
⑨ ArrayList.remove(int key)
ArrayList的remove方法用于从列表中删除指定位置的元素或指定元素的第一个匹配项。
实现这个方法我们只需要使用上面用到的 indexOf() 方法找到指定元素后，将其删除，将之后的元素一一向前移动即可~（还需要注意检查是否为空表）代码：
public void remove(int key) {int index = indexOf(key);if(isEmpty()){throw new ListIsEmpty("顺序表为空!");}if(index < 0){return;}for(int i = index ;i < usedSize;i++){elem[i] = elem[i + 1];}usedSize--;}
⑩ size()与clear()
ArrayList.size() 方法的作用是返回 ArrayList 中元素的数量。
ArrayList.clear() 的作用是清空 ArrayList 中的所有元素，将其变为空列表。
// 获取顺序表长度public int size() {return usedSize;}// 清空顺序表public void clear() {usedSize = 0;}
四、模拟ArrayList完整代码
📖 MyArrayList.java
import java.util.Arrays;public class MyArrayList {public int[] elem;public int usedSize;private static final int DEFAULT_SIZE = 10;public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("[");for(int i = 0;i < usedSize;i++){sb.append(elem[i]);if(i != usedSize - 1){sb.append(", ");}}sb.append("]");return sb.toString();}// 新增元素,默认在数组最后新增public void add(int data) {if(isFull()){elem = Arrays.copyOf(elem,elem.length + (elem.length >> 1));}elem[usedSize] = data;usedSize++;}/*** 判断当前的顺序表是不是满的！** @return true:满 false代表空*/public boolean isFull() {if(usedSize >= elem.length) {return true;}return false;}private boolean checkPosInAdd(int pos) {if(pos > usedSize + 1 || pos < 0){throw new PosIllegal("pos的位置不合法");}return true;//合法}// 在 pos 位置新增元素public void add(int pos, int data) {if(checkPosInAdd(pos)){usedSize++;if(isFull()) {elem = Arrays.copyOf(elem, elem.length << 1);}for (int i = usedSize - 2; i >= pos; i--) {elem[i + 1] = elem[i];}elem[pos] = data;}}// 判定是否包含某个元素public boolean contains(int toFind) {int l = 0;int r = usedSize - 1;while(l < r){int mid = l + r >> 1;if(toFind <= elem[mid]){r = mid;}else {l = mid + 1;}}if(elem[l] == toFind){return true;}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {int l = 0;int r = usedSize - 1;while(l < r){int mid = l + r >> 1;if(toFind <= elem[mid]){r = mid;}else {l = mid + 1;}}if(elem[l] == toFind){return l;}return -1;}// 获取 pos 位置的元素public int get(int pos) {if(isEmpty()){throw new ListIsEmpty("顺序表为空!");}if(pos > usedSize - 1 || pos < 0){throw new PosIllegal("pos的位置不合法!");}return elem[pos];}public boolean isEmpty() {if(usedSize == 0) {return true;}return false;}// 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, int value) {if(checkPosInAdd(pos)){elem[pos] = value;}}/*** 删除第一次出现的关键字key*/public void remove(int key) {int index = indexOf(key);if(isEmpty()){throw new ListIsEmpty("顺序表为空!");}if(index < 0){return;}for(int i = index ;i < usedSize;i++){elem[i] = elem[i + 1];}usedSize--;}// 获取顺序表长度public int size() {return usedSize;}// 清空顺序表public void clear() {usedSize = 0;}
}📖 PosIllegal.java
public class PosIllegal extends RuntimeException{public PosIllegal(){}public PosIllegal(String message){super(message);}
}
📖 ListIsEmpty.java
public class ListIsEmpty extends RuntimeException{public ListIsEmpty(){}public ListIsEmpty(String message){super(message);}
}
那么关于ArrayList(顺序表)的知识就为大家分享到这里啦~作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦~