[学习交流] 【石家庄校区】就业班day03-List,Set

Bin@

day03 List Set 今天我们来学习java中几种常见的数据结构：栈、队列、数组、链表、红黑树。然后学习单列集合体系，List和Set。
以下是今天的学习目标：
能够说出List集合特点
能够说出常见的数据结构
能够说出数组结构特点
能够说出栈结构特点
能够说出队列结构特点
能够说出单向链表结构特点
能够说出Set集合的特点
能够说出哈希表的特点
使用HashSet集合存储自定义元素
能够说出可变参数的格式
能够使用集合工具类
能够使用Comparator比较器进行排序

以下是今天的详细笔记：

数据结构数据结构: 就是数据的存储方式
不同的数据结构代表了不同的存储方式
不同的数据结构中, 会有不同的存入, 取出, 查找的方式和效率, 数据的存放方式也不同

如薯片, 可以用长纸筒装, 也可以用塑料包装袋装, 在两种容器中的存储方式就不同, 放入和取出的方式也不一样

栈
栈:
^  |
|  v
|                   |  出入口在同一端
| +---------+ |
| |       3    | |
| +---------+ |
| +---------+ |
| |       2    | | 栈
| +---------+ |
| +---------+ |
| |    1    | |
| +---------+ |
+-------------+

栈的特点:
先进后出 (FILO, First In Last Out)
入口和出口在同一侧

入栈(压栈): 将元素存入栈
出栈(弹栈): 从栈中取出元素

栈的适用场景:
栈内存 (main方法先进栈调用, main方法中的其他方法都调用完毕后, main才能出栈)
反转内容 (车尾变车头, 进去再出来就反转了)

队列队列:

入口                                                 出口
   -----------------------------------------------
               +---------+ +---------+ +---------+
---->          | 3    | |    2       | |       1    |  ---->
               +---------+ +---------+ +---------+
   -----------------------------------------------

队列的特点:
先进先出 (FIFO, First In First Out)
入口和出口在两端

队列的适用场景:
秒杀, 抢购
在线售票
处理高并发场景

数组
数组:
   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"  |  创建一个新数组, 将原数组元素复制进去, 然后存入新元素
+-----+-----+-----+-----+-----+-----+

数组的适用场景:
查询多, 增删少的数据存储场景国内城市

链表
链表: 链表由多个节点(Node / Entry) 组成
+-----+-----+-----+ +-----+-----+
|    |    |    |    |数据  |    |
+-----+-----+-----+ +-----+-----+

单向链表: 每个节点存储数据和下一个节点的地址值

链表 = 0x11

0x11             0x44             0x88
+-----+-----+    +-----+-----+    +-----+-----+
|  "a"  |  0x44| --> | "b" | 0x88  | --> | "c" | null |
+-----+-----+    +-----+-----+    +-----+-----+
   数据  下一个    数据  下一个    数据  下一个

双向链表: 每个节点存储数据, 上一个节点地址值和下一个节点地址值
0x11                   0x44                   0x88
+-----+-----+-----+    +-----+-----+-----+    +-----+-----+-----+
| null  | "a" | 0x44 | <--> | 0x11 | "b" | 0x88  | <--> |0x44 | "c" | null|
+-----+-----+-----+    +-----+-----+-----+    +-----+-----+-----+
   上一个  数据  下一个    上一个  数据  下一个    上一个  数据  下一个

链表的特点:
查询慢: 要找到其中某个节点, 只能从第一个节点一个一个向后寻找
增删快: 只需要修改保存的下一个节点的地址值, 就可以快速完成增删

// 删除结点
+---+ +---+ +---+
|  1 |----|  2  |----|  3 |
+---+ +---+ +---+

+---+          +---+
|  1  |-------------|  3 |
+---+          +---+
         +---+
            | 2 |
         +---+

链表的适用场景:
查询少, 增删多的场景
链表可以实现栈和队列的结构, 因为栈和队列增删频繁
补充：

[Java] 纯文本查看 复制代码

代码中链表节点的实现:

// 单向链表的节点
class Node<T> {
	T data;       // 存储的数据
	Node next;    // 下一个节点的地址值
}

// 双向链表的节点
class Node<T> {
	T data;       // 存储的数据
	Node before;  // 上一个节点的地址值
	Node after;   // 下一个节点的地址值
}

红黑树
红黑树: 是一种平衡二叉查找树
平衡: 左子节点和右子节点数量相等
二叉: 每个节点最多有2个子节点
查找: 节点存储的元素是按照大小顺序存储的
特点:
元素存储过程中就完成了大小排序
查询比链表快, 增删比数组快 (数组和链表的折中)

红黑树的适用场景:
查询和增删都有, 需要元素自动排序的场景
树的遍历:

补充：

[Java] 纯文本查看 复制代码

