集合（Collection、数据结构、List、泛型深入）
1.集合的概述
集合和数组都是容器。
数组的特点
数组定义完成并启动后，类型确定、长度固定。
适合元素的个数和类型确定的业务场景，不适合做需要增删数据操作。
集合的特点
集合的大小不固定，启动后可以动态变化，类型也可以选择不固定。
集合非常适合做个数不确定的元素增删操作。
注意：集合中只能存储引用类型数据，如果要存储基本类型数据可以选用包装类。
集合中存储的是元素的什么信息?
集合中存储的是元素对象的地址信息，如果想要查看内容信息，需要重写元素对象的toString方法。
2.Collection集合的体系特点
集合类体系结构如下图所示。
①Collection单列集合，每个元素（数据）只包含一个值。
②Map双列集合，每个元素包含两个值（键值对）。
Collection集合体系结构如下图所示。
Collection集合特点
List系列集合：添加的元素是有序、可重复、有索引。
ArrayList、LinekdList：有序、可重复、有索引。
Set系列集合：添加的元素是无序、不重复、无索引。
HashSet: 无序、不重复、无索引。
LinkedHashSet:有序、不重复、无索引。
TreeSet：按照大小默认升序排序、不重复、无索引。
示例代码如下：
publicstaticvoidmain(String[] args) { // list:有序 可重复 有索引Collectionlist=newArrayList(); list.add("Java"); list.add("MyBatis"); list.add("张三"); list.add("张三"); list.add("李四"); System.out.println(list); // [Java, MyBatis, 张三, 张三, 李四]// set:无序 不可重复 无索引Collectionlist2=newHashSet(); list2.add("Java"); list2.add("MyBatis"); list2.add("张三"); list.add("张三"); list.add("李四"); System.out.println(list2); // [Java, 张三, MyBatis] }
集合对于泛型的支持
集合都是支持泛型的，可以在编译阶段约束集合只能操作某种数据类型。
注意：集合和泛型都只能支持引用数据类型，不支持基本数据类型，所以集合中存储的元素都认为是对象。
3.Collection集合的常用API
Collection集合
Collection是单列集合的祖宗接口，它的功能是全部单列集合都可以继承使用的。
Collection API
方法名 |
说明 |
public boolean add(E e) |
把给定的对象添加到当前集合中 |
public void clear() |
清空集合中所有的元素 |
public boolean remove(E e) |
把给定的对象在当前集合中删除 |
public boolean contains(Object obj) |
判断当前集合中是否包含给定的对象 |
public boolean isEmpty() |
判断当前集合是否为空 |
public int size() |
返回集合中元素的个数 |
public Object[] toArray() |
把集合中的元素，存储到数组中 |
boolean addAll(Collection<? extends E> c); |
把参数集合中的元素拷贝到当前集合中， 且被拷贝的集合中元素不变 |
示例代码如下：
publicstaticvoidmain(String[] args) { Collection<String>list=newArrayList<>(); // 1. public boolean add(E e) 把给定的对象添加到当前集合中list.add("Java"); list.add("张三"); list.add("李四"); System.out.println(list); // [Java, 张三, 李四]// 2. public void clear() 清空集合中所有的元素// list.clear();// System.out.println(list); // []// 3. public boolean remove(E e) 把给定的对象在当前集合中删除list.add("Java"); list.remove("Java"); System.out.println(list); // [张三, 李四, Java] 默认删除集合中的第一个对应元素// 4. public boolean contains(Object obj) 判断当前集合中是否包含给定的对象System.out.println(list.contains("Java")); // trueSystem.out.println(list.contains("MyBatis")); // false// 5. public boolean isEmpty() 判断当前集合是否为空System.out.println(list.isEmpty()); // false// 6. public int size() 返回集合中元素的个数System.out.println(list.size()); // 3// 7. public Object[] toArray() 把集合中的元素，存储到数组中Object[] arr=list.toArray(); System.out.println("数组："+Arrays.toString(arr)); // 数组：[张三, 李四, Java]System.out.println("------扩展------"); Collection<String>l1=newArrayList<>(); l1.add("Java"); l1.add("HTML"); System.out.println(l1); // [Java, HTML]Collection<String>l2=newArrayList<>(); l2.add("张三"); l2.add("李四"); System.out.println(l2); // [张三, 李四]l1.addAll(l2); // 把l2中的元素全部拷贝到l1中去，l2中元素不变System.out.println(l1); // [Java, HTML, 张三, 李四]System.out.println(l2); // [张三, 李四] }
4.Collection集合的遍历方式
4.1方式一：迭代器
迭代器遍历概述
遍历就是一个一个的把容器中的元素访问一遍。
迭代器在Java中的代表是Iterator，迭代器是集合的专用遍历方式。
Collection集合获取迭代器
方法名 |
说明 |
Iterator<E> iterator() |
返回集合中的迭代器对象，该迭代器对象默认指向当前集合的0索引 |
Iterator中的常用方法
方法名 |
说明 |
boolean hasNext() |
询问当前位置是否有元素存在，存在返回true ,不存在返回false |
E next() |
获取当前位置的元素，并同时将迭代器对象移向下一个位置， 注意防止取出越界。 |
示例代码如下：
publicstaticvoidmain(String[] args) { Collection<String>list=newArrayList<>(); list.add("张三"); list.add("李四"); list.add("王五"); System.out.println(list); // [张三, 李四, 王五]// 得到当前集合的迭代器对象Iterator<String>it=list.iterator(); Stringele=it.next(); // 默认指向0索引，每访问一次，指向位置+1// System.out.println(ele); // 张三// System.out.println(it.next()); // 李四// System.out.println(it.next()); // 王五// System.out.println(it.next()); // 报错NoSuchElementException，此时索引在第3位，访问越界，没有此元素异常while (it.hasNext()) { // 采用while循环，循环条件是询问当前位置有元素存在，使用hasNext()方法，存在返回true ,不存在返回falseSystem.out.print(it.next() +"\t"); // 张三 李四 王五 } }
4.2方式二：foreach/增强for循环
增强for循环遍历概述
既可以遍历集合也可以遍历数组。
其内部原理是一个Iterator迭代器，遍历集合相当于是迭代器的简化写法。
实现Iterator接口的类才可以使用迭代器和增强for，collection接口已经实现了Iterator接口。
增强for循环的格式如下图所示。
示例代码如下：
publicstaticvoidmain(String[] args) { Collection<String>list=newArrayList<>(); list.add("张三"); list.add("李四"); list.add("王五"); System.out.println(list); // [张三, 李四, 王五]// foreach遍历集合for (Stringele : list) { // 自动提取集合/数组中的每一个元素System.out.print(ele+"\t"); // 张三 李四 王五 } System.out.println(); // foreach遍历数组double[] scores= {80, 99.3, 67, 5, 77.8}; for (doublescore : scores) { System.out.print(score+"\t"); // 80.0 99.3 67.0 5.0 77.8 } }
注：修改foreach循环中的变量的值对原集合/数组的值没有任何影响。
4.3方式三：lambda表达式
lambda表达式遍历集合概述
得益于JDK 8开始的新技术Lambda表达式，提供了一种更简单、更直接的遍历集合的方式。
Collection结合Lambda遍历的API
方法名 |
说明 |
default void forEach(Consumer<? super T> action): |
结合lambda遍历集合 |
示例代码如下：
publicstaticvoidmain(String[] args) { Collection<String>list=newArrayList<>(); list.add("张三"); list.add("李四"); list.add("王五"); System.out.println(list); // [张三, 李四, 王五]// list.forEach(new Consumer<String>() {// @Override// public void accept(String s) {// System.out.print(s + "\t"); // 张三 李四 王五// }// });list.forEach(s->System.out.print(s+"\t")); // 张三 李四 王五 }
5.常见数据结构
5.1数据结构概述、栈、队列
数据结构概述
数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树、…
栈数据结构的执行特点：后进先出，先进后出
数据进入栈模型的过程称为：压/进栈
数据离开栈模型的过程称为：弹/出栈
栈数据结构的执行特点示意如下图所示。
队列数据结构的执行特点：先进先出，后进后出
数据从后端进入队列模型的过程称为：入队列
数据从前端离开队列模型的过程称为：出队列
队列数据结构的执行特点示意如下图所示。
5.2数组
数组是一种查询快，增删慢的模型
查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同。（元素在内存中是连续存储的）
删除效率低：要将原始数据删除，同时后面每个数据前移。
添加效率极低：添加位置后的每个数据后移，再添加元素，同时需要保证索引没有出现大于等于数组长度越位。
5.3链表
链表的特点：链表中的元素是在内存中不连续存储的，每个元素节点包含数据值和下一个元素的地址。
链表查询相对慢(对比数组），无论查询哪个数据都要从头开始找
链表增删相对快(对比数组）。
链表的特点如下图所示。
如下图所示，链表种类分为单链表与双链表，双链表支持从前往后搜索，也支持从后往前搜索。
5.4二叉树、二叉查找树
二叉树的特点
只能有一个根节点，每个节点最多支持2个直接子节点。
节点的度：节点拥有的子树的个数，二叉树的度不大于叶子节点度为0的节点，也称之为终端结点。
高度：叶子结点的高度为1，叶子结点的父节点高度为2，以此类推，根节点的高度最高。
层：根节点在第一层，以此类推
兄弟节点：拥有共同父节点的节点互称为兄弟节点。
二叉查找树又称二叉排序树或者二叉搜索树，其结构如下图所示。
特点：
每一个节点上最多有两个子节点。
左子树上所有节点的值都小于根节点的值。
右子树上所有节点的值都大于根节点的值。
目的：提高检索数据的性能。
5.5平衡二叉树
平衡二叉树是在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。
平衡二叉树的要求
任意节点的左右两个子树的高度差不超过1，任意节点的左右两个子树都是一颗平衡二叉树。
平衡二叉树在添加元素后可能导致不平衡，基本策略是进行左旋，或者右旋保证平衡。
5.6红黑树
红黑树概述
每一个节点可以是红或者黑，红黑树不是通过高度平衡的，它的平衡是通过“红黑规则”进行实现的。
红黑规则
每一个节点或是红色的，或者是黑色的，根节点必须是黑色。
如果一个节点没有子节点或父节点，则该节点相应的指针属性为Nil，这些Nil视为叶节点，叶节点是黑色的。
如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
6.List系列集合
6.1List集合特点、特有API
List系列集合特点
ArrayList、LinekdList：有序，可重复，有索引。
有序：存储和取出的元素顺序一致
有索引：可以通过索引操作元素
可重复：存储的元素可以重复
List集合特有方法
List集合因为支持索引，所以多了很多索引操作的独特API，其他Collection的功能List也都继承了。
List集合特有方法
方法名 |
说明 |
void add(int index,E element) |
在此集合中的指定位置插入指定的元素 |
E remove(int index) |
删除指定索引处的元素，返回被删除的元素 |
E set(int index,E element) |
修改指定索引处的元素，返回被修改的元素 |
E get(int index) |
返回指定索引处的元素 |
示例代码如下：
publicstaticvoidmain(String[] args) { List<String>list=newArrayList<>(); list.add("Java"); list.add("MySQL"); list.add("HTML"); System.out.println(list); // [Java, MySQL, HTML]// void add(int index,E element) 在此集合中的指定位置插入指定的元素list.add(1, "MyBatis"); // [Java, MyBatis, MySQL, HTML]System.out.println(list); // E remove(int index) 删除指定索引处的元素，返回被删除的元素StringremoveEle=list.remove(2); System.out.println(removeEle); // MySQLSystem.out.println(list); // [Java, MyBatis, HTML]// E set(int index,E element) 修改指定索引处的元素，返回被修改的元素StringsetEle=list.set(1, "Python"); System.out.println(setEle); // MyBatisSystem.out.println(list); // [Java, Python, HTML]// E get(int index) 返回指定索引处的元素StringgetEle=list.get(0); System.out.println(getEle); // Java }
List集合的遍历方式小结
①迭代器②增强for循环③Lambda表达式④for循环（因为List集合存在索引）
ArrayList集合的底层原理
ArrayList底层是基于数组实现的：根据索引定位元素快，增删需要做元素的移位操作。
第一次创建集合并添加第一个元素的时候，在底层创建一个默认长度为10的数组。
6.2LinkedList集合特点、特有API
LinkedList的特点
底层数据结构是双链表，查询慢，首尾操作的速度是极快的，所以多了很多首尾操作的特有API。
LinkedList集合特有方法
方法名 |
说明 |
public void addFirst (E e) |
在该列表开头插入指定的元素 |
public void push(E e) |
同public void addFirst (E e)（push更专业） |
public void addLast (E e) |
将指定的元素追加到此列表的末尾 |
public E getFirst () |
返回此列表中的第一个元素 |
public E getLast () |
返回此列表中的最后一个元素 |
public E removeFirst () |
从此列表中删除并返回第一个元素 |
public E pop() |
同public E removeFirst ()（pop更专业） |
public E removeLast () |
从此列表中删除并返回最后一个元素 |
示例代码如下：
publicstaticvoidmain(String[] args) { // LinkedList可以完成队列结构、栈结构（双链表）// 栈LinkedList<String>stack=newLinkedList<>(); // 压栈/入栈// stack.addFirst("第1颗子弹");stack.push("第1颗子弹"); stack.push("第2颗子弹"); stack.push("第3颗子弹"); stack.push("第4颗子弹"); System.out.println(stack); // [第4颗子弹, 第3颗子弹, 第2颗子弹, 第1颗子弹]// 弹栈/出栈// System.out.println(stack.removeFirst()); // 第4颗子弹System.out.println(stack.pop()); // 第4颗子弹System.out.println(stack.pop()); // 第3颗子弹System.out.println(stack.pop()); // 第2颗子弹System.out.println(stack.pop()); // 第1颗子弹// 队列LinkedList<String>queue=newLinkedList<>(); // 入队queue.addLast("1号"); queue.addLast("2号"); queue.addLast("3号"); queue.addLast("4号"); System.out.println(queue); // [1号, 2号, 3号, 4号]// 出队System.out.println(queue.removeFirst()); // 1号System.out.println(queue.removeFirst()); // 2号System.out.println(queue.removeFirst()); // 3号System.out.println(queue.removeFirst()); // 4号 }
7.补充知识：集合的并发修改异常问题
问题引出
当我们从集合中找出某个元素并删除的时候可能出现一种并发修改异常问题。
哪些遍历存在问题？
迭代器遍历集合且直接用集合删除元素的时候可能出现。
增强for循环遍历集合且直接用集合删除元素的时候可能出现。
哪种遍历且删除元素不出问题？
迭代器遍历集合但是用迭代器自己的删除方法可以解决。
使用for循环遍历并删除元素后使查询索引i自减1，或者从后向前遍历并删除指定元素，就不会出现这个问题。
示例代码如下：
publicstaticvoidmain(String[] args) { // 1.准备数据List<String>list=newArrayList<>(); list.add("张三"); list.add("Java"); list.add("Java"); list.add("李四"); list.add("李四"); list.add("王五"); System.out.println(list); // [张三, Java, Java, 李四, 李四, 王五]// 需求：删除全部的Java信息// a.迭代器遍历删除/* Iterator<String> it = list.iterator();while (it.hasNext()) {String ele = it.next();if (ele.equals("Java")) {// list.remove("Java"); // 报错，并发异常，删除某个元素后迭代器查询索引会后移，不会遍历所有元素it.remove(); // 解决办法：用迭代器自己的删除方法,删除当前元素，并且迭代器查询索引不会后移，会遍历所有元素}}System.out.println(list); // [张三, 李四, 李四, 王五]*/// b.增强for循环遍历删除/* for (String ele : list) {if (ele.equals("Java")) {list.remove("Java"); // 报错，并发异常，删除某个元素后增强for循环查询索引会后移，不会遍历所有元素}}System.out.println(list);*/// c.lambda表达式遍历删除/* list.forEach(s -> {if (s.equals("Java")) {list.remove("Java"); // 报错，并发异常，删除某个元素后forEach的lambda表达式查询索引会后移，不会遍历所有元素}});System.out.println(list);*/// d.for循环遍历删除for (inti=0; i<list.size(); i++) { if (list.get(i).equals("Java")) { list.remove("Java"); // 不会报错，但是删除某个元素后for循环的查询索引i会后移，不会遍历所有元素，会漏删// 解决办法①：因此每次删除完元素后，使查询索引i自减1，使其刚好遍历所有元素i--; } } System.out.println(list); // [张三, 李四, 李四, 王五]// 解决办法②：从后向前遍历并删除指定元素for (inti=list.size() -1; i>=0; i--) { if (list.get(i).equals("Java")) { list.remove("Java"); } } System.out.println(list); // [张三, 李四, 李四, 王五] }
8.补充知识：泛型深入
8.1泛型概述
泛型：是JDK5中引入的特性，可以在编译阶段约束操作的数据类型，并进行检查。
泛型的格式：<数据类型>;注意：泛型只能支持引用数据类型。
集合体系的全部接口和实现类都是支持泛型的使用的。
泛型的好处
统一数据类型。
把运行时期的问题提前到了编译期间，避免了强制类型转换可能出现的异常，因为编译阶段类型就能确定下来。
泛型可以在很多地方进行定义
类后面->泛型类 方法申明上->泛型方法 接口后面->泛型接口
8.2自定义泛型类
泛型类的概述
定义类时同时定义了泛型的类就是泛型类。
泛型类的格式：修饰符 class 类名<泛型变量>{ }
此处泛型变量T可以随便写为任意标识，常见的如E、T、K、V等。
作用：编译阶段可以指定数据类型，类似于集合的作用。
泛型类的原理
把出现泛型变量的地方全部替换成传输的真实数据类型。
8.3自定义泛型方法
泛型方法的概述
定义方法时同时定义了泛型的方法就是泛型方法。
泛型方法的格式：修饰符 <泛型变量> 方法返回值 方法名称(形参列表){ }
作用：方法中可以使用泛型接收一切实际类型的参数，方法更具备通用性。
泛型方法的原理
把出现泛型变量的地方全部替换成传输的真实数据类型。
示例代码如下：
publicclassGenericDemo { publicstaticvoidmain(String[] args) { String[] names= {"张三", "李四", "王五"}; printArray(names); Integer[] ages= {18, 22, 30}; printArray(ages); } publicstatic<T>voidprintArray(T[] arr) { if (arr!=null) { StringBuildersb=newStringBuilder("["); for (inti=0; i<arr.length; i++) { sb.append(arr[i]).append(i==arr.length-1?"" : ","); } sb.append("]"); System.out.println(sb); } else { System.out.println(arr); } } }
8.4自定义泛型接口
泛型接口的概述
使用了泛型定义的接口就是泛型接口。
泛型接口的格式：修饰符 interface 接口名称<泛型变量>{}
作用：泛型接口可以让实现类选择当前功能需要操作的数据类型
泛型接口的原理
泛型接口可以约束实现类，实现类在实现接口的时候传入自己操作的数据类型，这样重写的方法都将是针对于该类型的操作。
8.5泛型通配符、上下限
通配符:?
? 可以在“使用泛型”的时候代表一切类型。
E T K V 是在定义泛型的时候使用的。
示例代码如下：
publicclassGenericDemo { publicstaticvoidmain(String[] args) { ArrayList<BENZ>benzs=newArrayList<>(); benzs.add(newBENZ()); benzs.add(newBENZ()); benzs.add(newBENZ()); go(benzs); ArrayList<BMW>bmw=newArrayList<>(); bmw.add(newBMW()); bmw.add(newBMW()); bmw.add(newBMW()); go(bmw); ArrayList<Dog>dog=newArrayList<>(); dog.add(newDog()); dog.add(newDog()); dog.add(newDog()); // go(dog); } /*** 所有车都可以参加比赛** @param cars*/publicstaticvoidgo(ArrayList<?extendsCar>cars) { } } classBENZextendsCar { } classBMWextendsCar { } classDog { } // 父类classCar { }
注意：虽然BMW和BENZ都继承了Car但是ArrayList<BMW>和ArrayList<BENZ>与ArrayList<Car>没有关系的！!
泛型的上下限
? extends Car：?必须是Car或者其子类泛型上限
? super Car：?必须是Car或者其父类泛型下限
