一  线性表

1.定义：线性表中的元素呈线性排列，一个元素只有一个前驱和一个后继

2.分类：

（1）顺序表：ArrayList（新版本）与Vector（旧版本）

（2）链表：LinkedList

（3）栈

（4）队列

注：上述集合类都实现了List接口，并且该接口继承自Collection

二  顺序表的定义

1.解释：顺序表是基于数组实现，其在数组的基础上增加了增删改查功能（与数组的主要区别），是对数组的进一步封装

2.特点：

（1）元素的在数组中连续存放

（2）存放线性结构的数据

3.对顺序表的实现的集合类：ArrayList（新版本）与Vector（旧版本）

区别：线程是否安全

ArrayList为线程不安全，在单线程下可以使用

多线程下则需要使用Vector

三  ArrayList的基本用法

1.指定该顺序表中存放的类型

注：若为基础类型则需要使用包装类（这也是引入包装类的原因，让基础类型也与类这个语法成一个体系）

2.初始化（构造方法）

（1）无参构造法

区别：

ArrayList<String> list=new ArrayList<>();

分析：此时创建了一个新的顺序表，可以往里面添元素，但是其内部当前没有元素（相当于一个空盒子）

ArrayList<String> list=null;

分析：此时不存在一个顺序表，不能往里面添元素（相当于连一个空盒子都没有）

（2）指定容量构造方法：创建顺序表时加上容量

（3）利用其他Collection来构建顺序表

注：前面写类型时，有一些写法是写成List<>

例如：

List<>  list=new ArrayList<>();

好处：

（1）对使用的类进行进一步封装，使使用者不用知道这是什么类型的数据结构就可以进行使用，降低使用成本

（2）后续要改变数据结构调整类型时对调用者无感

四  ArrayList提供的基本方法

前提：只要有出现index，需要用到下标的地方，都要考虑下标是否越界的情况（即下标要满足>=0且<size（判断下标的合法性很重要，后面模拟实现的时候也需要对下标异常的情况进行异常处理）

1.添加操作：

（1）头插：addFirst

（2）尾插：add

（3）随机位置插入：add（int index，Object obj）

注：注意此处在index插入元素后该元素的下标的就为index（就像跑步比赛超过第二名后你就为第二名）

（4）添加该顺序表元素的数据：addAll（Collection list）

2.删除

（1）根据下标来删除（返回被删除的值）：remove（int index）

（2）根据元素来删除（返回是否删除成功）：remove（Object obj），删除第一个出现的该元素
注：特殊情况：当顺序表中存放为整形数据时使用remove方法

当传入参数为内置类型时，其作为下标，调用根据下标来删除的方法

当传入的参数为整形的包装类时，其作为元素，调用根据元素来删除的方法

（3）删除内含该顺序表元素的数据：removeAll（Collection list）

3.设置和得到方法：set（int index，Object obj）get（int index）

注：get和set方法的底层还是基于数组进行实现的，数组的[]是非常高效的操作，其时间复杂度都为O（1）

4.清除顺序表中元素：clear（Collction list）

注：清空顺序表中的元素，相当于保留一个空盒子

5.判断是否包含该元素：contains（Object obj）

6.截取其部分元素：sublist（int fromIndex，int toIndex）

此处的sublist并不是拷贝了原顺序表的一部分，其就是原本list的原片段，对sublist得到的顺序表进行更改会影响原本的list

注意：计算机中的区间为前闭后开，所以toIndex可以等于size

7.获取元素下标

（1）从前往后遍历：indexOf（Object obj）获取到从左往右第一个值为obj的元素的下标

（2）从后往前遍历：lastIndexOf（object obj）获取到从右往左第一个值为obj元素的下标

（3）指定位置开始遍历

（i）指定位置从前往后遍历：indexOf（int pos，Object obj）从pos这个位置开始往后遇到的第一个值为obj的元素的下标

（ii）指定位置从后往前遍历：lastIndexOf（int pos，Object obj）从pos这个位置开始往前遇到的第一个值为obj的元素的下标

注：借助指定位置开始遍历可以得到第二个obj的下标第三个obj的下标或倒数第二个obj的下标

方式：先利用indexOf/lastIndexOf先得到第一个obj的下标，将该下标加一，作为指定位置的实参，对应要找的值作为obj的实参，这样得到的下标就为第二个obj的下标