代码中树节点的实现

// 树的节点
class Entry<T> {
	T data;           // 存储的数据
	Entry left;       // 左子节点的地址值
	Entry right;      // 右子节点的地址值
	Entry parent;     // 父节点的地址值
}

List集合List介绍和常用方法
List集合体系的特点:
1. 元素存取有序 (存入和取出元素的顺序一致) 3 2 1 3 2 1
2. 元素可以重复 3 2 2 1
3. 有索引
List子体系中的实现类都具有上述特点

java.util.List接口:
// 常用特有成员方法 (都是按照索引来操作的)
void add(int index, E element): 将指定的元素, 添加到该集合中的指定位置上
E get(int index): 返回集合中指定位置的元素
E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素
E set(int index, E element): 用指定元素替换集合中指定位置的元素, 返回值的更新前的元素
ArrayList集合的特点
ArrayList底层的数据结构:
数组

ArrayList的特点:
查询快
增删慢
线程不安全, 效率高

ArrayList适用场景:
存储的数据"查询多, 增删少"的场景. 如用一个ArrayList存储中国城市名称
LinkedList集合的特点和特有方法
LinkedList底层的数据结构:
链表

LinkedList的特点:
查询慢
增删快
线程不安全, 效率高

LinkedList适用场景:
存储的数据"查询少, 增删多"的场景. 如用LinkedList实现栈或队列

java.util.LinkedList<E>类: 链表结构, 查询慢, 增删快
// 特有成员方法(主要操作开头和末尾元素)
void addFirst(E e): 将指定元素插入此列表的开头
void addLast(E e): 将指定元素添加到此列表的结尾
E getFirst(): 返回此列表的第一个元素
E getLast(): 返回此列表的最后一个元素
E removeFirst(): 移除并返回此列表的第一个元素
E removeLast(): 移除并返回此列表的最后一个元素
E pop(): (其实就是removeFirst())从此列表所表示的栈中弹出一个元素
void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中
5分钟练习: 测试LinkedList特有方法
需求:
创建LinkedList集合, 添加元素1,2,3, 测试特有方法:
void addFirst(E e): 将指定元素插入此列表的开头
void addLast(E e): 将指定元素添加到此列表的结尾
E getFirst(): 返回此列表的第一个元素
E getLast(): 返回此列表的最后一个元素
E removeFirst(): 移除并返回此列表的第一个元素
E removeLast(): 移除并返回此列表的最后一个元素
E pop(): (其实就是removeFirst())从此列表所表示的栈中弹出一个元素
void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中
代码：

[Java] 纯文本查看 复制代码

public class Test {
    public static void main(String[] args) {
        // 创建LinkedList集合
        LinkedList<Integer> list = new LinkedList<>();

        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println("最初的集合:"+list);

        // void addFirst(E e): 将指定元素插入此列表的开头
        list.addFirst(0);
        System.out.println(list);

        // void addLast(E e): 将指定元素添加到此列表的结尾
        list.addLast(9);
        System.out.println(list);

        // E getFirst(): 返回此列表的第一个元素
        Integer getFirst = list.getFirst();
        System.out.println("getFirst:" + getFirst);

        // E getLast(): 返回此列表的最后一个元素
        Integer getLast = list.getLast();
        System.out.println("getLast:" + getLast);

        // E removeFirst(): 移除并返回此列表的第一个元素
        Integer removeFirst = list.removeFirst();
        System.out.println("removeFirst:" + removeFirst);

        // E removeLast(): 移除并返回此列表的最后一个元素
        Integer removeLast = list.removeLast();
        System.out.println("removeLast:" + removeLast);

        // E pop(): (其实就是removeFirst())从此列表所表示的栈中弹出一个元素
        Integer pop = list.pop();
        System.out.println("pop:" + pop);

        // void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中
        list.push(666);
        System.out.println(list);
    }
}

Vector集合
JDK 1.0 版本中只有一个 Vector集合
JDK 1.2 开始增加了Collection集合体系

Vector底层的数据结构:
数组

Vector的特点:
查询慢
增删快
(同步)线程安全, 效率低

Vector目前几乎没人使用
Set集合体系HashSet集合
Set集合体系特点:
1. 元素不可重复
2. 没有索引

HashSet特点:
1. 元素不可重复
2. 没有索引
3. 元素存取无序 (存入和取出顺序有可能不一致)
4. 底层采用哈希表结构. (查询快)
哈希表 = 数组 + 链表或红黑树

java.util.HashSet类:
// 常用方法
boolean add(E e): 添加元素, 根据元素的 hashCode() 和 equals() 方法判断是否重复. 重复则不添加并返回false, 不重复则添加并返回true
5分钟练习: 使用HashSet添加元素
需求:
创建HashSet对象, 存储 5,5,4,4,3,3,2,2,1,1, 使用增强for遍历HashSet集合打印元素, 查看是否和存入顺序一致, 是否有重复元素
代码：

