1、集合的体系特点

（1）集合类体系结构：

（2）先掌握Collection集合体系的使用：

（3）Collection集合特点

• List系列集合：添加的元素是有序、可重复、有索引。

---- ArrayList、LinekdList ：有序、可重复、有索引。

• Set系列集合：添加的元素是无序、不重复、无索引。

----HashSet: 无序、不重复、无索引；

----LinkedHashSet: 有序、不重复、无索引。

----TreeSet：按照大小默认升序排序、不重复、无索引。

（4）泛型：集合都是泛型的形式，可以在编译阶段约束集合只能操作某种数据类型

注意：集合和泛型都只能支持引用数据类型，不支持基本数据类型，所以集合中存储的元素都认为是对象。

如果集合中要存储基本类型的数据怎么办？

2、Collection集合常用API

Collection集合 ： Collection是单列集合的祖宗接口，它的功能是全部单列集合都可以继承使用的

Collection API如下:

3、Collection集合的遍历方式

（1）迭代器

迭代器遍历概述

• 遍历就是一个一个的把容器中的元素访问一遍。
• 迭代器在Java中的代表是Iterator，迭代器是集合的专用的遍历方式。

Collection集合获取迭代器

Iterator中的常用方法

迭代器执行流程

注意：迭代器如果取元素越界会出现什么问题： 出现NoSuchElementException异常。

（2）foreach/增强for循环

增强for循环：既可以遍历集合也可以遍历数组。

注意：修改第三方变量的值不会影响到集合中的元素

（3）lambda表达式

Collection结合Lambda遍历的API

4、Collection集合存储自定义类型的对象

案例： 影片信息在程序中的表示

需求：某影院系统需要在后台存储上述三部电影，然后依次展示出来。

分析：

① 定义一个电影类，定义一个集合存储电影对象。

② 创建3个电影对象，封装相关数据，把3个对象存入到集合中去。

③ 遍历集合中的3个对象，输出相关信息

代码：

存储结构：

5、常见数据结构

（1）数据结构概述、栈、队列

数据结构概述

• 数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。
• 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

常见的数据结构 ： 栈，队列 ，数组 ， 链表 ， 二叉树 ， 二叉查找树 ，平衡二叉树 ， 红黑树 ， …

栈数据结构的执行特点：后进先出，先进后出。（栈顶开口，栈底封闭）

常见数据结构之队列： 先进先出，后进后出。（前后端都开口）

（2）数组

特点：

• 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同。（元素在内存中是连续存储的）

• 删除效率低：要将原始数据删除，同时后面每个数据前移。

• 添加效率极低：添加位置后的每个数据后移，再添加元素。

（3）链表

特点：

• 链表中的元素是在内存中不连续存储的。每个元素节点包含数据值和下一个元素的地址。

链表查询慢。无论查询哪个数据都要从头开始找

链表增删相对快。

（4）二叉树、 二叉查找树

二叉树概述

特点：

只能有一个根节点，每个节点最多支持2个直接子节点。

节点的度： 节点拥有的子树的个数，二叉树的度不大于 2 叶子节点 ，度为0的节点，也称之为终端结点。

高度：叶子结点的高度为1，叶子结点的父节点高度为2， 以此类推，根节点的高度最高。

层：根节点在第一层，以此类推

兄弟节点 ：拥有共同父节点的节点互称为兄弟节点

二叉查找树又称二叉排序树或者二叉搜索树。

特点：

• 每一个节点上最多有两个子节点
• 左子树上所有节点的值都小于根节点的值
• 右子树上所有节点的值都大于根节点的值

（5）平衡二叉树

平衡二叉树是在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。

要求：任意节点的左右两个子树的高度差不超过1，任意节点的左右两个子树都是一颗平衡二叉树

平衡二叉树在添加元素后可能导致不平衡 ： 基本策略是进行左旋，或者右旋保证平衡。

（6）红黑树

红黑树概述

红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。

1972年出现，当时被称之为平衡二叉B树。1978年被修改为如今的"红黑树"。

每一个节点可以是红或者黑；红黑树不是通过高度平衡的，它的平衡是通过“红黑规则”进行实现的。

