Java - day14 - 集合（Collection、数据结构、List、泛型深入）

集合概述

• 集合是Java中存储对象数据的一种容器。

集合的特点

• 集合的大小不固定，启动后可以动态变化，类型也可以选择不固定。集合更像气球。
• 集合非常适合做元素的增删操作。
• 注意：集合中只能存储引用类型数据，如果要存储基本类型数据可以选用包装类。

集合适合的场景

• 数据的个数不确定，需要进行增删元素的时候。

Collection集合的体系特点

集合类体系结构

• collection单列集合，每个元素（数据）只包含一个值。
• Map双列集合，每个元素包含两个值（键值对）。
• 注意：前期先掌握Collection集合体系的使用。
• 

Collection集合特点

• List系列集合：添加的元素是有序、可重复、有索引。
• ArrayList、LinekdList ：有序、可重复、有索引。
• Set系列集合：添加的元素是无序、不重复、无索引。
• HashSet：无序、不重复、无索引;LinkedHashset:有序、不重复、无索引。
• TreeSet：按照大小默认升序排序、不重复、无索引。

集合对于泛型的支持

• 集合都是支持泛型的，可以在编译阶段约束集合只能操作某种数据类型

  Collection<string> lists = new ArrayList<string>();
  Collection<String> lists = new ArrayList<>();//JDK1.7开始后面的泛型类型申明可以省略不写
  

• 注意：集合和泛型都只能支持引用数据类型，不支持基本数据类型，所以集合中存储的元素都认为是对象。

如果集合中要存储基本类型的数据怎么办?

//存储基本类型使用包装类
Collection<Integer> lists = new ArrayList<>();
Collection<Double> lists = new ArrayList<>();

Collection集合常用API

Collection集合

• Collection是单列集合的祖宗接口，它的功能是全部单列集合都可以继承使用的。
• Collection API如下:
• 

Collection集合的遍历方式

方式一：迭代器

迭代器遍历概述

• 遍历就是一个一个的把容器中的元素访问一遍。
• 迭代器在Java中的代表是lterator，迭代器是集合的专用遍历方式。

Collection集合获取迭代器

lterator中的常用方法

方式二：foreach/增强for循环

增强for循环

• 增强for循环：既可以遍历集合也可以遍历数组。
• 它是JDK5之后出现的，其内部原理是一个lterator迭代器，遍历集合相当于是迭代器的简化写法。
• 实现lterable接口的类才可以使用迭代器和增强for，collection接口已经实现了lterable接口。
• 

方式三：lambda表达式

Lambda表达式遍历集合

• 得益于JDK 8开始的新技术Lambda表达式，提供了一种更简单、更直接的遍历集合的方式。

Collection结合Lambda遍历的API

Collection集合存储自定义类型的对象

集合中存储的是元素的什么信息?

• 集合中存储的是元素对象的地址。

实例：

package Collection集合存储自定义类型的对象;

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        // 1、定义一个电影类
        // 2、定义一个集合对象存储3部电影对象
        Collection<Movie> movies = new ArrayList<>();
        movies.add(new Movie("《你好，李焕英》", 9.5, "张小斐,贾玲,沈腾,陈赫"));
        movies.add(new Movie("《唐人街探案》", 8.5, "王宝强,刘昊然,美女"));
        movies.add(new Movie("《刺杀小说家》",8.6, "雷佳音,杨幂"));

        System.out.println(movies);

        // 3、遍历集合容器中的每个电影对象
        for (Movie movie : movies) {
            System.out.println("片名：" + movie.getName());
            System.out.println("得分：" + movie.getScore());
            System.out.println("主演：" + movie.getActor());
        }

    }
}

package Collection集合存储自定义类型的对象;

public class Movie {
    private String name;
    private double score;
    private String actor;

    public Movie() {
    }

