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

顶顶顶~~~~~~!

顶顶顶~~~~~~!