得到的下标再加一，作为实参，从这个位置往后遍历得到的下标就是第三个obj的下标

同理利用lastIndexOf也可得到倒数第几个元素的下标

8.顺序表的遍历

（1)使用下标遍历：for循环+get方法

（2）使用for-each遍历（只用于读，不可写）

例：for（Integer elem：list）

相当于把list中的元素一个个赋给elem，对elem的改变不会影响到顺序表中的元素

注：此时的for-each遍历相当于简化版本的迭代器

（3）使用迭代器遍历：适用于所有实现了Iterable接口的类

补充：迭代思想

解释：一步一步接近最终成果

应用：不仅用于编程语言，还用于开发项目等，例如开发一个比较大的项目时，先把所有要实现的功能全都列出来，挑里面最关键的二十个进行实现，然后发布上市，再接着挑出次重要的二十个进行实现，并且在这过程中不断吸收用户的评价反馈跟进，这样一轮就称为一次迭代，最终一步步去完成这个最终目标，才能让产品跟上市场发展的速度

（i）得到迭代器：

迭代器是一个泛型类，其泛型参数要与集合类的泛型参数相同

迭代器不是创建的，而是集合类里自带的，为集合类的内置对象，获取的是哪个顺序表的迭代器，对应其遍历的就是谁

Iterator<类>  iterator=list.iterator();

（ii）利用循环判断其迭代器后是否有元素

使用iterator的hasNext方法

（iii）然后利用迭代器的next方法获取到当前元素并且迭代器后移一位

注：

（1）此时的迭代器相当于光标，一开始这个光标指向顺序表的第一个元素的前面

（2）与Scanner类似，这是Java中迭代器写法的典型风格，不仅是集合类

9.获得顺序表的元素个数：使用size方式

区别：

数组长度：使用.length访问length属性

字符串长度：使用.length（）方法得到字符串长度

顺序表：使用size（）得到顺序表中元素个数

注：这几种方式不相同要注意区分

10.扩容机制

（1）作用：ArrayList的底层是基于数组实现的，但数组一旦创建其长度就为固定了，可能存在容量不够的情况，扩容机制就是用于解决这种情况存在的

（2）触发：当数组个数大于等于数组长度时会自动触发

（3）扩容大小：扩容大小为原来的1.5倍

扩的大小过大：占用内存空间，导致内存空间的浪费

扩的大小太小：内存空间很快又不够用，又得重新扩容拷贝，成本也较高

（4）内部实现：虽然数组的长度无法改变，但可用一个容量更大的数组来代替旧数组

（i）先创建一个数组长度为原来1.5倍的新数组

注：此处的1.5倍有两种写法

data.length*1.5和data.length+(data.length>>1)

第二种写法：

分析：data.length>>1相当于对原数*0.5

原因：计算机计算移位表达式时比计算四则运算更高效（正常情况写第一种写法就可以了）

（ii）利用for循环将旧数组的元素赋值给新数组

（iii）将类中的数组引用指向新数组

注：此时将新数组的引用赋给原来存储旧数组的引用，此时没有引用指向旧数组，JVM就会自动触发垃圾回收机制，将存储在堆上的旧数组进行回收

解释：需要先创建新引用，再将新引用赋给ArrayList中数组引用的原因：直接将新数组引用放于旧数组引用中会导致旧数组的回收，无法将旧数组的元素赋值到新数组中

（5）时间复杂度：由于每个扩容都需要将旧数组的元素拷贝到新数组，时间复杂度为O（N）

注：扩容机制本身也属于一个高风险高成本的操作（例如：如果原本的元素就很多了其就会涉及大量的内存拷贝操作）

五  ArrayList使用相关的习题

1.发牌操作：

（1）利用顺序表来存储牌（使用add将牌添加到顺序表中）

（2）洗牌：利用Collection类中的shuffle方法（打乱顺序表中的顺序）

补充：

工具类：由于方法不能单独于类存在，必须存放于类中，而这些方法又不需要具体的实例来调用（即和类本身没有什么关系，不依赖类的属性和方法，也不需要进行重写），所以利用工具类将这些方法进行组织和规整（直接通过类名即可调用该方法）

判断：如果某个类都是静态方法，则称其为工具类

常见工具类：

Collections：存放用于操作集合类的方法

Arrays：存放用于操作数组的方法

（iii）发牌：先创建一个顺序表数组，每一个顺序表表示一个玩家，用于存放该玩家的所有的牌