[Java] 纯文本查看 复制代码

public class Test {
    public static void main(String[] args) {
        // 创建HashSet集合, 用不用多态都行, 因为add方法不是子类特有的
        Set<Integer> set = new HashSet<>();

        // 添加元素
        set.add(5);
        set.add(5);
        set.add(4);
        set.add(4);
        set.add(3);
        set.add(3);
        set.add(2);
        set.add(2);
        set.add(1);
        set.add(1);

        // 增强for遍历
        for (Integer integer : set) {
            System.out.println(integer);  // 1 2 3 4 5
        }

    }
}

HashSet原理: 哈希值
哈希值:
一个十进制数值, 一般是通过将该对象的内部地址转换成一个整数来实现的

public native int hashCode();
可以调用系统本地代码(C/C++)计算出一个对象地址的哈希值

hashCode()方法的作用
方法内部的算法用于将对象计算为一个哈希值, 便于根据哈希值比较对象是否"相等"
哈希值主要是为了提高对象存储在哈希表中的效率

注意:
1. 如果我们不满意Object中的哈希值计算方法, 可以重写hashCode()方法.
但在Java代码中不能直接重写带有 native 的方法, 重写时应该将 native 去掉
@Override
public int hashCode() {}
2. hashCode() 方法有可能将"不同的对象"计算出"相同的哈希值", 这称为"哈希冲突", 在出现冲突后, 一般再通过 equals() 方法来继续判断对象是否"相等"

"重地" "通话"
HashSet原理: 哈希表结构
哈希表:
JDK 8以前 : 哈希表 = 数组 + 链表
JDK 8及之后 : 哈希表 = 数组 + 链表或红黑树
数组中存储的每个元素, 是哈希值相同的一组节点的链表或红黑树
HashSet原理: 存储元素不重复的原理
HashSet集合保证添加元素不重复的原理:
调用 add(E e) 添加元素时, 先调用 hashCode() 获取哈希值, 和当前HashSet集合中的元素比较
如果哈希值不同, 则认为元素不重复, 添加, 并返回true
如果哈希值相同, 则有可能是哈希冲突, 所以继续调用元素的 equals() 方法和所有哈希值相同的元素比较
如果 equals() 比较所有元素都没有相同的, 则认为元素不重复, 添加, 并返回true
如果 equals() 比较出有相同的元素, 则认为元素重复, 不添加, 并返回false

HashSet存储自定义元素的去重
自定义JavaBean对象实现在HashSet中去重:
JavaBean默认继承Object类中的 hashCode() 和 equals() 方法, 都是根据对象地址值判断是否重复的
要根据属性值判断是否重复, 应该在JavaBean类中重写 hashCode() 和 equals() 方法, 使其按照属性值比较
5分钟练习: 自定义Person类存入HashSet实现去重
需求:
定义Person类:
私有成员变量: 姓名String name, 年龄int age
生成无参/有参构造, set/get方法, toString()方法
生成 hashCode() 和 equals() 方法
定义测试类
创建3个Person对象, 其中2个对象的姓名和年龄均相同, 另外1个对象姓名或年龄不同
创建HashSet集合, 存入3个Person对象, 打印HashSet集合, 查看是否去重
代码：

[Java] 纯文本查看 复制代码

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 +
                '}';
    }

    // 生成hashCode()和equals()方法, 根据属性值判断是否重复, 用于存储HashSet去重
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age &&
                Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

public class Test {
    public static void main(String[] args) {
        // 创建3个Person对象
        Person p1 = new Person("张三", 13);
        Person p2 = new Person("张三", 13);
        Person p3 = new Person("张三", 55); // 年龄不同

        // 创建HashSet集合
        HashSet<Person> set = new HashSet<>();
        set.add(p1);
        set.add(p2);
        set.add(p3);

        // 打印集合, 查看是否去重
        System.out.println(set);
        // [Person{name='张三', age=55}, Person{name='张三', age=13}]
    }
}

LinkedHashSet集合
LinkedHashSet特点:
1. 元素存取有序 (存入和取出顺序一致)
2. 元素不可重复
3. 没有索引

LinkedHashSet底层数据结构:
哈希表 + 链表 (也就是: 数组 + 链表或红黑树 + 链表)
其中, 哈希表用于存储数据, 额外的链表用于记录元素添加时的先后顺序, 以便在获取元素时保持顺序一致
补充：
总结: 什么时候用List, 什么时候用Set?
要存储的元素可以重复的, 用List集合:
增删少, 用ArrayList
增删多, 用LinkedList
要存储的数据要求不重复, 或者相对一个集合去重, 用Set集合:
不要求存取顺序一致, 用HashSet
要求存取顺序一致, 用LinkedHashSet
5分钟练习: 使用LinkedHashSet存储元素
需求:
创建LinkedHashSet对象, 存储 5,5,4,4,3,3,2,2,1,1, 使用增强for遍历LinkedHashSet集合打印元素, 查看是否和存入顺序一致
可变参数
可变参数:
JDK 5 出现. 指同一个类型参数个数可变的参数
可变参数的本质就是一个"数组"

