百木园2.1数组和集合的区别(理解)
-
相同点
都是容器,可以存储多个数据
-
不同点
-
数组的长度是不可变的,集合的长度是可变的
-
数组可以存基本数据类型和引用数据类型
集合只能存引用数据类型,如果要存基本数据类型,需要存对应的包装类
-
2.2集合类体系结构(理解)
2.3Collection 集合概述和使用(应用)
-
Collection集合概述
-
是单例集合的顶层接口,它表示一组对象,这些对象也称为Collection的元素
-
JDK 不提供此接口的任何直接实现.它提供更具体的子接口(如Set和List)实现
-
-
创建Collection集合的对象
-
多态的方式
-
具体的实现类ArrayList
-
-
Collection集合常用方法
方法名 说明 boolean add(E e) 添加元素 boolean remove(Object o) 从集合中移除指定的元素 boolean removeIf(Object o) 根据条件进行移除 void clear() 清空集合中的元素 boolean contains(Object o) 判断集合中是否存在指定的元素 boolean isEmpty() 判断集合是否为空 int size() 集合的长度，也就是集合中元素的个数
2.4迭代器(应用)
-
迭代器介绍
-
迭代器,集合的专用遍历方式
-
Iterator<E> iterator(): 返回此集合中元素的迭代器,通过集合对象的iterator()方法得到,迭代器对象一旦被创建，默认指向集合的0索引位置.
-
-
Iterator中的常用方法
boolean hasNext(): 判断当前位置是否有元素可以被取出 E next(): 获取当前位置的元素,将迭代器对象移向下一个索引位置
-
示例代码
public class MyCollectionDemo3 {
public static void main(String[] args) {
Collection<String> list = new ArrayList<>();
list.add(\"a\");
list.add(\"b\");
list.add(\"c\");
list.add(\"d\");
list.add(\"e\");
//1,获得迭代器的对象
//迭代器对象一旦被创建，默认指向集合的0索引位置
Iterator<String> it = list.iterator();
//2.利用迭代器里面的方法进行遍历
/*
boolean hasNext() 判断当前是否还有元素
E next() 取出当前元素，并指向下一个元素
*/
while(it.hasNext()){
System.out.println(it.next());
}
}
} -
迭代器原理
-
迭代器中删除的方法
void remove(): 删除迭代器对象当前指向的元素
public class IteratorDemo2 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add(\"a\");
list.add(\"b\");
list.add(\"b\");
list.add(\"c\");
list.add(\"d\");
Iterator<String> it = list.iterator();
while(it.hasNext()){
String s = it.next();
if(\"b\".equals(s)){
//指向谁,那么此时就删除谁.
it.remove();
}
}
System.out.println(list);
}
}
2.5增强for循环(应用)
-
介绍
-
它是JDK5之后出现的,其内部原理是一个Iterator迭代器
-
实现Iterable接口的类才可以使用迭代器和增强for
-
简化数组和Collection集合的遍历
-
-
格式
for(集合/数组中元素的数据类型 变量名 : 集合/数组名) {
// 已经将当前遍历到的元素封装到变量中了,直接使用变量即可
}
-
代码
public class MyCollectonDemo1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add(\"a\");
list.add(\"b\");
list.add(\"c\");
list.add(\"d\");
list.add(\"e\");
list.add(\"f\");
//1,数据类型一定是集合或者数组中元素的类型
//2,str仅仅是一个变量名而已,在循环的过程中,依次表示集合或者数组中的每一个元素
//3,list就是要遍历的集合或者数组
for(String str : list){
System.out.println(str);
}
}
} -
注意事项
public class MyCollectionDemo7 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add(\"a\");
list.add(\"b\");
list.add(\"c\");
list.add(\"d\");
//str是第三方变量，对第三方变量的修改 不会影响集合原有值
for(String str : list){
str = \"q\";
System.out.println(str);
}
//集合或数组名.for 敲回车，快速生成增强for格式
for (String s : list) {
System.out.println(s);
}
//System.out.println(list);
}
} -
三种遍历集合方式总结
-
如果需要操作索引，使用普通for循环
-
如果在遍历的过程中需要删除元素，请使用迭代器
-
如果仅仅只是遍历，则使用增强for
-
2.6Collection练习(应用)
public class MyCollectionDemo8 {
public static void main(String[] args) {
ArrayList<Student> list = new ArrayList<>();
list.add(new Student(\"小皮同学\",23));
list.add(new Student(\"小路同学\",31));
list.add(new Student(\"小贾同学\",33));
//迭代器的方式进行遍历
Iterator<Student> it = list.iterator();
while(it.hasNext()){
Student s = it.next();
System.out.println(s);
}
System.out.println(\"-------------------------\");
//增强for
for (Student student : list) {
System.out.println(student);
}
System.out.println(\"--------------------------\");
//普通for循环
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
3.List集合
3.1List集合的概述和特点(记忆)
-
List集合的概述
-
有序集合,这里的有序指的是存取顺序
-
用户可以精确控制列表中每个元素的插入位置,用户可以通过整数索引访问元素,并搜索列表中的元素
-
与Set集合不同,列表通常允许重复的元素
-
-
List集合的特点
-
存取有序
-
可以重复
-
有索引
-
-
示例代码
public class MyListDemo1 {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add(\"aaa\");
list.add(\"bbb\");
list.add(\"ccc\");
Iterator<String> it = list.iterator();
while(it.hasNext()){
String s = it.next();
System.out.println(s);
}
System.out.println(\"---------------------\");
for (String s : list) {
System.out.println(s);
}
}
}
3.2List集合的特有方法(应用)
-
方法介绍
方法名 描述 void add(int index,E element) 在此集合中的指定位置插入指定的元素 E remove(int index) 删除指定索引处的元素，返回被删除的元素 E set(int index,E element) 修改指定索引处的元素，返回被修改的元素 E get(int index) 返回指定索引处的元素 -
示例代码
public class MyListDemo2 {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add(\"aaa\");
list.add(\"bbb\");
list.add(\"ccc\");
method1(list);
method2(list);
method3(list);
method4(list);
}
private static void method4(List<String> list) {
//E get(int index) 返回指定索引处的元素
String s = list.get(0);
System.out.println(s);
}
private static void method3(List<String> list) {
//E set(int index,E element) 修改指定索引处的元素，返回被修改的元素
//被替换的那个元素,在集合中就不存在了.
String result = list.set(0, \"qqq\");
System.out.println(result);
System.out.println(list);
}
private static void method2(List<String> list) {
//E remove(int index) 删除指定索引处的元素，返回被删除的元素
//在List集合中有两个删除的方法
//第一个 删除指定的元素,返回值表示当前元素是否删除成功
//第二个 删除指定索引的元素,返回值表示实际删除的元素
String s = list.remove(0);
System.out.println(s);
System.out.println(list);
}
private static void method1(List<String> list) {
//void add(int index,E element) 在此集合中的指定位置插入指定的元素
//原来位置上的元素往后挪一个索引.
list.add(0,\"qqq\");
System.out.println(list);
}
}
4.数据结构
4.1数据结构之栈和队列(记忆)
-
栈结构
先进后出
-
队列结构
先进先出
4.2数据结构之数组和链表(记忆)
-
数组结构
查询快、增删慢 arraylist
-
链表结构
查询慢、增删快
添加元素
查询元素
5.List集合的实现类
5.1List集合子类的特点(记忆)
-
ArrayList集合
底层是数组结构实现，查询快、增删慢
-
ArrayList源码分析
ArrayList使用无参构造创建时，数组的长度为零。当ArrayList第一次添加元素时，创建一个新的长度为10的数组，后续每次数组要进行扩容时，每次扩大为原来的1.5倍。
-
LinkedList集合
底层是链表结构实现，查询慢、增删快
-
LinkedList示例代码
public class MyLinkedListDemo3 {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add(\"aaa\");
list.add(\"bbb\");
list.add(\"ccc\");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println(\"-------------------------\");
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
System.out.println(s);
}
System.out.println(\"--------------------------\");
for (String s : list) {
System.out.println(s);
}
}
}
5.2LinkedList集合的特有功能(应用)
-
特有方法
方法名 说明 public void addFirst(E e) 在该列表开头插入指定的元素 public void addLast(E e) 将指定的元素追加到此列表的末尾 public E getFirst() 返回此列表中的第一个元素 public E getLast() 返回此列表中的最后一个元素 public E removeFirst() 从此列表中删除并返回第一个元素 public E removeLast() 从此列表中删除并返回最后一个元素 -
示例代码
public class MyLinkedListDemo4 {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add(\"aaa\");
list.add(\"bbb\");
list.add(\"ccc\");
// public void addFirst(E e) 在该列表开头插入指定的元素
//method1(list);
// public void addLast(E e) 将指定的元素追加到此列表的末尾
//method2(list);
// public E getFirst() 返回此列表中的第一个元素
// public E getLast() 返回此列表中的最后一个元素
//method3(list);
// public E removeFirst() 从此列表中删除并返回第一个元素
// public E removeLast() 从此列表中删除并返回最后一个元素
//method4(list);
}
private static void method4(LinkedList<String> list) {
String first = list.removeFirst();
System.out.println(first);
String last = list.removeLast();
System.out.println(last);
System.out.println(list);
}
private static void method3(LinkedList<String> list) {
String first = list.getFirst();
String last = list.getLast();
System.out.println(first);
System.out.println(last);
}
private static void method2(LinkedList<String> list) {
list.addLast(\"www\");
System.out.println(list);
}
private static void method1(LinkedList<String> list) {
list.addFirst(\"qqq\");
System.out.println(list);
}
}
6.泛型
1.1泛型概述
-
泛型的介绍
泛型是JDK5中引入的特性，它提供了编译时类型安全检测机制
-
泛型的好处
-
把运行时期的问题提前到了编译期间
-
避免了强制类型转换
-
-
示例代码
/**
* 不写泛型的弊端
*/
public class GenericitySummarize {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add(\"aaa\");
list.add(\"bbb\");
list.add(\"ccc\");
list.add(123);
Iterator it = list.iterator();
while(it.hasNext()){
String next = (String) it.next();
int len = next.length();
System.out.println(len);
}
}
}
7.Set集合
2.1Set集合概述和特点【应用】
-
不可以存储重复元素
-
存取顺序不一致
-
没有索引,不能使用普通for循环遍历，跟索引相关的方法也没有。
2.2Set集合的使用【应用】
存储字符串并遍历
public class MySet1 {
public static void main(String[] args) {
//创建集合对象
Set<String> set = new TreeSet<>();
//添加元素
set.add(\"ccc\");
set.add(\"aaa\");
set.add(\"aaa\");
set.add(\"bbb\");
// for (int i = 0; i < set.size(); i++) {
// //Set集合是没有索引的，所以不能使用通过索引获取元素的方法
// }
//遍历集合
Iterator<String> it = set.iterator();
while (it.hasNext()){
String s = it.next();
System.out.println(s);
}
System.out.println(\"-----------------------------------\");
for (String s : set) {
System.out.println(s);
}
}
}
8.TreeSet集合
3.1TreeSet集合概述和特点【应用】
-
不可以存储重复元素
-
没有索引
-
不可以重复
-
可以将元素按照规则进行排序
-
TreeSet()：根据其元素的自然排序进行排序
-
TreeSet(Comparator comparator) ：根据指定的比较器进行排序
-
3.2TreeSet集合基本使用【应用】
存储Integer类型的整数并遍历
public class MyTreeSet1 {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);
ts.add(3);
ts.add(4);
ts.add(1);
ts.add(2);
System.out.println(ts);
}
}
3.3自然排序Comparable的使用【应用】
-
案例需求
-
存储学生对象并遍历，创建TreeSet集合使用无参构造方法
-
要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序
-
-
实现步骤
-
使用空参构造创建TreeSet集合
-
用TreeSet集合存储自定义对象，无参构造方法使用的是自然排序对元素进行排序的
-
-
自定义的Student类实现Comparable接口
-
自然排序，就是让元素所属的类实现Comparable接口，重写compareTo(T o)方法
-
-
重写接口中的compareTo方法
-
重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写
-
-
-
代码实现
学生类
public class Student implements Comparable<Student>{
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
测试类
public class MyTreeSet2 {
public static void main(String[] args) {
//创建集合对象
TreeSet<Student> ts = new TreeSet<>();
//创建学生对象
Student s1 = new Student(\"zhangsan\",28);
Student s2 = new Student(\"lisi\",27);
Student s3 = new Student(\"wangwu\",29);
Student s4 = new Student(\"zhaoliu\",28);
Student s5 = new Student(\"qianqi\",30);
//把学生添加到集合
ts.add(s1);
ts.add(s2);
ts.add(s3);
ts.add(s4);
ts.add(s5);
//遍历集合
for (Student student : ts) {
System.out.println(student);
}
}
} -
自然排序原理
3.4比较器排序Comparator的使用【应用】
-
案例需求
-
存储老师对象并遍历，创建TreeSet集合使用带参构造方法
-
要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序
-
-
实现步骤
-
用TreeSet集合存储自定义对象，带参构造方法使用的是比较器排序对元素进行排序的
-
比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写compare(T o1,T o2)方法
-
重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写
-
-
代码实现
老师类
public class Teacher {
private String name;
private int age;
public Teacher() {
}
public Teacher(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
测试类
public class MyTreeSet4 {
public static void main(String[] args) {
//创建集合对象
TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {
3.5两种比较方式总结【理解】
-
两种比较方式小结
-
自然排序: 自定义类实现Comparable接口,重写compareTo方法,根据返回值进行排序
-
比较器排序: 创建TreeSet对象的时候传递Comparator的实现类对象,重写compare方法,根据返回值进行排序
-
在使用的时候,默认使用自然排序,当自然排序不满足现在的需求时,使用比较器排序
-
-
两种方式中关于返回值的规则
-
如果返回值为负数，表示当前存入的元素是较小值，存左边
-
如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存
-
如果返回值为正数，表示当前存入的元素是较大值，存右边
-
-
二种方式如何确定是升序还是降序
-
自然排序
public int compareTo(Student o) {
//this在前，参数在后，表示升序
//this在后，参数在前，表示降序
//根据age年龄升序，当年龄一样的时候，根据name姓名进行升序
int result = this.age - o.age;
result = result == 0 ? this.name.compareTo(o.name) : result;
return result;
}
-
比较器排序
public int compare(String o1, String o2) {
// o1在前表示升序， o1在后表示降序。
int result = o1.length() - o2.length();
result = result == 0 ? o1.compareTo(o2) : result;
return result;
}
-
-
示例代码
存入四个字符串，\"c\" \"ab\" \"df\" \"qwer\"按照长度排序，如果长度一样则按照首字母排序
public class MyTreeSet5 {
public static void main(String[] args) {
/*TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
int result = o1.length() - o2.length();
result = result == 0 ? o1.compareTo(o2) : result;
return result;
}
});*/
//TreeSet带参构造 传递一个比较器对象 使用lambad表达式方式
TreeSet<String> ts = new TreeSet<>(
(String o1, String o2) -> {
int result = o1.length() - o2.length();
result = result == 0 ? o1.compareTo(o2) : result;
return result;
}
);
ts.add(\"c\");
ts.add(\"ab\");
ts.add(\"df\");
ts.add(\"qwer\");
System.out.println(ts);
}
}
9.数据结构
4.1二叉树【理解】
-
关于树的一些专业名称
-
节点: 在树结构中,每一个元素称之为节点
-
根节点：最顶层的节点，我们叫做根节点
-
度: 每一个节点的子节点数量称之为度
-
树高：一个树的层数，我们叫做树高
-
-
二叉树的特点
任意一个节点的度要小于等于2，即任意一个节点最多只能有二个子节点。
-
二叉树结构图
4.2二叉查找树【理解】
-
二叉查找树的特点
-
每一个节点上最多有两个子节点
-
左子树上所有节点的值都小于根节点的值
-
右子树上所有节点的值都大于根节点的值
-
-
二叉查找树结构图
-
二叉查找树和二叉树对比结构图
-
二叉查找树添加节点规则
-
小的存左边
-
大的存右边
-
一样的不存
-
4.3平衡二叉树【理解】
-
平衡二叉树的特点
-
是一个二叉查找树
-
任意节点的左右两个子树的高度差不超过1
-
-
平衡二叉树旋转
-
旋转触发时机
-
当添加一个节点之后,该树不再是一颗平衡二叉树
-
-
左旋
-
就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点
-
-
右旋
-
就是将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点
-
-
-
平衡二叉树和二叉查找树对比结构图
-
平衡二叉树旋转的四种情况
-
左左
-
左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行右旋即可
-
-
左右
-
左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡
-
如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋
-
-
右右
-
右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行左旋即可
-
-
右左
-
右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋
-
-
4.3红黑树【理解】
-
红黑树的特点
-
是一个二叉查找树
-
每一个节点可以是红或者黑
-
红黑树不是高度平衡的,它的平衡是通过\"自己的红黑规则\"进行实现的
-
-
红黑树的红黑规则有哪些
-
每一个节点或是红色的,或者是黑色的
-
根节点必须是黑色
-
如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的
-
如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连 的情况)
-
对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
-
-
红黑树添加节点的默认颜色
-
添加节点时,默认为红色,效率高
-
-
红黑树添加节点后如何保持红黑规则
-
根节点位置
-
直接变为黑色
-
-
非根节点位置
-
父节点为黑色
-
不需要任何操作,默认红色即可
-
-
父节点为红色
-
叔叔节点为红色
-
将\"父节点\"设为黑色,将\"叔叔节点\"设为黑色
-
将\"祖父节点\"设为红色
-
如果\"祖父节点\"为根节点,则将根节点再次变成黑色
-
-
叔叔节点为黑色
-
将\"父节点\"设为黑色
-
将\"祖父节点\"设为红色
-
以\"祖父节点\"为支点进行旋转
-
-
-
-
10.HashSet集合
1.1HashSet集合概述和特点(应用)
-
底层数据结构是哈希表
-
存取无序
-
不可以存储重复元素
-
没有索引,不能使用普通for循环遍历
1.2HashSet集合的基本应用(应用)
public class HashSetDemo {
public static void main(String[] args) {
//创建集合对象
HashSet<String> set = new HashSet<String>();
//添加元素
set.add(\"hello\");
set.add(\"world\");
set.add(\"java\");
set.add(\"java\");
set.add(\"java\");
set.add(\"java\");
//迭代器遍历
Iterator<String> it = set.iterator();
while (it.hasNext()) {
String next = it.next();
System.out.println(next);
}
System.out.println(\"=================\");
//增强for遍历
for (String s : set) {
System.out.println(s);
}
}
}
1.3哈希值(理解)
-
哈希值简介
根据对象的地址值或者属性值计算出来的一个int类型的整数
-
如何获取哈希值
Object类中的public int hashCode()：返回对象的哈希码值
-
哈希值的特点
-
如果没有重写hashcode方法，那么就根据对象的地址值进行计算哈希值
针对同一个对象，返回的哈希值相同，针对不同的对象，返回的哈希值不同
-
如果重写了hashcode方法，一般都是根据对象的属性值来进行重写。
如果不同对象的属性值相同，那么它们的哈希值也是一样的。
-
-
示例代码
public class HashSetDemo2 {
public static void main(String[] args) {
Student s1 = new Student(\"张三\",23);
Student s2 = new Student(\"张三\",23);
Student s3 = new Student(\"李四\",24);
//如果Student类没有重写hashcode方法，则根据地址值计算哈希值
//如果重写了则一般根据属性值进行计算哈希值
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
System.out.println(s3.hashCode());
}
}
public class Student {
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}