目录

1、List介绍

2、线性表

3、顺序表

4、实现自己的顺序表

4.1、display方法

4.2、add方法

4.3、contains方法

4.4、indexOf方法

4.5、get方法

4.6、set方法

4.7、remove方法

4.8、size方法

4.9、clear方法

---

1、List介绍

List是一个接口，继承自Collection

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作

List 常用方法如下：

2、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储

3、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。（顺序表：其实是一个动态扩容的数组）

为了更好的理解数据结构，我们先实现自己的顺序表，了解底层逻辑

4、实现自己的顺序表

定义一个IList接口（非必须），接口中的功能如下：

创建一个 MyArrayList 类并实现 IList 接口，重写 IList 中的所有方法

定义 elem 数组，用于存放数据；uesdSize，用于记录当前数组中数据个数

提供一个默认不带参数的构造方法，初始化数组容量为10；再提供带一个参数的构造方法，自定义初识容量

4.1、display方法

4.2、add方法

数据结构是一门逻辑非常严谨的学科，在实现具体功能之前，需要先判断合不合法

在add方法中，要先判断数组容量是否为满，满则扩容（copyOf）

把扩容写成一个方法，用 private 封装；这里用封装，是因为这个功能是解决其他功能需要包含的，只为当前类中的方法服务不是提供给用户用的

默认在数组最后新增 的实现

在pos位置新增元素，需要先判断 pos 位置合不合法，合法范围在 0 <= pos <= usedSize。例如，数组中有3个元素，只能在 [0,3] 下标插入,不能在 4 或 5 下标插入，因为在数据结构中每次存储数据的时候，必须有一个前驱信息

^

此时的处理方式是，再写一个 checkPosOnAdd 方法来检查pos的合法性，内容是当 pos 不合法时抛出一个异常；再自定义一个运行时异常 PosIllegality 类

在调用 checkPosOnAdd 方法时可能会抛出异常，所以要在这个方法后加上异常声明

在pos位置新增元素 的实现，使用 try-catch 的方式处理异常

4.3、contains方法

4.4、indexOf方法

4.5、get方法

先判断 pos 位置合法性，这里使用 checkPosOnGetAndSet 方法；再检查数组是否为空，这里采用的是抛出异常的方式，创建一个运行时异常 MyArrayListEmpty

4.6、set方法

4.7、remove方法

4.8、size方法

4.9、clear方法

一般情况下，直接把usedSize置为0

当顺序表中存储的是引用类型时，不能简单的将usedSize置为0，需要将数组一个一个置空