发五轮，每一轮要发给三个玩家，利用两个for循环，第一个表示轮数，第二个表示玩家数

先将这张牌从牌堆中移除（remove）并创建新引用存放他，再利用add方法将其添加到对应玩家的顺序表中作为牌

2.杨辉三角

 （1）思路：

创建一个二维的顺序表，其顺序表中的元素又是一个顺序表，每一个顺序表顺下来分别代表一行，分别去添加每一行的内容

添加：利用两个for循环，第一个for循环代表一行，第二个for循环代表每一行的每一个元素，第二个for循环结束时代表这一行添加元素完毕

（2）步骤：

（i）在第一个for循环中创建一个顺序表添加到二维顺序表中，接下来对这个顺序表进行元素的添加

（ii）在第二个for中完成对元素的添加：添加的元素位置有两种情况，一种是首位和末尾的元素固定为1，一种是该元素为上一行的前一个位置和同位置的两个元素相加（需要借用二维顺序表得到上一个顺序表及其元素）

（iii）添加结束后返回该二维顺序表

（3）注意：注意返回值的兼容性

区别于：二维顺序表看是否为实现了该接口的类/继承该父类的类

要点：看最外层的那部分，里层需要保持一致

例如：

List<List<Integer>>是接口

ArrayList<List<Integer>>可以视为实现了该接口的类（其内部的泛型参数是一致的）

ArrayList<ArrayList<Integer>>则不是实现该接口的类（其内部的泛型参数不一样，泛型参数在看的时候就没有实现该接口/该类的子类的兼容性了）

注：因此要注意返回的那个参数的类型与返回值类型是否兼容

3.注意事项：

（1）情况：当满足相等情况对数组进行搬运，让后面的元素代替前面那个满足相等情况的元素后，此时如果直接对下标进行++，那么会导致新代替上来的这个元素没有进行是否相等的情况判断后就被跳过了，会导致有元素被遗漏

解决：本次循环有进行遍历替代的情况，替换后先不进行++，针对新替代上的这个元素进行判断，确定其不满足相等的情况时再对其进行++操作

(2)非递减顺序：前后不能一大一小，可以有相等的情况（相当于递增的弱化版本）

六  ArrayList的内部实现

内部实现特别注意的前提和点：

（1）当前元素个数是否大于等于数组长度，如果是，则需要触发扩容机制

（2）要判断用户所传入的下标参数是否合法性，不合法要抛出异常，对其进行异常的处理

注：无法确定用户会传入什么样的参数，所以在使用前一定要对用户传入的参数的合法性进行判断

作为调用者，在使用时要进行判断，作为实现者无法确定用户传进来的参数，也要进行判断

调用者和实现者同时进行检查，称为double check，确保有一方出错也不会造成严重后果

注：虽然实现时不对其进行异常处理其在运行过程中系统也会抛出错误

但在面试中写程序对合法性和异常的处理是至关重要的，体现出一个人写代码的意识

面试现场写代码，一般不关注结果，而关注其写的过程

比如以下这些点

（1）拿到问题后如何思考

（2）是如何将问题分解，一步步进行实现

（3）代码的风格和习惯（比如写注释等）

（4）处理问题的手段（写的过程中遇到问题是如何解决的）

（5）其他方面的一些代码意识（合法性的判断，异常的处理等）

1.基本属性：

（1）ArrayList是基于数组创建的，所以其要有一个引用指向其内部的数组

（2）有一个size来记录此时数组的有效元素

注：模拟实现一般不给其增添泛型参数，其实现起来较为复杂，正常情况下按String类型来进行实现既可

（3）构造方法：

（i）无参构造法：自己设定其默认容量为多少

（ii）设定初始容量：要注意传入的容量是否合法/容量本身是否太小对其进行调整

（iii）利用其他顺序表进行构造

2.添加：注：所有的添加操作结束后都要对size进行自加

（1）O（1）尾插add（Object obj）:直接数组中对应size位置的元素赋为obj

注：虽然此时的尾插操作可能会触发扩容操作（需要遍历数组操作，复杂度为O（N）），但由于我们可以在一开始的时候就设定好数组的容量，所以其触发的概率较低，所以还是认为其时间复杂度为O（1）

（2）O（N）指定位置插入add（int index，Object obj）

步骤：

（i）先将index处开始的元素都往后移动一个位