格式: 用在方法的参数中
修饰符返回值类型方法名(int... 变量名) {
// 可以直接将变量名当作数组名使用
}
方法名();

注意事项:
1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
2. 一个方法的参数列表中, 只能有一个可变参数
3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后
Collections集合工具类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):将集合中元素按照指定规则排序
5分钟练习: 测试addAll()和shuffle()方法
需求:
创建ArrayList集合, 使用Collections.addAll()方法, 向集合中添加1,2,3,4,5
然后调用shuffle()方法打乱该集合的顺序, 打印集合查看效果
代码：

[Java] 纯文本查看 复制代码

public class Test {
    public static void main(String[] args) {
        // 创建ArrayList集合
        ArrayList<Integer> list = new ArrayList<>();

        Collections.addAll(list, 1, 2, 3, 4, 5);

        System.out.println(list);  // [1, 2, 3, 4, 5]

        // 打乱
        Collections.shuffle(list);

        // 查看打乱后的结果
        System.out.println(list);  // [4, 2, 3, 1, 5]
    }
}

Collections集合工具类: sort(List<T> list)
sort(List<T> list): 默认按照"升序"将元素排序
数字, 字母, 都可以按照升序排序

自定义JavaBean对象默认不能排序, 因为不知道如何比较哪个对象大, 哪个对象小
自定义JavaBean对象要想排序, 需要实现 Comparable<E> 接口, 重写 int compareTo(E e) 方法
规则:
this-参数: 升序(从小到大)
参数-this: 降序(从大到小)
5分钟练习: 实现Person排序
需求:
定义Person类, 实现Comparable接口, 泛型为Person:
私有成员变量: 姓名String name, 年龄int age
生成无参/有参构造, set/get方法, toString()
重写int compareTo(E e)方法
方法内部根据Person对象的年龄计算大小
定义测试类
创建3个Person对象, 分别为:
李四, 14
张三, 13
王五, 15
创建ArrayList集合, 存储3个Person对象
调用 Collections.sort() 方法, 对集合排序, 然后使用增强for遍历输出结果, 查看是否排序
代码：

[Java] 纯文本查看 复制代码

public class Person implements Comparable<Person> {  // 让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 +
                '}';
    }

    @Override
    public int compareTo(Person o) {
        /*
        规则:
            this-参数: 升序从小到大
            参数-this: 降序从大到小
         */
        // 按照Person对象的年龄升序排序
//        return this.getAge() - o.getAge();

        // 按照Person对象的年龄降序排序
        return o.getAge() - this.getAge();
    }
}

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);

        // 将3个对象存入集合
        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);

    }
}

Collections集合工具类: sort(List<T> list，Comparator<? super T> )
Comparable接口和Comparator接口区别
Comparable: 让JavaBean自身具有可比较性 (自己和其他人比)
Comparator: 定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)

Comparator使用方式:
定义类作为比较器, 实现Comparator<E>接口, 重写 int compare(E o1, E o2) 方法, 泛型为要比较的元素的类型
在Collections.sort(List<T> list，Comparator<? super T> c)方法中传入自定义比较器对象
规则:
o1-o2: 升序(从小到大)
o2-o1: 降序(从大到小)
5分钟练习: 使用Comparator对Person集合排序
需求:
定义Person类:
私有成员变量: 姓名String name, 年龄int age
生成无参/有参构造, set/get方法, toString()
定义测试类
创建3个Person对象, 分别为:
李四, 14
张三, 13
王五, 15
创建ArrayList集合, 存储3个Person对象
调用Collections.sort(List<T> list，Comparator<? super T> c)方法, 对集合排序, 比较器使用匿名内部类对象方式, 按照Person对象的年龄排序
然后使用增强for遍历输出结果, 查看是否排序
代码：

[Java] 纯文本查看 复制代码

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) {
        // 创建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, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                /*
                规则:
                    o1-o2: 升序
                    o2-o1: 降序
                 */
                // 按照年龄升序
//                return o1.getAge() - o2.getAge();

                // 按照年龄降序
                return o2.getAge() - o1.getAge();
            }
        });
        System.out.println("排序后:" + list);
    }
}

cuipu · cuipu

顶顶顶~~~~~~!

鸽子dove · 鸽子dove

顶顶顶~~~~~~!

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] 【石家庄校区】就业班day03-List,Set

评分

2 个回复

浏览过的版块