    public Movie(String name, double score, String actor) {
        this.name = name;
        this.score = score;
        this.actor = actor;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getScore() {
        return score;
    }

    public void setScore(double score) {
        this.score = score;
    }

    public String getActor() {
        return actor;
    }

    public void setActor(String actor) {
        this.actor = actor;
    }

    @Override
    public String toString() {
        return "Movie{" +
                "name='" + name + '\'' +
                ", score=" + score +
                ", actor='" + actor + '\'' +
                '}';
    }
}

常见数据结构

数据结构概述、栈、队列

• 数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。
• 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

栈的执行特点

• 后进先出，先进后出

队列

• 先进先出，后进后出
• 数据从后端进入队列模型的过程称为：入队列
• 数据从前端离开队列模型的过程称为：出队列

数组

• 数组是一种查询快，增删慢的模型。
• 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同。(元素在内存中是连续存储的)
• 删除效率低：要将原始数据删除，同时后面每个数据前移。
• 添加效率极低：添加位置后的每个数据后移，再添加元素。

链表

链表的特点

• 链表中的元素是在内存中不连续存储的，每个元素节点包含数据值和下一个元素的地址。
• 链表查询慢。无论查询哪个数据都要从头开始找。
• 链表增删相对快。
• 
• 
• 
• 

链表的种类

• 单向链表
• 双向链表
• 

二叉树、二叉查找树

二叉树概述

二叉树特点

• 只能有一个根节点，每个节点最多支持2个直接子节点。
• 节点的度:节点拥有的子树的个数，二叉树的度不大于2叶子节点度为o的节点，也称之为终端结点。
• 
• 
• 二叉查找树又称二叉排序树或者二叉搜索树。
• 特点:
• 每一个节点上最多有两个子节点
• 左子树上所有节点的值都小于根节点的值
• 右子树上所有节点的值都大于根节点的值
• 目的：提高检索数据的性能。

二叉树查找树添节点

• 规则:
• 小的存左边
• 大的存右边
• 一样的不存

平衡二叉树

• 平衡二叉树是在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。
• 

平衡二叉树的要求

• 任意节点的左右两个子树的高度差不超过1，任意节点的左右两个子树都是一颗平衡二叉树

识别如下是否是平衡二叉树

平衡二叉树在添加元素后可能导致不平衡

• 基本策略是进行左旋，或者右旋保证平衡。

平衡二叉树 - 旋转的四种情况

左左

• 当根节点左子树的左子树有节点插入，导致二叉树不平衡

左右

• 当根节点左子树的右子树有节点插入，导致二叉树不平衡

右右

• 当根节点右子树的右子树有节点插入，导致二叉树不平衡

右左

• 当根节点右子树的左子树有节点插入，导致二叉树不平衡

红黑树

• 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。
• 1972年出现，当时被称之为平衡二叉B树。1978年被修改为如今的"红黑树"。
• 每一个节点可以是红或者黑;红黑树不是通过高度平衡的，它的平衡是通过“红黑规则”进行实现的。

红黑规则

• 每一个节点或是红色的，或者是黑色的，根节点必须是黑色。
• 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，叶节点是黑色的。
• 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
• 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
• 红黑树增删改查的性能都很好
• 

总计

各种数据结构的特点和作用是什么样的

• 队列:先进先出，后进后出。
• 栈:后进先出，先进后出。
• 数组:内存连续区域，查询快，增删慢。
• 链表:元素是游离的，查询慢，首尾操作极快。
• 二叉树:永远只有一个根节点,每个结点不超过2个子节点的树。
• 查找二叉树:小的左边，大的右边，但是可能树很高，查询性能变差。
• 平衡查找二叉树:让树的高度差不大于1，增删改查都提高了。
• 红黑树（就是基于红黑规则实现了自平衡的排序二叉树)

List系列集合

List集合特点、特有API

List系列集合特点

• ArrayList、LinekdList：有序，可重复，有索引。

List的实现类的底层原理

• ArrayList底层是基于数组实现的，根据查询元素快，增删相对慢。
• LinkedList底层基于双链表实现的，查询元素慢，增删首尾元素是非常快的。

List集合特有方法

• List集合因为支持索引，所以多了很多索引操作的独特api，其他Collection的功能List也都继承了。
• 

List集合的遍历方式小结

• 迭代器
• 增强for循环
• Lambda表达式
• for循环（因为List集合存在索引)

ArrayList集合的底层原理

• ArrayList底层是基于数组实现的:根据索引定位元素快，增删需要做元素的移位操作。
• 第一次创建集合并添加第一个元素的时候，在底层创建一个默认长度为10的数组。

LinkedList集合的底层原理

LinkedList的特点

• 底层数据结构是双链表，查询慢，首尾操作的速度是极快的，所以多了很多首尾操作的特有API。

LinkedList集合的特有功能

补充知识:集合的并发修改异常问题

问题引出

• 当我们从集合中找出某个元素并删除的时候可能出现一种并发修改异常问题。

哪些遍历存在问题?

• 迭代器遍历集合且直接用集合删除元素的时候可能出现。
• 增强for循环遍历集合且直接用集合删除元素的时候可能出现。

哪种遍历且删除元素不出问题

• 迭代器遍历集合但是用迭代器自己的删除方法操作可以解决。
• 使用for循环遍历并删除元素不会存在这个问题。

补充知识:泛型深入

泛型的概述和优势

泛型概述

• 泛型:是JDK5中引入的特性，可以在编译阶段约束操作的数据类型，并进行检查。
• 泛型的格式：<数据类型>;
• 注意:泛型只能支持引用数据类型。
• 集合体系的全部接口和实现类都是支持泛型的使用的。

泛型的好处

• 统一数据类型。
• 把运行时期的问题提前到了编译期间，避免了强制类型转换可能
  出现的异常，因为编译阶段类型就能确定下来。

泛型可以在很多地方进行定义:

• 类后面 → 泛型类
• 方法申明上 → 泛型方法
• 接口后面 → 泛型接口