• 红黑规则

每一个节点或是红色的，或者是黑色的，根节点必须是黑色。

如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况 )。

对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每 个叶节点(Nil)是黑色的；

• 红黑树小结

红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的

• 各种数据结构的特点和作用是什么样的?

队列：先进先出，后进后出。

栈：后进先出，先进后出。

数组：内存连续区域，查询快，增删慢。

链表：元素是游离的，查询慢，首尾操作极快。

二叉树：永远只有一个根节点, 每个结点不超过2个子节点的树。

查找二叉树：小的左边，大的右边，但是可能树很高，查询性能变差。

平衡查找二叉树：让树的高度差不大于1，增删改查都提高了。

红黑树（就是基于红黑规则实现了自平衡的排序二叉树）

6、List系列集合

（1）List集合特点、特有API

List系列集合特点

• ArrayList、LinekdList ：有序，可重复，有索引。
• 有序：存储和取出的元素顺序一致
• 有索引：可以通过索引操作元素
• 可重复：存储的元素可以重复

List集合特有方法

• List集合因为支持索引，所以多了很多索引操作的独特api，其他Collection的功能List也都继承了。

（2）List集合的遍历方式

① 迭代器

② 增强for循环

③ Lambda表达式

④ for循环（因为List集合存在索引）

（3）ArrayList集合的底层原理

• ArrayList底层是基于数组实现的：根据索引定位元素快，增删需要做元素的移位操作。
• 第一次创建集合并添加第一个元素的时候，在底层创建一个默认长度为10的数组。

（4）LinkedList集合的底层原理

LinkedList的特点

• 底层数据结构是双链表，查询慢，首尾操作的速度是极快的，所以多了很多首尾操作的特有API。

LinkedList集合的特有功能

7、补充知识：泛型深入

（1）泛型概述

• 泛型：是JDK5中引入的特性，可以在编译阶段约束操作的数据类型，并进行检查。
• 泛型的格式：<数据类型>; 注意：泛型只能支持引用数据类型。
• 集合体系的全部接口和实现类都是支持泛型的使用的。

泛型的好处：

• 统一数据类型。
• 把运行时期的问题提前到了编译期间，避免了强制类型转换可能出现的异常，因为编译阶段类型就能确定下来。

泛型可以在很多地方进行定义:

• 类后面： 泛型类
• 方法声明上 ：泛型方法
• 接口后面 ：泛型接口

（2）自定义泛型类

泛型类的概述

• 定义类时同时定义了泛型的类就是泛型类。
• 泛型类的格式：修饰符 class 类名<泛型变量>{ }

• 此处泛型变量T可以随便写为任意标识，常见的如E、T、K、V等。
• 作用：编译阶段可以指定数据类型，类似于集合的作用。
• 泛型类的原理：把出现泛型变量的地方全部替换成传输的真实数据类型。

（3）自定义泛型方法

泛型方法的概述

• 定义方法时同时定义了泛型的方法就是泛型方法。
• 泛型方法的格式：修饰符 <泛型变量> 方法返回值 方法名称(形参列表){}

• 作用：方法中可以使用泛型接收一切实际类型的参数，方法更具备通用性。
• 泛型方法的原理： 把出现泛型变量的地方全部替换成传输的真实数据类型

（4）自定义泛型接口

泛型接口的概述

• 使用了泛型定义的接口就是泛型接口。
• 泛型接口的格式：修饰符 interface 接口名称<泛型变量>{}

• 作用：泛型接口可以让实现类选择当前功能需要操作的数据类型
• 泛型接口的原理：实现类可以在实现接口的时候传入自己操作的数据类型，这样重写的方法都将是针对于该类型的操作。

（5）泛型通配符、上下限

通配符:?

• ? 可以在“使用泛型”的时候代表一切类型。
• E T K V 是在定义泛型的时候使用的。

注意：虽然BMW和BENZ都继承了Car但是ArrayList和ArrayList与ArrayList没有关系的！!

泛型的上下限：

• ? extends Car: ?必须是Car或者其子类 泛型上限
• ? super Car ： ?必须是Car或者其父类 泛型下限