[数据结构与算法]Java基础：集合（Collection、数据结构、List、泛型深入）

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

集合体系特点

• 集合与数组

  • 数组和集合的元素存储的个数

    • 数组定义后类型确定，长度固定
    • 集合类型可以不固定，大小是可变的

  • 数组和集合存储元素的类型

    • 数组可以存储基本类型和引用类型的数据
    • 集合只能存储引用数据类型的数据

  • 数组和集合适合的场景

    • 数组适合做数据个数和类型确定的场景
    • 集合适合做数据个数不确定，且要做增删元素的场景，集合种类更多，功能更强大

1. 集合的代表：Collection接口
2. Collection集合分了2大常用的集合体系：
   • List系列集合：添加的元素是有序、可重复、有索引
   • Set系列集合：添加的元素是无序、不重复、无索引
3. 约定集合存储数据的类型，需要注意：
   • 集合支持泛型
   • 集合和泛型不支持基本类型，只支持引用数据类型

Collection集合常用API

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

• Collection API如下

Collection集合的遍历方式

方式一：迭代器

1. 迭代器遍历概述

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

2. Collection集合获取迭代器

   方法名称	说明
   Iterator iterator()	返回集合中的迭代器对象，该迭代器对象默认指向当前集合的0索引

3. Iterator中的常用方法

   方法名称	说明
   boolean hasNext()	询问当前位置是否有元素存在，存在返回true ,不存在返回false
   E next()	获取当前位置的元素，并同时将迭代器对象移向下一个位置，注意防止取出越界

4. 迭代器执行流程

Iterator<String> it = lists.iterator();
while(it.hasNext()){
  String ele = it.next();
  System.out.println(ele);
}

5. 注意事项
   • 迭代器的默认位置：Iterator iterator()：得到迭代器对象，默认指向当前集合的索引0
   • 迭代器如果取元素越界会出现NoSuchElementException异常

方式二：foreach（增强for循环）

• 增强for循环

for(元素数据类型 变量名 : 数组或者Collection集合) {
         //在此处使用变量即可，该变量就是元素
}

Collection<String> list = new ArrayList<>();
...
for(String ele : list) {
    System.out.println(ele);
}

修改其中ele变量的值不会影响到集合中的元素，增强for既可以遍历集合也可以遍历数组

方式三：lambda表达式

• Collection结合Lambda遍历的API

Collection<String> lists = new ArrayList<>();
...
lists.forEach(new Consumer<String>() {
    @Override
        public void accept(String s) {
                System.out.println(s);
        }
});
// 使用lambda遍历
  lists.forEach(s -> {
         System.out.println(s);
   });
   //  lists.forEach(s -> System.out.println(s));

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

• 需求： 某影院系统需要在后台存储三部电影，然后依次展示出来
• 分析：
  • ：定义一个电影类，定义一个集合存储电影对象。
  • ：创建3个电影对象，封装相关数据，把3个对象存入到集合中去。
  • ：遍历集合中的3个对象，输出相关信息。