自定义泛型类

泛型类的概述

• 定义类时同时定义了泛型的类就是泛型类。
• 泛型类的格式：修饰符 class 类名 <泛型变量> { }
• 范例: public class MyArrayList<T>{}
• 此处泛型变量T可以随便写为任意标识，常见的如E、T、K、V等。
• 作用：编译阶段可以指定数据类型，类似于集合的作用。

课程案例导学

• 模拟ArrayList集合自定义一个集合MyArrayList集合,完成添加和删除功能的泛型设计即可。

实例：

package 泛型类;

public class Test {
    public static void main(String[] args) {
        // 需求：模拟ArrayList定义一个MyArrayList ，关注泛型设计
        MyArrayList<String> list = new MyArrayList<>();
        list.add("Java");
        list.add("Java");
        list.add("MySQL");
        list.remove("MySQL");
        System.out.println(list);

        MyArrayList<Integer> list2 = new MyArrayList<>();
        list2.add(23);
        list2.add(24);
        list2.add(25);
        list2.remove(25);
        System.out.println(list2);
    }
}

package 泛型类;

import java.util.ArrayList;

public class MyArrayList<E> {
    private ArrayList lists = new ArrayList();

    public void add(E e){
        lists.add(e);
    }

    public void remove(E e){
        lists.remove(e);
    }

    @Override
    public String toString() {
        return lists.toString();
    }
}

泛型类的原理

• 把出现泛型变量的地方全部替换成传输的真实数据类型。

泛型类的核心思想:

• 把出现泛型变量的地方全部替换成传输的真实数据类型

泛型类的作用

• 编译阶段约定操作的数据的类型，类似于集合的作用。

自定义泛型方法

泛型方法的概述

• 定义方法时同时定义了泛型的方法就是泛型方法。
• 泛型方法的格式：修饰符 <泛型变量> 方法返回值 方法名称(形参列表){ }
• 范例: public <T> void show(T t){ }
• 作用：方法中可以使用泛型接收一切实际类型的参数，方法更具备通用性。

泛型方法的原理:

• 把出现泛型变量的地方全部替换成传输的真实数据类型。

课程案例导学

• 给你任何一个类型的数组，都能返回它的内容。也就是实现Arrays.toString(数组)的功能!

实例：

package 自定义泛型方法;

public class GenericDemo {
    public static void main(String[] args) {
        String[] names = {"小璐", "蓉容", "小何"};
        printArray(names);

        Integer[] ages = {10, 20, 30};
        printArray(ages);

        Integer[] ages2 = getArr(ages);
        String[]  names2 = getArr(names);
    }

    public static <T> T[] getArr(T[] arr){
        return arr;
    }

    public static <T> void printArray(T[] arr){
        if(arr != null){
            StringBuilder sb = new StringBuilder("[");
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]).append(i == arr.length - 1 ? "" : ", ");
            }
            sb.append("]");
            System.out.println(sb);
        }else {
            System.out.println(arr);
        }
    }
}

自定义泛型接口

泛型接口的概述

• 使用了泛型定义的接口就是泛型接口。
• 泛型接口的格式:修饰符interface接口名称<泛型变量>
• 范例: public interface Data<E>
• 作用：泛型接口可以让实现类选择当前功能需要操作的数据类型

泛型接口的原理

• 实现类可以在实现接口的时候传入自己操作的数据类型，这样重写的方法都将是针对于该类型的操作。

泛型通配符、上下限

通配符:?

• ? 可以在“使用泛型”的时候代表一切类型。
• E T K V是在定义泛型的时候使用的。

泛型通配符:案例导学

• 开发一个极品飞车的游戏，所有的汽车都能一起参与比赛。
• 注意:
• 虽然BMW和BENZ都继承了Car但是ArrayList<BMW>和ArrayList<BENZ>与ArrayList<Car>没有关系的! !

泛型的上下限:

• ? extends Car: ?必须是Car或者其子类 —— 泛型上限
• ? super Car : ?必须是Car或者其父类 —— 泛型下限

实例：

package 通配符;
import java.util.ArrayList;

public class GenericDemo {
    public static void main(String[] args) {
        ArrayList<BMW> bmws = new ArrayList<>();
        bmws.add(new BMW());
        bmws.add(new BMW());
        bmws.add(new BMW());
        go(bmws);

        ArrayList<BENZ> benzs = new ArrayList<>();
        benzs.add(new BENZ());
        benzs.add(new BENZ());
        benzs.add(new BENZ());
        go(benzs);

        ArrayList<Dog> dogs = new ArrayList<>();
        dogs.add(new Dog());
        dogs.add(new Dog());
        dogs.add(new Dog());
        // go(dogs);
    }

    /**
     所有车比赛
     */
    public static void go(ArrayList<? extends Car> cars){
    }
}

class Dog{

}

class BENZ extends Car{
}

class BMW extends Car{
}

// 父类
class Car{
}