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或者其父类 泛型下限