【List，ArrayList与顺序表】

目录

1，什么是List

2，List的使用

3，线性表

4，顺序表

4.1 接口的实现

5， ArrayList简介

6，ArrayList的使用

6.1 ArrayList的构造方法

6.2 ArrayList的常见操作

 6.3 ArrayList的遍历

7，ArrayList的具体使用

7.1 简单的洗牌算法

7.2 杨辉三角

7.3 面试题

8，ArrayList的优缺点

1，什么是List

在集合框架中，List是一个接口，继承自Collection。

Collection也是一个接口，继承自Iterable。

他的一些方法：

Iterable是最顶层的一个接口

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

List中提供了好的方法，具体如下：（部分）

2，List的使用

注意：List是个接口，并不能直接用来实例化。

如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。

3，线性表

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

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

4，顺序表

顺序表其实就是一个数组，数组本身是一块连续的内存

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

4.1 接口的实现

对数组进行增删改查：

定义一个IList接口：

定义MyArrayList类实现IList接口：

定义一个测试类Test：

接下来就对其接口里面的功能在重写方法里面一一完成：

1，新增元素，默认在数组最后新增

确定新增位置，只需要放到usedSize位置，usedSize+1即可。但是数据结构是一门非常严谨的学科，在这里我们还要判断数组是否已满！！！即在接口里面定义一个方法判断数组是否已满！

重写这个方法，若usedSize等于数组长度，则满

2，在pos位置新增元素

从最后一个数据往后面挪，才能插入指定位置，所以定义一个下标i，i的起始位置是usedSize-1的位置，把i位置的值赋值给i+1，在i--，i=pos都要移动，再将需要插入的元素存入pos位置，usedSize++即可！！！但是要考虑pos位置是否合法，不能usedSize，若满了扩容。

在MyArrayList类中写一个方法判断pos合不合法：

若不合法，可抛出一个异常，则定义一个异常类：

最终代码：

3，判定是否包含某个元素（给一个数，查找数组中是否包含这个数）

查找次数不用把整个数组查找完，只需要查找usedSize次即可

4，查找某个元素对应的位置

5，获取pos位置的元素

在这种情况下，pos不能等于usedSize，pos合法的位置只要0~usedSize-1，其他都不合法！

即写一个方法来判断pos位置元素是否合法：

6，给pos位置的元素设为value—>相当于更新

首先检查pos位置的合法性，不能pos=usedSize，即可直接调用checkPosofGet方法，可将此方法名修改一下，以便观察与理解

7，删除第一次出现的关键字key 

可定义一个下标i，代表你要删的位置，让i+1的值赋值给i下标的值，然后i++，再让i+1的值赋值给前面的值，走到i