从本博客起，我将带大家学习Java当中的数据结构。
那让我们从顺序表开始吧，本博客内容包括但不限于实现一个自己的ArrayList、相关的API介绍、相关API的实现以及使用。
一.顺序表概述
1.ArrayList的位置
顺序表（ArrayList）是线性表（List）的一种，继承自AbstractList类，并实现了List接口，以下是它在Java继承体系中的位置：
2.ArrayList的结构
逻辑结构：元素的有序序列
物理结构：顺序存储
ArrayList的本质是基于数组的连续存储结构，最大的优势就是对于确定位置的元素访问及其方便。
如下是它的存储示意图：
只要知道数据下标，就可以快速拿到元素，时间复杂度为O(1)。
二.ArrayList的实现
ArrayList在jdk当中的实现有足足1732行，我们挑选了部分核心方法来实现：
ps：想要查看源码，按住Ctrl+Alt选中ArrayList并点击，弹出选项框点击要查找的类即可：
想要深入了解建议查看源码，不过不建议初学者看源码，因为涉及一些Java高级特性。
核心方法
我们要实现的核心方法如下（为了学习，简便，先不考虑泛型）：
// 新增元素,默认在数组最后新增public void add(int data) {}//判断是否已满public boolean isFull() {}// 在 pos 位置新增元素public void add(int pos, int data) {}// 判定是否包含某个元素public boolean contains(int toFind) {}// 查找某个元素对应的位置public int indexOf(int toFind) {}// 获取 pos 位置的元素public int get(int pos) {}// 给 pos 位置的元素设为 value [更新]public void set(int pos, int value) {}//检查pos位置是否合法private void checkPos(int pos) { }//删除第一次出现的关键字keypublic void remove(int toRemove) {}// 获取顺序表长度public int size() {}// 清空顺序表public void clear() {}1.属性
Java当中顺序表的存储结构如下：
嗯......这可能有些复杂，为了方便学习，我们简化一下：
先不考虑泛型实现，也不考虑io流，这些以后再说！我们假设存储的元素都是整形，那我们自己的ArrayList就有了3个属性：
用来存储的结构，数组
用来表示有效元素的个数的数，usedSize
用来初始化数组大小的自定义常量，DEFAULT_SIZE
ok！这下我们的ArrayList就初步构建完成。
2.构造方法
//默认初始化public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}//指定容量初始化public MyArrayList(int initCapacity) {this.elem = new int[initCapacity];}初始化之后，我们就可以操作顺序表了，即增、删、查、改。
3.增
//新增元素public void add(int data) {if (isFull()) {this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSize] = data;this.usedSize++;}//在 pos 位置新增元素public void add(int pos, int data) {if (isFull()) {this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}checkPos(int pos)for (int i =usedSize-1; i > pos; i--) {this.elem[i+1] = this.elem[i];}this.elem[pos] = data;this.usedSize++;}//判断非满public boolean isFull() {if (this.usedSize == this.elem.length) {return true;}return false;}//检查位置是否合法private void checkPos(int pos) {if (pos < 0 || pos >this.elem.length) {throw new PosOutOfBoundsException("pos out of bounds!");}}我们提供2种新增元素方式，即默认新增和指定位置新增，它们构成了方法的重载。
在新增元素之前，我们必须检查数组是否已满，否则就可能发生StackOutOfBounds异常。判断是否已满的方式很简单，只要比较有效元素个数是否等于数组长度即可（.length为数组自带属性）。
如果数组已满，我们就要扩容，扩容方式是调佣Arrays方法库中的复制数组，并指定大小为2倍，再赋值给原数组elme。随后就可以新增元素了。
默认新增：在数组的末尾添加元素，直接this.elem[this.usedSize] = data即可。
指定位置（下标）新增：首先我们要判断这个“位置”是否合法，使用私有方法checkPos()，即是否在原数组边界外（由于是线性表，元素必须是连续的，不能空一个元素），不合法抛出我们自定义异常PosOutOfBoundsException，合法则把所有pos后元素后移一位，然后插入即可。
4.查
//判定是否包含某个元素
public boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (this.elem[i] == toFind) {return true;}}return false;
}//查找某个元素对应的位置
public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (this.elem[i] == toFind) {return i;}}return -1;
}//获取 pos 位置的元素
public int get(int pos) {checkPos(pos);return this.elem[pos];
}5.删
删除一个元素，我们有2件事要做，即找到那个元素位置、把之后的元素前移1格覆盖要删除的元素。
//删除第一次出现的关键字key
public void remove(int toRemove) {int index = this.indexOf(toRemove);if (index == -1) {System.out.println(toRemove + " is not found!");return;}for (int i = index+1; i < this.elem.length; i++) {this.elem[i] = this.elem[i-1];}this.usedSize--;
}
indexOf()方法实现了查找某元素位置，remove()则实现删除，即前移后置元素，这里的实现很简单，就不赘述了。
6.改
// 给 pos 位置的元素设为 value [更新]
public void set(int pos, int value) {checkPos(pos); //任然要检查位置是否合法this.elem[pos] = value;
}7.其他
一些其他方法的实现：
//展示元素
public void display() {for (int i = 0; i <= usedSize; i++) {System.out.print(elem[i] + " ");}
}// 获取顺序表长度
public int size() {return this.usedSize;
}// 清空顺序表
public void clear() {this.usedSize = 0;
}
三.ArrayList常用方法使用示例
以下代码给出了常用方法的使用方法，供大家学习参考：
import java.util.ArrayList;
import java.util.Arrays;public class ArrayListDemo {public static void main(String[] args) {// 1. 初始化List<String> fruits = new ArrayList<>();//ArrayList<String> fruits = new ArrayList<>()也可System.out.println("初始化列表: " + fruits); // []// 2. 添加元素fruits.add("Apple"); // 末尾添加fruits.add(0, "Banana");// 指定位置插入fruits.addAll(Arrays.asList("Orange", "Grape"));System.out.println("添加元素后: " + fruits); // [Banana, Apple, Orange, Grape]// 3. 访问元素System.out.println("\n访问元素演示:");System.out.println("索引1的元素: " + fruits.get(1)); // AppleSystem.out.println("列表大小: " + fruits.size()); // 4System.out.println("包含Orange? " + fruits.contains("Orange")); // trueSystem.out.println("Mango的位置: " + fruits.indexOf("Mango")); // -1// 4. 修改元素System.out.println("\n修改元素演示:");fruits.set(2, "Lemon");System.out.println("修改后: " + fruits); // [Banana, Apple, Lemon, Grape]// 5. 删除元素System.out.println("\n删除元素演示:");fruits.remove("Banana"); // 按对象删除fruits.remove(0); // 按索引删除System.out.println("删除后: " + fruits); // [Lemon, Grape]// 6. 其他操作System.out.println("\n其他操作演示:");System.out.println("是否为空? " + fruits.isEmpty()); // false// 遍历方式1：for循环System.out.print("for循环遍历: ");for(int i=0; i<fruits.size(); i++){System.out.print(fruits.get(i) + " ");}// 遍历方式2：增强for循环System.out.print("\n增强for循环: ");for(String fruit : fruits){System.out.print(fruit + " ");}// 遍历方式3：forEach方法，fruit会在集合内遍历，结合Lambda表达式可以减少代码量System.out.print("\nforEach方法: ");fruits.forEach(fruit -> System.out.print(fruit + " "));// 清空列表fruits.clear();System.out.println("\n清空后: " + fruits); // []}
}说明1：初始化时，有2种选择：
List<T> list = new ArrayList<>()
ArrayList<T> list = new ArrayList<>()2种方式区别不大，但大部分情况下选择第一种，由于多态特性，虽然不能用ArrayList的特定方法，但是不指定实际绑定类型，可以让list有更灵活的转变可能，如转换成链表（虽然大部分情况下不使用）：
List<String> list = new ArrayList<>();
list.add("Java");
list = new LinkedList<>(); // 允许替换实现合理选择初始化方式，可以让代码在灵活性和功能性之间达到最佳平衡。这也是 Java 集合框架设计的精髓所在。
当然，实际情况实际选择，如需要调用ArrayList特有方法，请用ArrayList类型初始化。
说明2：第三种方法结合了Lambda表达式，使循环更为简洁高效，并且这种方式支持链式编程，可以大大节省代码量，是现代编程首选。
另外，此处还等价于：
fruits.forEach(System.out::println);详情请参考Lambda表达式的使用及其化简。
结语
阅读过源码的朋友应该知道Java内部的实现比这要复杂一些，涉及了很多高级特性，但是其核心的方法内涵就是这么简单，了解了这些后，使用ArrayList就能更加得心应手。
觉得有帮助不妨点个赞，下一篇我们将介绍链表，链表的一些方法和特性比顺序表复杂很多，我们会更加详细地讲解。
