前言：
实现顺序表的代码放开头，供大家更好的查阅，每个方法都有代码的实现。
其次我会讲解Java自带的ArrayList的实例，扩容机制ArrayList使用方法，遍历以及它的优缺点。
目录
一、自己实现的顺序表
二、Java的ArrayList实例的扩容机制
三、ArrayList的使用
四、ArrayList的遍历
六、ArrayList的优缺点
一、自己实现的顺序表
package myarraylist;
//IList.java
public interface IList {
// 新增元素,默认在数组最后新增
void add(int data);
// 在 pos 位置新增元素
void add(int pos, int data);
// 判定是否包含某个元素
boolean contains(int toFind);
// 查找某个元素对应的位置
int indexOf(int toFind);
// 获取 pos 位置的元素
int get(int pos);
// 给 pos 位置的元素设为 value
void set(int pos, int value);
//删除第一次出现的关键字toRemove
void remove(int toRemove);
//删除全部出现的关键字toRemove
void removeAll(int toRemove);
// 获取顺序表长度
int size();
// 清空顺序表
void clear();
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
void display();
//判断数组满了没，能不能继续插入数据
Boolean isFull();
}
package myarraylist;
//posNotLegalException.java
public class posNotLegalException extends RuntimeException{
public posNotLegalException(){
}
public posNotLegalException(String msg){
super(msg);
}
}
package myarraylist;
//MyArrayList.java
import java.util.Arrays;
public class MyArrayList implements IList {
public int[] elem;
int usesize;
public MyArrayList() {
this.elem = new int[10];
}
//尾插
@Override
public void add(int data) {
if (isFull()) {
elem = Arrays.copyOf(elem, 2 * elem.length);
}
this.elem[usesize] = data;
this.usesize++;
}
@Override
public void add(int pos, int data) {
try {
posException(pos);
} catch (posNotLegalException e) {
e.printStackTrace();
}
if (isFull()) {
elem = Arrays.copyOf(elem, 2 * elem.length);
}
for (int i = usesize - 1; i >= pos; i--) {
elem[i + 1] = elem[i];
}
elem[pos] = data;
usesize++;
}
private void posException(int pos) throws posNotLegalException {
if (pos < 0 || pos > usesize) {
throw new posNotLegalException("pos位置不合法");
}
}
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usesize; i++) {
if (elem[i] == toFind) {
return true;
}
}
return false;
}
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usesize; i++) {
if (elem[i] == toFind) {
return i;
}
}
return -1;
}
@Override
public int get(int pos) {
try {
posExceptionOfGetAndSet(pos);
} catch (posNotLegalException e) {
e.printStackTrace();
}
return elem[pos];
}
@Override
public void set(int pos, int value) {
try {
posExceptionOfGetAndSet(pos);
} catch (posNotLegalException e) {
e.printStackTrace();
}
elem[pos] = value;
}
private void posExceptionOfGetAndSet(int pos) throws posNotLegalException{
if (pos < 0 || pos >= usesize) {
throw new posNotLegalException("get and set的pos位置不合法");
}
}
@Override
public void remove(int toRemove) {
int pos = indexOf(toRemove);
if (pos == -1) {
System.out.println("没有你要找的数据");
return;
}
for (int i = pos; i < usesize - 1; i++) {
elem[i] = elem[i + 1];
}
usesize--;
}
@Override
public void removeAll(int toRemove) {
for (int i = 0; i < usedSize; i++) {
if (elme[i] == toRemove) {
for (int j = i; j < usedSize -1; j++) {
elme[j] = elme[j + 1];
}
usedSize--;
}
}
}
@Override
public int size() {
return usesize;
}
@Override
public void clear() {
usesize = 0;
}
@Override
public void display() {
for (int i = 0; i < usesize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
@Override
public Boolean isFull() {
return usesize == elem.length;
}
}
二、Java的ArrayList实例的扩容机制
ArrayList是一个类，它有三个构造函数
既然分配的是0空间，为什么可以add元素呢？
当调用不带参数的构造方法进行add方法的时候，第一次add会分配大小为10内存，若内存，就会按照1.5倍扩容。
【总结】
1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要扩容的大小 初步预估按照1.5倍大小扩容 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容
public static void main(String[] args) {
//构建一个空的列表
List<Integer> list1=new ArrayList<>();
//十个容量的列表
List<Integer> list2=new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
//list3构建好之后，与list中的元素一致
ArrayList<Integer> list3=new ArrayList<>(list1);
//不要省略类型，因为里面什么都可以放，很混乱
List list4=new ArrayList();
list4.add("111");
list4.add(123);
}ArrayList和List有什么区别 ?
List是一个接口类型，ArrayList是一个类，这是他们两本质区别。
其次接口它能访问到的方法比较少，而ArrayList是当前对象的方法，所以ArrayList能访问到的方法比List多。
三、ArrayList的使用
Java自带的ArrayList常见的方法：
| 方法 | 功能 |
| boolean add(E e) | 尾插 e |
| void add(int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll(Collection c) | 尾插 c 中的元素 |
| E remove(int index) | 删除 index 位置元素 |
| boolean remove(Object o) | 删除遇到的第一个 o |
| E get(int index) | 获取下标 index 位置元素 |
| E set(int index, E element) | 将下标 index 位置元素设置为 element |
| void clear(） | 清空 |
| boolean contains(Object o) | 判断 o 是否在线性表中 |
| int indexOf(Object o) | 返回第一个 o 所在下标 |
| int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
| List subList(int fromIndex, int toIndex) | 截取部分 list（左闭右开） |
上面的E指的是泛型的种类（具体请看我之前的博客） ，
public static void main(String[] args) {
ArrayList<Integer> list=new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(0,0);
list.remove(0);
list.remove(1);
System.out.println(list);
System.out.println(list.contains(3));
list.get(2);
list.set(1,2);
System.out.println(list);
ArrayList<Integer> list1=new ArrayList<>();
list1.addAll(list);
System.out.println(list1);
//左闭右开
System.out.println(list.subList(1, 3));
}其实，我们自己实现的顺序表方法的功能跟这个也大差不差，我们自己实现一遍顺序表基本上就游刃有余了。这个表格也不要刻意去背，我们需要的时候顺着表格找就行了。
四、ArrayList的遍历
public static void main(String[] args) {
List<Integer> list=new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
//for循环遍历
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i)+" ");
}
System.out.println();
//foreach遍历
for (Integer integer:list) {
System.out.println(integer+" ");
}
System.out.println();
//迭代器
Iterator<Integer> it=list.listIterator();
while (it.hasNext()){
System.out.println(it.next()+" ");
}
System.out.println();
}用的比较多的是for和foreach（第一种和第二种），第三种简单了解就好了。
但是这里有个问题，为什么list要用get（i），不能直接list[i]呢？
答：list里面存的是Integer，而这东西是类，它不是简单的数据类型，Integer存的是地址，而不是值，相当于把值装箱（装箱也在我泛型博客右具体介绍）
六、ArrayList的优缺点
优点：
给了下标，找值特别快 ，复杂度是O（1）
缺点：
1.如果在任意位置插元素，删除元素。你需要用for循环，复杂度是O（N）
2.增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3.增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继 续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
问题：那有没有一种数据结构，可以解决顺序表的缺点？
答：有，那就是链表 。（下一篇博客）
