•  List接口是由多个类实现的：1、ArrayList类 2、LinkedList类 3、Vector类（通过Stack类实现）
• 学习List接口：1、学习ArrayList类 -> 2、学习顺序表 -> 3、学习线性表

1、线性表

• 定义：相同特性数据元素的有限序列，线性表就是一种数据结构；
• 常见的线性表：顺序表、链表、栈、队列... 
• 线性表在逻辑上是线性结构，也就是说在逻辑上是连续存储的；但是在物理结构上就不一定连续存储；

---

2、顺序表

• 顺序表就是在物理结构上连续存储的一种线性结构；
• 顺序表是采用数组进行存储数据的，所以是连续存储；
• 顺序表中主要实现的功能就是对数据进行增删改查，也就是对数组进行增删改查；

• -> 为什么不直接使用数组进行存储呢？

  1. 数组并不能实现一些特有功能
  2. 顺序表就是在数组的基础上增加一些特有的功能和方法
  3. 将带有特有功能的数组，组织成一种新的数据类型，这个新数据类型就是顺序表
• 顺序表是一种新的数据类型，这种新的类型是用来操作数组的；

---

顺序表的实现（MyArrayList）

• 我们在写这个顺序表时，首先要明白顺序表是什么；
• 顺序表中主要实现的功能就是对数据进行增删改查，也就是对数组进行增删改查；
• 我们需要通过三方面进行编写代码：1、MyArrayList类（也就是顺序表类）  2、ArrayListInterface接口（也就是功能接口） 3、异常类，所以代码大的分为了这三部分；

 

---

1、MyArrayList类

重点、难点：新增方法

重点、难点：删除方法

MyArrayList代码：

