数据结构
l 栈 特点：先进后出 出入口在同一个 先进去的元素最后面才能出来，First In Last Out；
（1）Main 方法先进栈调用，然后main方法内部的方法进栈调用完毕，main才能出栈；
（2）反转作用（就是车尾变车头）
^ |
| v
| | 出入口在同一端
| +---------+ |
| | 3 | |
| +---------+ |
| +---------+ |
| | 2 | | 栈
| +---------+ |
| +---------+ |
| | 1 | |
| +---------+ |
+-------------+
栈的特点:
先进后出 (FILO, First In Last Out)
入口和出口在同一侧
入栈(压栈):将元素存入栈
出栈(弹栈):从栈中取出元素
栈的适用场景:
栈内存 (main方法先进栈调用, main方法中的其他方法都调用完毕后, main才能出栈)
反转内容 (车尾变车头, 进去再出来就反转了)
2.队列 quaue 特点 先进先出 入口跟出口在两端
使用场景
（1）秒杀，抢购
（2）在线售票
（3）处理高并发场景
队列:
入口 出口
-----------------------------------------------
+---------+ +---------+ +---------+
----> | 3 | | 2 || 1 | ---->
+---------+ +---------+ +---------+
-----------------------------------------------
队列的特点:
先进先出 (FIFO, First In First Out)
入口和出口在两端
队列的适用场景:
秒杀, 抢购
在线售票
处理高并发场景
l 数组 特点：数组长度不可变 查询快 增删慢
数组:
0x01 0x02 0x03 0x04 0x05
+-----+-----+-----+-----+-----+
|"a" | "b" | "c" | "d" | "e" |
+-----+-----+-----+-----+-----+
0 1 2 3 4
数组的特点:
查询快: 通过 (第一个元素地址值 + 索引) 可以快速计算出该索引元素的地址值
增删慢: 增加一个元素, 要创建长度+1的新数组, 然后将原数组元素复制到新数组, 然后存入新元素; 删除类似
// 添加元素
+-----+-----+-----+-----+-----+
|"a" | "b" | "c" | "d" | "e"| 如果要添加元素"f"
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+-----+
|"a" | "b" | "c" | "d" | "e" |"f" | 创建一个新数组, 将原数组元素复制进去, 然后存入新元素
+-----+-----+-----+-----+-----+-----+
数组的适用场景:
查询多, 增删少的数据存储场景 国内城市
（1） 数组的地址是连续的，我们通过数组的首地址可以找到数组，通过索引可以快速的查找
（2） 数组的长度是不可变得，我们要增删一个元素，必须创建一个新数组
l 链表 特点 查询慢 增删快（理解自行车的车链子）
1. 查询慢：链表中的地址不是连续的每次查询元素都要从头开始查询
2. 增删快：链表结构增删/删除一个元素对链表的结构没有影响
链表: 链表由多个 节点(Node /Entry) 组成
+-----+-----+-----+ +-----+-----+
| | | | |数据 | |
+-----+-----+-----+ +-----+-----+
单向链表: 每个节点存储 数据 和 下一个节点的地址值
链表 = 0x11;
0x11 0x44 0x88
+-----+-----+ +-----+-----+ +-----+-----+
|"a" | 0x44| --> | "b" | 0x88| --> | "c" |null|
+-----+-----+ +-----+-----+ +-----+-----+
数据 下一个 数据 下一个 数据 下一个
双向链表: 每个节点存储 数据, 上一个节点地址值和 下一个节点地址值
0x11 0x44 0x88
+-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+
|null| "a" | 0x44| <--> |0x11 | "b" | 0x88| <-->|0x44 | "c" | null|
+-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+
上一个 数据 下一个 上一个 数据 下一个 上一个 数据 下一个
l 链表的特点:
查询慢: 要找到其中某个节点, 只能从第一个节点一个一个向后寻找
增删快: 只需要修改保存的下一个节点的地址值, 就可以快速完成增删
//删除结点
+---+ +---+ +---+
|1 |----| 2 |----| 3 |
+---+ +---+ +---+
+---+ +---+
|1 |-------------| 3 |
+---+ +---+
+---+
| 2 |
+---+
l 链表的适用场景:
使用场景： 查询少 增删多
链表可以实现栈和队列的结构, 因为栈和队列增删频繁
l 节点
l 单向链表
一个一个往下找，方法只能一个
// 单向链表的节点
class Node<T> {
Tdata; // 存储的数据
Nodenext; // 下一个节点的地址值
}
l 双向链表
方向是两个 可以反方向
// 双向链表的节点
classNode<T> {
T data; // 存储的数据
Node before; // 上一个节点的地址值
Node after; // 下一个节点的地址值
}
l 双重链表
双重链表，一个存储顺序，一个存储数组
l 红黑树 特点
二叉树：分支不能超过两个
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image020.png
排序树/查找树：查找速度非常快，数字左边小右边大
是一种 平衡 二叉 查找 树
平衡: 左子节点和右子节点数量相等
二叉: 每个节点最多有2个子节点
查找: 节点存储的元素是按照大小顺序存储的
特点:
元素存储过程中就完成了大小排序
查询比链表快, 增删比数组快 (数组和链表的折中)
l 红黑树的适用场景:
查询和增删都有, 需要元素自动排序的场景
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image022.png
l 平衡树和不平衡树
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image024.png
红黑树 特点：近似于平衡树，查询的非常快，查询叶子的节点最大次数和最小次数不能超过2倍
约束：
（1） 节点可以是红色的或者黑色的
（2） 根节点是黑色
（3） 叶子的节点（空节点）是黑色的
（4） 每个红色的节点的子节点都是黑色的
（5） 任何一个节点到
节点添加的方法和节点的遍历 先往左边走有子节点往左没有就直接取值往右
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image026.png
l 红黑树趋近于平衡如下图
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image028.png
数组跟链表都需要遍历才能比大小
树形结构红黑树比大小很方便效率高简单
u List接口 继承了Collection
特点
（1） 元素存取有序 (存入和取出元素的顺序一致)321->321 排序: 从小到大
（2） 元素可以重复 1 1 1 1
（3） 有索引
l 常用特有成员方法 (都是按照索引来操作的)
1.void add(int index, E element):将指定的元素,添加到该集合中的指定位置上
2.E get(int index): 返回集合中指定位置的元素
3.E remove(int index):移除列表中指定位置的元素, 返回的是被移除的元素
4.E set(int index, E element):用指定元素替换集合中指定位置的元素, 返回值的更新前
使用时注意索引越界异常
数组越界异常
1.void add(int index, E element):将指定的元素,添加到该集合中的指定位置上
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image030.png
打印的不是地址值重写了toString方法
添加索引位置添加元素 如果原索引有元素也可以添加往后退一位
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image032.png
3.E remove(int index):移除列表中指定位置的元素, 返回的是被移除的元素
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image034.png
4.E set(int index, E element):用指定元素替换集合中指定位置的元素, 返回值的更新前 file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image036.png
l 集合的遍历的方式
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image038.png
l List 接口底下实现类 ArrayList集合的
ArrayList底层的数据结构:
数组
ArrayList的特点:
查询快
增删慢
线程不安全, 效率高
ArrayList适用场景:
存储的数据"查询多, 增删少"的场景. 如用一个ArrayList存储中国城市名称
重点 数据结构：底层是一个数组（是一个而多线程的线程不安全数组效率高）
（1） 查询快 ，增删慢
l 实现类 LinkedList（链表形式）
（1） 查询慢 增删快 线程不安全，效率高
（2） 包含了大量首尾操作的方法
（3） 注意LinkedList集合特有方法不能使用多态
（4） 集合特点 数据结构：底层是一个链表结构
l 特有成员方法(主要操作开头和末尾元素)
树
（1）void addFirst(E e):将指定元素插入此列表的开头
（2）void addLast(E e): 将指定元素添加到此列表的结尾
（3）E getFirst(): 返回此列表的第一个元素
（4）E getLast(): 返回此列表的最后一个元素
（5）E removeFirst(): 移除并返回此列表的第一个元素
（6）E removeLast(): 移除并返回此列表的最后一个元素
（7）E pop(): (其实就是removeFirst())从此列表所表示的栈中弹出一个元素
（8）void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中
使用add添加元素
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image040.png
（1）void addFirst(E e): 将指定元素插入此列表的开头
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image042.png
（8）void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image044.png
（3）E getFirst(): 返回此列表的第一个元素
（4）E getLast(): 返回此列表的最后一个元素
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image046.png
增加一个判断isEmpty来判断集合不为空集合从而获取集合的首个，和尾个对象
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image048.png
（5）E removeFirst(): 移除并返回此列表的第一个元素，就是被删除的元素
（6）E removeLast(): 移除并返回此列表的最后一个元素，就是被删除的元素
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image050.png
x Vector底层的数据结构: 了解就行
（1）数组
Vector的特点:
（1）查询慢
（2）增删快
(同步)线程安全, 效率低
x Vector目前几乎没人使用
1. 不允许存储相同元素
2. 没有索引值Set 接口 继承了Collection
l HashSet集合
l Set集合体系特点:
1. 元素不可重复
2. 没有索引
树 HashSet特点:
1. 元素不可重复
2. 没有索引
3. 元素存取无序 (存入和取出顺序有可能不一致)
4. 底层采用 哈希表 结构. (查询快)
哈希表 = 数组 + 链表或红黑树
树 // 常用方法
booleanadd(E e): 添加元素, 根据元素的 hashCode() 和equals() 方法判断是否重复. 重复则不添加并返回false,不重复则添加并返回true
往集合添加，遍历set集合 特点不能存储重复 没有顺序 无序的集合
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image052.png
结果是 123 输出不能显示重复的元素
l HashSet原理：哈希值
哈希值:
一个十进制数值, 一般是通过将该对象的内部地址转换成一个整数来实现的
树
public native int hashCode();
可以调用系统本地代码(C/C++)计算出一个对象地址的哈希值
hashCode()方法的作用
方法内部的算法用于将对象计算为一个哈希值, 便于根据哈希值比较对象是否"相等"
哈希值主要是为了提高对象存储在哈希表 中的效率
注意:
1. 如果我们不满意Object中的哈希值计算方法, 可以重写hashCode()方法.
但在Java代码中不能直接重写带有 native 的方法, 重写时应该将native 去掉
@Override
public int hashCode() {}
树
hashCode() 方法有可能将"不同的对象"计算出"相同的哈希值", 这称为"哈希冲突", 在出现冲突后, 一般再通过 equals() 方法来继续判断对象是否"相等"
"重地" "通话"
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image054.png
l 返回的是一个整数，是一个十进制的整数。重写的显示重写的
字符串类的哈希值 如下图：
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image056.png
l 哈希值冲突再通过equals方法比较最后做结果
2. hashCode() 方法有可能将"不同的对象"计算出"相同的哈希值", 这称为"哈希冲突", 在出现冲突后, 一般再通过 equals() 方法来继续判断对象是否"相等"
"重地" "通话"
l 哈西塞的底层是 哈希表 特点 查询速度快
哈希表:
JDK 8以前 : 哈希表 = 数组 + 链表
JDK 8及之后 : 哈希表 = 数组 + 链表或红黑树
数组中存储的每个元素, 是哈希值相同的一组节点的链表或红黑树
l 哈希值原以及哈希值冲突的原理
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image058.png
l 如果链表的长度超过8位就会转换为红黑树：
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image060.png
l Set 怎么实现不重复元素的原理代码演示
HashSet集合保证添加元素不重复的原理:
调用 add(E e) 添加元素时, 先调用 hashCode() 获取哈希值, 和当前HashSet集合中的元素比较
如果哈希值不同, 则认为元素不重复, 添加, 并返回true
如果哈希值相同, 则可能是哈希冲突, 所以继续调用元素的 equals() 方法和所有哈希值相同的元素比较
如果equals() 比较所有元素都没有相同的, 则认为元素不重复,添加, 并返回true
如果equals() 比较出有相同的元素, 则认为元素重复, 不添加, 并返回false
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image062.png
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image064.png
l Set.add(s1)
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image066.png
l Set.add(s2)
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image068.png
l Set.add（”重地”）
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image070.png
l Set.add（“通话”）
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image072.png
l Set元素不重复的原理HashSet存储自定义元素的去重
自定义JavaBean对象实现在HashSet中去重:
JavaBean默认继承Object类中的 hashCode() 和 equals() 方法, 都是根据对象地址值判断是否重复的
要根据属性值判断是否重复, 应该在JavaBean类中重写 hashCode() 和 equals() 方法, 使其按照属性值比较
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image074.png
l LinkedHashSet集合 继承了HashSet 变相的Set接口
l LinkedHashSet特点:
1. 元素存取有序 (存入和取出顺序一致)
2. 元素不可重复
3. 没有索引
l LinkedHashSet底层数据结构:
哈希表 + 链表 (也就是: 数组 + 链表或红黑树 + 链表)
树
其中, 哈希表用于存储数据, 额外的链表用于记录元素添加时的先后顺序, 以便在获取元素时保持顺序一致
总结: 什么时候用List, 什么时候用Set?
要存储的元素可以重复的, 用List集合:
增删少, 用ArrayList
增删多, 用LinkedList
要存储的数据要求不重复, 或者相对一个集合去重, 用Set集合:
不要求存取顺序一致, 用HashSet
要求存取顺序一致, 用LinkedHashSet
l 代码解释：LinkedHashSet 有序不重复没有索引
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image076.png
l 可变参数
可变参数:
JDK5 出现. 指同一个类型的参数, "个数可变"
可变参数的本质就是一个"数组"
格式: 用在方法的参数中
树 修饰符返回值类型 方法名(int... 变量名) {
// 可以直接将 变量名 当作 数组名 使用
}
方法名();
注意事项:
1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
2. 一个方法的参数列表中, 只能有一个可变参数
3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后
l 使用可变参数前提： file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image078.png
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image080.png
l 可变参数的原理：
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image082.png
l Collections集合工具类: addAll(),shuffle()
树
java.util.Collections类: 操作集合的工具类
// 静态方法
static <T> boolean addAll(Collection<?super T> c, T... elements):往集合中添加一些元素
static void shuffle(List<?> list):打乱集合顺序
static <T> void sort(List<T> list):将集合中元素按照默认规则排序
static <T> void sort(List<T> list，Comparator<? super T> c):将集合中元素按照指定规则排序
public class Test {
public static void main(String[] args) {
// 创建集合
ArrayList<Integer> list = new ArrayList<>();
// 添加多个元素
Collections.addAll(list, 1, 2, 3, 4, 5);
// 打乱
Collections.shuffle(list);
// 打印
System.out.println(list);
l Collections集合工具类:sort(List<T> list)
sort(List<T> list): 默认按照"升序"将元素排序
数字, 字母, 都可以按照升序排序
自定义JavaBean对象默认不能排序,因为不知道如何比较哪个对象大, 哪个对象小
自定义JavaBean对象要想排序, 需要实现 Comparable<E> 接口, 重写 int compareTo(E e) 方法
规则:
this-参数: 升序(从小到大)
参数-this: 降序(从大到小)
l 实现Person排序
public class Person implementsComparable<Person>{ // 注意写上泛型
@Override
public int compareTo(Person o) {
return this.getAge() - o.getAge(); // 按照年龄升序排序
}
private String name;
private int age;
public Person() {
}
public Person(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;
}
@Override
public String toString() {
return "Person{" +
"name='" + name +'\'' +
", age=" + age +
'}';
}
}
public class Test {
public static void main(String[] args) {
// 创建3个Person对象
Person p1 = new Person("李四", 14);
Person p2 = new Person("张三", 13);
Person p3 = new Person("王五", 15);
// 创建集合
ArrayList<Person> list = new ArrayList<>();
list.add(p1);
list.add(p2);
list.add(p3);
System.out.println("排序前:" + list);
// 排序
Collections.sort(list);
System.out.println("排序后:" + list);
/*
排序前:[Person{name='李四', age=14}, Person{name='张三', age=13},Person{name='王五', age=15}]
排序后:[Person{name='张三', age=13}, Person{name='李四', age=14},Person{name='王五', age=15}]
*/
}
}
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image084.png
file:///C:/Users/939969~1/AppData/Local/Temp/msohtmlclip1/01/clip_image086.png
l Collections集合工具类:sort(List<T> list，Comparator<? super T> )
l Comparable接口和Comparator接口区别
Comparable:让JavaBean自身具有可比较性 (自己和其他人比)
Comparator:定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)
Comparator使用方式:
1. 定义类实现Comparator<E>接口, 重写 int compare(E o1, E o2) 方法, 泛型为比较元素的类型
规则:
o1-o2: 升序(从小到大)
o2-o1: 降序(从大到小)
2. 在Collections.sort(List<T> list，Comparator<? super T> c)方法中传入自定义比较器对象
l 使用Comparator对Person集合排序
public class Person {
private String name;
private int age;
public Person() {
}
public Person(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;
}
@Override
public String toString() {
return "Person{" +
"name='" + name +'\'' +
", age=" + age +
'}';
}
}
public class Test {
public static void main(String[] args) {
// 创建Person对象
Person p1 = new Person("李四", 14);
Person p2 = new Person("张三", 13);
Person p3 = new Person("王五", 15);
// 创建ArrayList
ArrayList<Person> list = new ArrayList<>();
list.add(p1); list.add(p2);
播妞在线
list.add(p3);
System.out.println("排序前:" + list);
// 排序
Collections.sort(list, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() -o2.getAge(); // 按照年龄升序
}
});
System.out.println("排序后:" + list);
}
}
u 今日API
java.util.List<E>接口:
//常用特有成员方法 (都是按照索引来操作的)
public void add(int index, E element):将指定的元素, 添加到该集合中的指定位置上
public E get(int index):返回集合中指定位置的元素
public E remove(int index):移除列表中指定位置的元素, 返回的是被移除的元素
public E set(int index, E element):用指定元素替换集合中指定位置的元素, 返回值的更新前的元素
java.util.LinkedList<E>类: 链表结构, 查询慢, 增删快
//特有成员方法(主要操作开头和末尾元素)
void addFirst(E e):将指定元素插入此列表的开头
void addLast(E e):将指定元素添加到此列表的结尾
E getFirst():返回此列表的第一个元素
E getLast():返回此列表的最后一个元素
E removeFirst():移除并返回此列表的第一个元素
E removeLast():移除并返回此列表的最后一个元素
E pop():(其实就是removeFirst())从此列表所表示的堆栈处弹出一个元素 栈stack
void push(E e):(其实就是addFirst())将元素推入此列表所表示的堆栈
java.util.Set<E>接口:
//成员方法
booleanadd(E e): 添加元素. 元素不重复则添加成功, 返回true; 否则返回false
java.util.Collections类: 操作集合的工具类
//静态方法
static <T> boolean addAll(Collection<T> c, T... elements):往集合中添加一些元素
static void shuffle(List<?> list):打乱集合顺序
static <T> void sort(List<T> list):将集合中元素按照默认规则排序
static <T> void sort(List<T> list，Comparator<? super T> c):将集合中元素按照指定规则排序
收藏
淘帖
踩
