第一章 数据结构
1.1 数据结构的作用
- Java是面向对象的语音,好似自动挡汽车,c语音手动挡,数据结构?
- 数据结构:是变速箱的工作原理。
- 你完全可以不懂变速箱怎样工作,就可以把自动挡车从a开到b,而且未必跑到比懂得人慢。
- 编程经验起到很大作用,但是不懂底层原理,就只能开车,不会修车,也不会造车。
- 这里讲常见的:堆栈,队列,数组,链表,红黑树。
- 要求:
- 这里入门数据结构,了解每一个特性。
1.2 数据结构_栈—子弹弹夹
- 栈:stack,又称堆栈——特点:先进后出【重点】
- 入口和出口在同一侧
- 入栈也叫压栈
- 出栈也叫弹栈
1.3 数据结构_队列—排队安检
- 队列:queue——特点:先进先出【重点】
- 入口和出口在两侧
1.4 数据结构_数组
- 数组:Array——特点:查询快,增删慢【重点】
- ++查询快++:数组的地址是连续的,我们通过数组的首地址可以找到数组,通过数组的索引可以快速查找某一个元素
- ++增删慢++:数组的长度是固定的,我们想要增加/删除一个元素,必须创建一个新数组,把源数组的数据复制过来。
- 在堆内存中,频繁的创建数组,复制数组中的元素,销毁数组:效率低下
1.5 数据结构_链表
- 链表:linked list——特点:查询慢,增删快【重点】
- ++查询慢++:链表中地址不是连续的,每次查询元素,都必须从头查询。
- ++增删快++:链表结构,增加/删除一个元素,对链表的整体结构没有影响,所以增删快
- 由一系列结点node组成,每个结点包括两部分。
- ++存储数据元素++的数据域
- ++存储下一个结点地址++的指针域
- 常说的链表:单向链表和双向链表–>这里介绍单向链表。
- 单向链表:链表中只有一条链子,不能保证元素的顺序(存储元素和取出元素的顺序有可能不一致)
- 双向链表:链表中有两条链子,有一条链子是专门记录元素的顺序,是一个有序的集合(存元素和取元素顺序一致)
- 链表中每一个元素称为结点:
- 一个结点包含了一个数据域(存储数组),两个指针域(存储地址)【!】
1.6 数据结构_红黑树
- 二叉树:binary tree
- 是每个结点不超过2个的有序数(tree)
- 左子树(左孩子)和右子树(右孩子)
- 排序树/查找树:
- 在二叉树的基础上,元素是有大小顺序的
- 左子树小,右子树大
- 平衡数:++查询快++
- 左子树和右子树相等
- 不平衡数:
- 左子树和右子树不相等
- 红黑树:
- 特点:
- 趋近于平衡树,查询的速度非常快【重点】
- 查询叶子节点最大次数和最小次数不能超过2倍
- 例:最小查找次数1,最大查找次数4–>就不是红黑树
- 约束:
- 节点可以是红色的或者黑色的
- 根节点是黑色的
- 叶子节点(空节点)是黑色的
- 每个红色的节点的子节点都是黑色的
- 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
第二章 List集合
2.1 List接口介绍
- java.util.List接口 extends Collection接口
- List三大特点:
- 有序的集合:存储元素和取出元素的顺序是一致的(存储123 取出也是123)
- 有索引:包含了一些带索引的方法
- 允许存储重复的元素
- List接口中带索引的方法(++特有++):
- void add(int index, E element)
- 在列表的指定位置插入指定元素(可选操作)
- E get(int index)
- 返回列表中指定位置的元素
- E remove(int index)
- 移除列表中指定位置的元素(可选操作)
- E set(int index, E element)
- 用指定元素替换列表中指定位置的元素(可选操作)
- 注:在操作索引的时候,一定要防止索引越界异常
- IndexOutOfBoundsException越界异常
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");
System.out.println(list); //[a, b, c, d, a]:不是地址重写了toString
//void ==add==(int index, E element)
//在c,d之间添加一个张子玄
list.add(3, "张子玄"); //[a, b, c, 张子玄, d, a]
System.out.println(list);
//E ==remove==(int index)
//移除c元素
String removeE = list.remove(2);
System.out.println("被移除的元素" + removeE);
System.out.println(list);
//E ==set==(int index, E element)
//替换最后一个a为A
String setA = list.set(4, "A");
System.out.println("替换的元素:" + setA);
System.out.println(list);
//E ==get==(int index)
//使用普通for循环来遍历集合
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println("=============");
//使用迭代器Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()){
String next = it.next();
System.out.print(next + " ");
}
System.out.println("=============");
//使用增强for
for (String s : list) {
System.out.print(s + " ");
}
}
//结果:
[a, b, c, d, a]
[a, b, c, 张子玄, d, a]
被移除的元素c
[a, b, 张子玄, d, a]
替换的元素:a
[a, b, 张子玄, d, A]
a b 张子玄 d A =============
a b 张子玄 d A =============
a b 张子玄 d A
2.2 ArrayList集合
- java.util.ArrayList集合:List接口的大小可变数组的实现
- 底层数据存储结构是:数组结构【特点】
- 增删慢,查找快【重点】
- 此实现不是同步的——多线程
- 效率高,速度快
- 常用功能:
- ++查询数据++
- ++遍历数据++
2.3 LinkedList集合
- java.util.LinkedList集合 implements List接口
- 底层数据存储结构是:链表结构【特点】
- 增删快,查找慢【重点】
- 此实现不是同步的——多线程
- 效率高,速度快
- 常用功能:
- ++添加数据++
- ++删除数据++
- LinkedList是一个双向链表如下:
- ++找头和尾很方便,所以有大量操作首尾元素的方法++
- 使用LinkedList集合中特有的方法,不能使用多态(看不到子类的特有方法)
- ++注:push方法等效于addFirst++
- 注:++getFirst和getLast加一个isEmpty判断++——不然报错
- ++注:pop方法等效于removeFirst++
public class Demo02LinkedList {
public static void main(String[] args) {
//show01();
//show02();
show03();
}
//三个移除的方法
private static void show03() {
LinkedList<String> linked = new LinkedList<>();
linked.add("a");
linked.add("b");
linked.add("c");
linked.add("d");
System.out.println(linked); //[a, b, c, d]
//removeFirst
String s = linked.removeFirst();
System.out.println("移除的第一元素:" + s);
System.out.println(linked);
//pop等效于removeFirst
String pop = linked.pop();
System.out.println("移除了第一个元素" + pop);
System.out.println(linked);
//removeLast
String s1 = linked.removeLast();
System.out.println("移除的第一元素:" + s1);
System.out.println(linked);
//结果:
// [a, b, c, d]
// 移除的第一元素:a
// [b, c, d]
// 移除了第一个元素b
// [c, d]
// 移除的第一元素:d
// [c]
}
//两个返回方法
private static void show02() {
LinkedList<String> linked = new LinkedList<>();
linked.add("a");
linked.add("b");
linked.add("c");
System.out.println(linked); //[a, b, c]
if(!linked.isEmpty()){
//getFirst
String first = linked.getFirst();
System.out.println(first); //a
//getLast
String last = linked.getLast();
System.out.println(last); //c
}
}
//三个添加方法
private static void show01() {
LinkedList<String> linked = new LinkedList<>();
linked.add("a");
linked.add("b");
linked.add("c");
System.out.println(linked); //[a, b, c]
/* //addFirst——添加到开头
linked.addFirst("wwww");
System.out.println(linked); //[wwww, a, b, c]*/
/* //push——等效于addFirst
linked.push("abc");
System.out.println(linked); //[abc, a, b, c]*/
//addLast——添加到尾
linked.addLast("com");
System.out.println(linked); //[a, b, c, com]
}
}
2.4 Vector集合
- java.util.Vector集合(1.0版本),底层是数组
- 与新collection实现不同,Vector是同步的——单线程
- 速度慢,1.2版本后被ArrayList取代
第三章 Set集合
3.1 Set接口
- java.util.Set接口 extends Collection接口
- Set接口的特点:
- 不允许存储重复的元素(唯一)
- 没有索引,没有带索引的方法,也不能使用普通for循环遍历
3.2 HashSet集合介绍
- java.util.HashSet接口 implements Set接口
- 底层由哈希表结构(实际上是一个HashMap实例)支持。
- 速度快
- 此实现不是同步的——多线程
- 效率高,速度快
- HashSet的特点:
- 不允许存储重复的元素(唯一)
- 没有索引,没有带索引的方法,也不能使用普通for循环遍历
- 是一个无序集合,存储元素和取出元素的顺序有可能不一致
3.3 哈希值
- 哈希值(hashCode):是一个十进制整数,由系统随机给出(就是对象的地址值,是一个逻辑地址,是模拟出来得到的地址,不是数据实际存储的物理地址)
- 在Object类中有一个方法,可以获取对象的哈希值。
- int hashCode()
- 返回该对象的哈希码值。
- 特殊哈希值:
- String类的哈希值
- String类重写了Object类的hasCode方法
public static void main(String[] args) {
Person p1 = new Person();
int h1 = p1.hashCode();
System.out.println(h1);
Person p2 = new Person();
int h2 = p2.hashCode();
System.out.println(h2);
System.out.println(p1);
System.out.println(p2);
System.out.println(p1 == p2);
//String重写了hashCode方法
String s1 = new String("abc");
String s2 = new String("abc");
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
}
3.4 hashSet集合存储数据的结构—哈希表
- 哈希表:JDK1.8之前:底层采用数组+链表实现。JDK1.8之后:底层采用数组+链表+红黑树实现。
- 哈希表的特点:
- 速度快
- 步骤:
- 先按相同哈希值进行一个分组(数组)
- 然后将相同元素类挂在一起(链表)
- 如果挂在一起数超过8个,将链表转换为红黑树(红黑树)
- 注:默认16空间,如果超了就加一倍
3.5 Set集合存储元素不重复的原理
- Set集合在调用add方法的时候
- add方法会调用元素的hashCode方法和equals方法,判断元素是否重复。
- Set集合存储元素不重复的元素
- 前提:存储的元素必须重写hashCode方法和equals方法
public static void main(String[] args) {
HashSet<String> setH = new HashSet<>();
String s1 = new String("abc");
String s2 = new String("abc");
setH.add(s1);
setH.add(s2);
setH.add("重地");
setH.add("通话");
setH.add("abc");
System.out.println(setH); //[重地, 通话, abc]
}
3.6 HashSet存储自定义类型元素
- Set集合保证元素唯一:
- 存储的元素(String, Integer,…,Student,Person),必须重写hashCode方法和equals方法
- 总结:
- 只要是用HashSet存储自定义类型元素,必须重写hashCode方法和equals方法【重点】
// 自定义类型元素要求:
// 同名同年龄的人,视为同一个人,只能存储一次
//定义一个Person类
public class Person {
private String name;
private int age;
public Person() {
}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person person = (Person) o;
return getAge() == person.getAge() &&
Objects.equals(getName(), person.getName());
}
@Override
public int hashCode() {
return Objects.hash(getName(), getAge());
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", 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;
}
}
//定义主方法:Demo03HashSetPerson.java
public static void main(String[] args) {
HashSet<Person> setH = new HashSet<>();
Person p1 = new Person("小美女", 18);
Person p2 = new Person("小美女", 18);
Person p3 = new Person("小美女", 19);
setH.add(p1);
setH.add(p2);
setH.add(p3);
System.out.println(setH);
}
//没重写前结果:
[Person{name='小美女', age=19}, Person{name='小美女', age=18}, Person{name='小美女', age=18}]
//重写后结果:
[Person{name='小美女', age=19}, Person{name='小美女', age=18}]
3.7 LinkedHashSet集合
- (API)具有可预知迭代顺序的Set接口
- java.util.LinkedHashSet集合 extends HashSet集合
- LinkedHashSet集合的特点:
- 底层是一个哈希表(数组+链表+红黑树)+链表:多了一条链表(记录元素的存储顺序),保证元素有序
public static void main(String[] args) {
HashSet<String> setH = new HashSet<>();
setH.add("www");
setH.add("abc");
setH.add("abc");
setH.add("itcast");
System.out.println(setH); //无序,不重复
System.out.println("============");
LinkedHashSet<String> setLH = new LinkedHashSet<>();
setLH.add("www");
setLH.add("abc");
setLH.add("abc");
setLH.add("itcast");
System.out.println(setLH); //有序,不重复
}
//结果:
[abc, www, itcast]
============
[www, abc, itcast]
第四章 可变参数
1.1 可变参数…
- JDK1.5之后的新特性
- 使用前提:(定义方法时使用)【重点】
- 当方法的参数列表当中数据类型已经确定,但是参数的个数不确定,就可以使用可变参数
- 使用格式:
修饰符 返回值类型 方法名(数据类型...变量名){
//...
}
- 可变参数的原理:
- 可变参数的底层就是一个数组,根据传递参数个数不同,会创建不同长度的数组,来存储这些参数
- 传递的参数个数,可以是0个(不传递),1,2…多个
- 可变参数的注意事项:
- 一个方法的参数列表,只能有一个可变参数。
public static int method(int...num){}
- 如果方法的参数有多个,那么可变参数必须写在参数列表的末尾。
public static int method(int a, int b, int...num){}
- 可变参数的终极(特殊)写法:
- Object类型的可变参数(这样就可以是任意数据类型,不需要知道了)
public static void method(Object...obj){}
public class Demo05VarArgs {
public static void main(String[] args) {
int i = add(1, 3, 5, 7, 8);
System.out.println(i); //24
}
//定义一个方法,计算0-n任意个int类型整数的和
public static int add(int...arr){
int sum = 0;
//用增强for来累加
for (int i : arr) {
sum += i;
}
return sum;
}
}
第五章 Collections工具类
5.1 Collections概述及方法
- Collections工具类:来对操作集合的工具类
- 常用的方法:
- static boolean
addAll(Collection<? super T> c, T… elements)
- 将所有指定元素添加到指定 collection 中(往集合中添加多个元素【重点】)
- static void shuffle(List<?> list)
- 使用默认随机源对指定列表进行置换。 (打乱集合顺序)
- static void sort(List list)
*根据元素的自然顺序对指定列表按升序进行排序(将集合元素按照默认规则排序(升序)) - static void sort(List list, Comparator<? super T> c)
*根据指定比较器产生的顺序对指定列表进行排序(将集合元素按照指定规则排序)
- addAll和shuffle演示:
public static void main(String[] args) {
ArrayList<String> listA = new ArrayList<>();
//往集合添加多个元素
/* listA.add("a");
listA.add("a");
listA.add("a");
listA.add("a");
listA.add("a");*/
//添加麻烦,所以使用Collections的addAll方法
Collections.addAll(listA, "a", "b", "c", "d");
System.out.println(listA); //[a, b, c, d]
//使用Collections的shuffle方法:打乱集合顺序
Collections.shuffle(listA);
System.out.println(listA); //[a, c, b, d]
}
- 默认sort方法演示:
- 不管数字还是字符串,他们都实现了Comparable接口【重点】
- 实现的目的是: 重写该接口中的compareTo方法
- 自定义类型类用到Collections的sort方法时【重点】:
- 只要是用到Collections工具类中sort方法的自定义类型类,必须实现Comparable接口,重写他的方法compareTo【重点】
- comparable接口的排序规则:
- 自己(this)-参数:升序
- ++默认是升序++:从小到大
- 字符串是按照自然排序来进行升序
public static void main(String[] args) {
ArrayList<Integer> listA = new ArrayList<>();
/* listA.add(1);
listA.add(3);
listA.add(2);*/
Collections.addAll(listA, 1, 3, 2);
System.out.println("数字排序前:");
System.out.println(listA); //[1, 3, 2]
//默认sort——升序
Collections.sort(listA);
System.out.println("数字默认sort排序后:");
System.out.println(listA); //[1, 2, 3]
System.out.println("=============");
ArrayList<String> listB = new ArrayList<>();
Collections.addAll(listB, "a", "c", "b");
System.out.println("字符串排序前:");
System.out.println(listB); //[a, b, c]
//默认sort——升序
Collections.sort(listB);
System.out.println("字符串默认sort排序后:");
System.out.println(listB); //[1, 2, 3]
}
- 指定规则sort方法演示:
- static void sort(List list, Comparator<? super T> c)
2. 格式:
Collections.sort(listA, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; //升序 } });
3. 注:return o1 - o2; //升序
4. 比较单个(数组,字符等)不能直接比较字符串等。 - Comparator接口和Comparable接口的区别:
- Comparable:自己(this)和别人(参数)比较,自己需要实现Comparable接口,重写比较的规则compareTo方法
- Comparator:相当于找了一个第三方裁判,比较两个人
- 重写了compare方法
public static void main(String[] args) {
ArrayList<Integer> listA = new ArrayList<>();
/* listA.add(1);
listA.add(3);
listA.add(2);*/
Collections.addAll(listA, 1, 3, 2);
System.out.println("数字排序前:");
System.out.println(listA); //[1, 3, 2]
//规则sort——升序
Collections.sort(listA, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
System.out.println(listA);
}
//结果:
数字排序前:
[1, 3, 2]
[1, 2, 3]