package ArrayList;import java.util.Arrays;/***  顺序表就是使用数组实现的，只是有一些特有的功能*  1、先要有一个数组*  2、获取到顺序表的长度->这个长度就是数组使用长度*  3、打印顺序表->遍历数组*  4、新增元素->注意：新增完元素后一定要将useSize++*  5、判断当前位置是否合法->不合法应该抛出异常*  6、查找元素、获取元素下标、获取元素*  7、删除元素->1、判断顺序表是否为空；2、查找元素下标；3、从前向后依次覆盖*  8、清空顺序表*/
public class MyArrayList implements ArrayListInterface{public int[] array; // 定义的数组public int useSize; // 数组使用的大小public static final int DEFAULT_CAPACITY = 10; // 数组默认大小10// 初始化public MyArrayList() {// 将数组初始化this.array = new int[DEFAULT_CAPACITY]; // 初始化数组}@Overridepublic int size() {// 因为是数组使用长度，并且使用长度是公开的,所以直接返回return useSize;}@Overridepublic void display() {// 打印顺序表// 也就是遍历顺序for (int i = 0; i < size(); i++) {// 将数组中的所有元素打印出来System.out.print(array[i] + " ");}System.out.println();}@Overridepublic void add(int data) {// 增加元素，默认增加到数组的最后位置// 1、数组是否满 -> 所以先写isFullif(isFull()) {// 满了进行扩容array = Arrays.copyOf(array,array.length);}// 满了之后会进行新增元素,没满也会进行新增元素,所以新增元素写在外面// 将useSize位置放上这个元素array[useSize] = data;// 新增一个元素之后需要将useSize++useSize++;}@Overridepublic boolean isFull() {// 判断一下，数组是否满// 满了并不代表数组越界，所以这里的判断应该是==// 我最开始写的是>=if(useSize == array.length) {return true; // 如果满了，返回true}return false; // 没满返回false}@Overridepublic boolean isEmpty() {// 判断是否为空// 顺序表中没有任何元素时则为空if(useSize == 0) {return true;}return false;}@Overridepublic void checkPosInAdd(int pos) {// 判断当前位置是都合法// 当前的下标小于0，大于数组长度 -> 这样考虑是有缺陷的，如果当前位置前面是null，那么就不能新增元素的；// 所以当前位置大于的不是数组长度，而是大于useSize+1处就不能新增元素了if(pos < 0 || pos > size()) {// 其实不合法应该抛出异常的// System.out.println(pos + "当前位置不合法");throw new PosException(pos + "当前位置不合法");}System.out.println(pos + "当前位置合法");}@Overridepublic void add(int pos, int data) {// 在特定位置新增元素// 当前位置是否合法?// 如果数组是满的呢？checkPosInAdd(pos);if(isFull()) {array = Arrays.copyOf(array,array.length);}// 位置合法情况下// 在此位置处，需要先将元素向后移动// 这里有一个细节useSize-1，下标比长度少1for (int i = useSize-1; i >= pos; i--) {// 从后向前移动元素// 将前一个元素放到后一个元素的位置array[i+1] = array[i];}// 新增元素// 最后useSize++array[pos] = data;useSize++;}@Overridepublic boolean contains(int data) {// 查找当前元素是否存在for (int i = 0; i < size(); i++) {if(array[i] == data) {return true;}}return false;}@Overridepublic int indexOf(int data) {// 返回的是当前值的下标for (int i = 0; i < size(); i++) {if(array[i] == data) {return i; // 存在返回下标}}return -1; // 不存在返回-1// 数组中没有-1这个下标}@Overridepublic int get(int pos) {// 获取特定位置的元素// 判断位置是否合法checkPosInAdd(pos);// 最开始我写的时候，少了一个判断条件// 如果这个顺序表为空，就没有获取到任何元素if(isEmpty()) {// 如果顺序表为空，抛出异常throw new EmptyException("顺序表为空");}// 合法情况,直接返回该位置元素return array[pos];}@Overridepublic void set(int pos, int value) {// 给特定位置更新元素值// 判断位置是否合法checkPosInAdd(pos);// 这是给已经有值的位置更新值// 如果顺序表为空就没法更新if(isEmpty()) {// 如果顺序表为空，抛出异常throw new EmptyException("顺序表为空");}// 合法情况,直接返回该位置元素array[pos] = value;}@Overridepublic void remove(int key) {// 1、顺序表是否为空// 2、查找要删除数的下标// 3、从前向后一次覆盖if(isEmpty()) {throw new EmptyException("顺序表为空");}int pos = indexOf(key); // 查找key元素的下标// 找到key元素下标后，进行删除元素// 删除元素：当前下标，从前向后依次覆盖for (int i = pos; i < size()-1; i++) {// 后一个元素覆盖前一个元素array[i] = array[i+1];}// 删除之后useSize--useSize--;}@Overridepublic void clear() {// 清空顺序表，防止内存泄漏// 将每一个对象都置为null// 因为这里的对象全都是int类型// 所以只需要将useSize置为0useSize = 0;}
}

---

2、 ArrayListInterface接口

size() -> 获取顺序表的长度，这个长度是顺序表的使用长度

display() -> 打印顺序表

add() -> 新增元素，默认新增到顺序表的最后

isFull() -> 判断当前顺序表是否满

isEmpty() -> 判断当前顺序表是否为空

checkPosInAdd() -> 判断当前位置是否合法

contains() -> 查看顺序表中是否包含某个元素

indexOf() -> 根据元素返回下标

get() -> 根据位置返回元素

set() -> 更新某个下标的值

remove() -> 删除第一次出现的某个元素

clear() -> 清空顺序表

 ArrayListInterface代码：

package ArrayList;/***  顺序表中的功能*  这些接口中的功能都需要类去实现*/public interface ArrayListInterface {// 获取顺序表的长度->这个长度是使用长度int size();// 打印顺序表// 根据useSize判断void display();// 新增元素// 默认新增到数组的最后void add(int data);// 判断当前顺序表是否满boolean isFull();// 判断当前顺序小是否为空boolean isEmpty();// 判断当前位置是否合法void checkPosInAdd(int pos);// 在特定位置新增元素// 实现了方法的重载void add(int pos, int data);// 查找是否包含某个元素boolean contains(int data);// 查找某个元素对应位置int indexOf(int data);// 获取特定位置的元素int get(int pos);// 给特定位置元素更新新值void set(int pos, int value);// 删除第一次出现的某个值void remove(int key);// 清空顺序表void clear();
}