public class Movie {    
  private String name; 
  private double score;
  private String acotr;
  public Movie(String name, double score, String acotr) {
    this.name = name;
    this.score = score;
    this.acotr = acotr;
}
// ... getter + setter

public class SystemDemo {
    public static void main(String[] args) {
            Collection <Movie> movies = new ArrayList<>();
            movies.add(new Movie(“《肖生克的救赎》”, 9.7 ,  “罗宾斯”));
            movies.add(new Movie(“《霸王别姬》”, 9.6 ,  “张国荣、张丰毅”));
            movies.add(new Movie(“《阿甘正传》”, 9.5 ,  “汤姆.汉克斯"));
            System.out.println(movies);
            for (Movie movie : movies) {
           	    System.out.println("片名：" + movie.getName());
                System.out.println("评分：" + movie.getScore());  
                System.out.println("主演：" + movie.getAcotr());
                }
     }
}

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

数据结构

数据就结构概述

1. 数据结构概述
   • 数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的
   • 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率
2. 常见的数据结构
   • 栈
   • 队列
   • 数据
   • 链表
   • 二叉树
   • 二叉查找树
   • 平衡二叉树
   • 红黑树
   • …

栈

栈数据结构的执行特点：先进后出，后进先出

队列

队列数据结构的执行特点：先进先出，后进后出

数组

数组是一种查询快，增删慢的模型

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

链表

链表的特点

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

二叉树、二叉查找树

1. 二叉树
   • 只能有一个根节点，每个节点最多支持2个直接子节点。
   • 节点的度： 节点拥有的子树的个数，二叉树的度不大于2 叶子节点 度为0的节点，也称之为终端结点。
   • 高度：叶子结点的高度为1，叶子结点的父节点高度为2，以此类推，根节点的高度最高。
   • 层：根节点在第一层，以此类推
   • 兄弟节点 ：拥有共同父节点的节点互称为兄弟节点
     
2. 二叉查找树

• 二叉查找树又称二叉排序树或者二叉搜索树。特点：
  • 每一个节点上最多有两个子节点
  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值
• 二叉树查找树添节点规则：
  • 小的存左边
  • 大的存右边
  • 一样的不存
    

平衡二叉树

1. 二叉树查找存在的问题：
   
   问题：出现瘸子现象，导致查询的性能与单链表一样，查询速度变慢！
2. 平衡二叉树特点
   • 平衡二叉树是在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。
     
3. 平衡二叉树的要求
   • 任意节点的左右两个子树的高度差不超过1，任意节点的左右两个子树都是一颗平衡二叉树
     

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

1. 平衡二叉树-左左

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

2. 平衡二叉树-左右

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

3. 平衡二叉树-右右

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

4. 平衡二叉树-右左

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

红黑树

1. 红黑树概述
   • 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
   • 1972年出现，当时被称之为平衡二叉B树。1978年被修改为如今的"红黑树"
   • 每一个节点可以是红或者黑；红黑树不是通过高度平衡的，它的平衡是通过红黑规则进行实现的
     
2. 红黑规则
   • 每一个节点是红色的，或者是黑色的，根节点必须是黑色
   • 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
   • 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
3. 添加节点
   • 添加的节点的颜色，可以是红色的，也可以是黑色的。
   • 默认用红色效率高。
     
     当添加的节点为根节点时，直接变成黑色就可以了
     
     
4. 红黑树小结

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

数据结构总结队列：先进先出，后进后出。

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

List集合

List集合特点及特有API

1. List系列集合特点
   • ArrayList、LinekdList ：有序，可重复，有索引。
   • 有序：存储和取出的元素顺序一致
   • 有索引：可以通过索引操作元素
   • 可重复：存储的元素可以重复
2. List集合特有的方法
   • List集合因为支持索引，所以多了很多索引操作的独特api，其他Collection的功能List也都继承了

3. List的实现类的底层原理

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

List集合的遍历方式小结

1. 迭代器
2. 增强for循环
3. Lambda表达式
4. for循环（因为List集合存在索引）

ArrayList集合的底层原理

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

List<String> list = new ArrayList<>();
list.add("a");

LinkedList集合的底层原理

1. LinkedList的特点：底层数据结构是双链表，查询慢，首尾操作的速度是极快的，所以多了很多首尾操作的特有API
2. LinkedList集合的特有功能

集合的并发修改异常问题

泛型深入

泛型的概述和优势

1. 泛型概述

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

2. 泛型的优势

   • 统一数据类型
   • 把运行时期的问题提前到了编译期间，避免了强制类型转换可能出现的异常，因为编译阶段类型就能确定下来
   • 泛型可以在很多地方进行定义：
   • 类后面 （泛型类）；方法申明上（ 泛型方法）；接口后面 （泛型接口）

自定义泛型类

1. 泛型类的概述
   • 定义类时同时定义了泛型的类就是泛型类。
   • 泛型类的格式：修饰符 class 类名<泛型变量>{ }
     public class MyArrayList<T> { }
   • 此处泛型变量T可以随便写为任意标识，常见的如E、T、K、V等。
   • 作用：编译阶段可以指定数据类型，类似于集合的作用
2. 泛型类的原理：
   • 把出现泛型变量的地方全部替换成传输的真实数据类型。

自定义泛型方法

1. 泛型方法的概述

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

2. 泛型方法的原理：

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

自定义泛型接口

1. 泛型接口的概述
   • 使用了泛型定义的接口就是泛型接口。
   • 泛型接口的格式：修饰符 interface 接口名称<泛型变量>{ }
     public interface Data<E>{}
   • 作用：泛型接口可以约束实现类，实现类可以在实现接口的时候传入自己操作的数据类型这样重写的方法都将是针对于该类型的操作。
2. 泛型接口的原理
   • 实现类可以在实现接口的时候传入自己操作的数据类型，这样重写的方法都将是针对于该类型的操作。

泛型通配符、上下限

1. 通配符:?
   • ? 可以在“使用泛型”的时候代表一切类型。
   • E T K V 是在定义泛型的时候使用的。
2. 虽然BMW和BENZ都继承了Car但是ArrayList和ArrayList与ArrayList没有关系的
3. 泛型的上下限：
   • ? extends Car: ?必须是Car或者其子类 泛型上限
   • ? super Car ： ?必须是Car或者其父类 泛型下限