注：此处要结合图像思考其要从前往后开始搬运一个位还是从后往前搬运一个位

根据画图来看若从前往后移动位置会导致部分数据的丢失，所以需要从后往前开始移动位置

并且i是否要等于index也需要结合画图代入特殊值来进行判断来写出式子

例如for（int i=size-1；i<=index;i--)

data[i+1]=data[i];

（ii）在将index处位置换为obj

3.删除：删除完元素后注意要对size进行自减

（1）O（N）按照下标删除remove（int index）：将index后的元素往前一个位置

注：此时与add的指定位置添加元素相同，都需要结合画图去考虑要从前往后遍历去进行往前移还是从后往前遍历去往前一个位置

此时若从后往前遍历移位可以看出后面的值会覆盖前面的值导致前面元素的消失

（2）O（N）按照元素删除remove（Object obj）

（i）先利用一个for循环找到第一个obj出现的下标位置，对循环结束后的数进行判断若其size则说明顺序表中没有该元素直接返回false即可

（ii）若能找到该元素下标将该下标作为按照下标删除的方法的参数进行删除

（iii）删除成功返回true失败返回false

补充：区分两种删除失败：按照下标删除在输入下标不合理时会抛出异常和按照元素删除在元素不存在返回false

第一种：属于是程序编写时程序员没有考虑到位，理论上是不应该不存在这个错误的，属于编程错误，即代码bug

第二种：由于其要等到运行时才能知道其是否包含该元素，所以元素不存在的情况合情合理，并不属于代码bug

4.O（1）get/set：利用利用[]对应得到和赋值即可

5.clear：直接将size设为0

注：此时进行的时逻辑上的删除，而非物理上的，将数组的元素所占的空间设为无效，令下次创建的新元素直接覆盖掉旧元素，而不是能直接将原数据抹掉

类似的情况：电脑上的硬盘空间，对电脑上的文件直接进行删除，只是将其对应占用的空间标记为无效，下次别的文件可以继续使用该空间，但被删除的文件通过特殊手段还是可以获取的

6.IndexOf（Object obj）：利用for循环从0开始往后遍历+if语句，找不到返回-1

7.lastIndexOf（Object obj）：利用for循环从size-1开始往前开始遍历比较，找不到返回-1

8.contains（Object obj）：返回IndexOf（Object obj）！=-1，不为-1说明存在为true

9.sublist（int fromIndex，int toIndex）：

补充面对区间的合法性判断入手点（以本方法为例）

（1）区间性质：先判断该区间为左闭右开还是左闭右闭等

（2）左右区间本身：利用（1）的判断对左右区间本身的要满足的性质

例如：fromIndex>=0&&toIndex<=size（由（1）的性质可知此处可取等）

（3）左右区间的大小关系：左区间要小于右区间+根据实际情况讨论是否能相等

注：此处是否能等于要根据实际情况来进行讨论，在这个方法中，左区间等于右区间等到的是一个空区间，对应截取的是一个空的顺序表是合理的，要根据具体情况具体分析

10.查看顺序表中的内容

（1）利用调试器进行查看：在进行完操作的后一行代码设置断点，在后台进行查看即会显示顺序表中的内容

（2）重写toString方法

注：字符串是不可变对象，要对字符串进行拼接需要使用StringBuilder类来对字符串进行拼接

（i）利用StringBuilder创建的对象的append方法对顺序表中元素进行添加，中间用逗号隔开（注意最后一个元素要用if判断，其不需要添加，）

（ii）最后使用该对象中所含有的toString方法将其转换为字符串进行返回

注：StringBuilder自带toString方法可以与String类进行转换

11.注意：对这些功能的实现也要有对应的测试方法

每一个功能对应一个测试方法进行测试，这种思路称为单元测试

七  ArrayList的总结

1.特点：

（1）基于数组实现，创建顺序表时，会先创建出一大块内存空间（导致资源浪费），其元素在内存中连续占用存储空间

（2）用于得到和设置中间元素及直接插入元素高效

2.局限性：

（1）空间利用率低（数组容量固定，有部分创建了但是没用上）

（2）用于插入和删除中间元素需要进行搬运，效率低

注：为了解决上述问题，需要引用新的数据结构，也就是后面所讲的链表

3.效率：

判断标准：时间复杂度

（1）效率高：得到和设置中间元素及直接插入元素

（2）效率低：从任意位置插入和删除元素