---

3、异常类 

1、PosException代码：

package ArrayList;public class PosException extends RuntimeException{// PosException是一个运行时异常// 写一个构造方法(有参数、无参数)public PosException(){}public PosException(String message){super(message); // 调用父类}
}

2、EmptyException代码：

package ArrayList;public class EmptyException extends RuntimeException{public EmptyException(){}public EmptyException(String message){super(message);}
}

---

认识顺序表 （ArrayList）

ArrayList的构造方法

// 在学习一个类时，首先学习这个类的构造方法ArrayList<Integer> arrayList = new ArrayList<>(); // 实例化不带参数的构造方法System.out.println("实例化不带参数的构造方法");arrayList.add(1);arrayList.add(2);arrayList.add(3);System.out.println("--------------------------------------------------------------------------");ArrayList<Integer> arrayList1 = new ArrayList<>(10); // 这是实例化带参数的构造方法System.out.println("实例化带参数的构造方法，为内存分配空间");arrayList.add(10);arrayList.add(20);arrayList.add(30);System.out.println("--------------------------------------------------------------------------");ArrayList<Integer> arrayList2 = new ArrayList<>(arrayList);System.out.println("这是带参数的构造方法");System.out.println("可以这样实例化的原因是：");System.out.println("1、后面括号中arrayList这个类是Collection的子类；");System.out.println("2、arrayList这个类的类型是Integer;");System.out.println("3、E是Integer类型，arrayList这个类的类型是E这个类或这个是E的子类都可以");System.out.println("--------------------------------------------------------------------------");

---

ArrayList的输出

 

// 顺序表的输出System.out.println("顺序表没有具体的方法实现顺序表的输出，可以通过以下方法进行输出：");// soutSystem.out.println("sout输出顺序表");System.out.println(arrayList2);System.out.println("--------------------------------------------------------------------------");// foriSystem.out.println("fori输出顺序表");for (int i = 0; i < arrayList2.size(); i++) {// 这样输出是错的，这是顺序表，不是数组；顺序表是使用数组实现的// System.out.println(arrayList2[i]);System.out.print(arrayList2.get(i) + " ");}System.out.println();System.out.println("--------------------------------------------------------------------------");// foreachSystem.out.println("foreach输出顺序表");for (Integer x:arrayList2) {System.out.print(x + " ");}System.out.println();System.out.println("--------------------------------------------------------------------------");// 迭代器输出顺序表System.out.println("迭代器输出顺序表");System.out.println("因为：顺序表是Iterable这个接口的子类，所以可以使用迭代器进行输出");System.out.println("iterator()这个方法的返回值是Iterator<E>");Iterator<Integer> y = arrayList2.iterator();while(y.hasNext()) {// 判断y的下一个位置是否有值System.out.print(y.next() + " "); // 输出y的下一个值}System.out.println();System.out.println("listIterator()这个方法的返回值是ListIterator<E>");ListIterator<Integer> z = arrayList2.listIterator();while(z.hasNext()) {// 判断z的下一个位置是否有值System.out.print(z.next() + " "); // 输出z的下一个值}System.out.println();System.out.println("--------------------------------------------------------------------------");

---

 ArrayList的方法（subList）

// ArrayList中的subList方法System.out.println("subList：左闭右开的方法，实现的是顺序表的截取");System.out.println("但是subList这个方法并没有开辟新的空间，而是指向所截取顺序表的空间");System.out.println("subList()这个方法的返回值是List<E>, 所以需要使用List<E>接收");System.out.println();System.out.print("这是从arrayList2这个顺序表截取的值，输出list：");List<Integer> list = arrayList2.subList(0,2);System.out.println(list);System.out.print("修改截取后的值，将下标为0处修改为111，输出修改后的list：");list.set(0,111);System.out.println(list);System.out.print("输出顺序表arrayList2：");System.out.println(arrayList2);System.out.println("说明：subList这个方法并没有开辟新的空间，而是指向所截取顺序表的空间");System.out.println("--------------------------------------------------------------------------");

---